Moat: Generating Logic Puzzles With Exactly One Solution

Moat is the third puzzle game I’ve built, after Arrows and Decanta. The board is a square map split into coloured realms. You place one castle in every row, every column and every realm, and since every castle has a moat around it, no two castles may touch, not even at a corner. If you’ve played Star Battle or the LinkedIn Queens puzzle, the family will feel familiar.

The rule that makes a puzzle like this good is also the hardest one to generate for: every board must have exactly one solution, and logic alone must reach it. A board with two solutions forces the player to guess at some point, and a guess in a logic puzzle feels like cheating. Moat has endless levels, a daily challenge and events, all generated on the phone from a seed, with no server, so the generator has to guarantee that rule on its own, every time, in a few tens of milliseconds.

A random board is never unique

The obvious approach, drawing random realms and checking whether the puzzle happens to have one solution, doesn’t work. I measured it with the game’s own engine on 300 seeds at 8 × 8:

raw boards: unique 0/300; solutions median 275, max 821

Not one random board was unique; the typical one had 275 solutions. So Moat builds the solution first and shapes the board around it, in three steps.

Step 1: place the castles

The castles are the answer, so they come first: one per row and column, and neighbouring rows at least two columns apart, because only castles in neighbouring rows can touch. A small backtracking search does it, trying the columns of each row in a shuffled order drawn from the seed:

export function placeCastles(size: number, rng: Rng): number[] {
  const columns: number[] = [];
  const used = new Set<number>();
  const walk = (row: number): boolean => {
    if (row === size) return true;
    for (const column of rng.shuffle([...Array(size).keys()])) {
      if (used.has(column)) continue;
      if (row > 0 && Math.abs(column - columns[row - 1]!) <= 1) continue;
      columns[row] = column;
      used.add(column);
      if (walk(row + 1)) return true;
      used.delete(column);
    }
    return false;
  };
  if (!walk(0)) throw new Error(`No placement of ${size} castles`);
  return columns.map((column, row) => row * size + column);
}

Step 2: grow a realm around each castle

Each castle seeds a realm. Until every cell is taken, a realm is drawn at random and claims a random free cell next to it. Every realm stays connected and holds exactly one castle, so the intended answer is a valid solution by construction. It just isn’t the only one yet.

Counting solutions, fast

Everything after this depends on one question asked thousands of times: how many solutions does this board have? Moat’s exact solver answers it row by row, with bit masks for the columns and realms already used:

• a castle may not sit within one column of the row above’s, which is all the moat rule asks;
• a realm whose last cell is in this row and still has no castle must take this row’s castle, and two such realms end the branch at once;
• a realm with no free column left in the rows to come ends the branch too.

The last two rules prune the search so early that the solver can stop at a limit: asking for 2 solutions answers “is it unique?”, and asking for 3 returns up to two other solutions (the first the search finds), which is what the next step needs.

Step 3: move border cells until the others die

Here is the idea at the heart of the generator. Take a cell where some other solution puts a castle and the intended solution doesn’t, and move that cell into a neighbouring realm. That neighbouring realm already holds a castle in every solution, so in each other solution that used the moved cell, the realm now holds two castles: those solutions are all gone at once. The intended solution doesn’t care, because none of its castles moved realm.

The move isn’t free, though: a placement that used to put two castles in the old realm and none in the new one can become a new solution, so the count doesn’t always fall. That’s why the generator counts again after every move, and why it has a budget.

const others = solveExact(board, { limit: UNIQUE_SAMPLE + 1 }).filter((s) =>
  s.some((cell) => !intended.has(cell)),
);
if (others.length === 0) return [...board.realmOf]; // unique: done

Each round samples a few other solutions, counts how many of them use each cell, and moves the cell used by the most (ties broken by the seed). If moving the cell would cut its old realm in two, the piece cut off goes with it, so every realm stays connected. After at most 400 moves the generator gives up on the seed.

On the same 300 seeds, this made 190 boards unique (the other 110 ran out of moves and were dropped for the next sub-seed), after 15 moves on average. A board from that run, with realms as letters and castles in lower case, went from 389 solutions to 1 in 13 moves:

BBAaBBBB
BbBBBBBB
BBDBBBBc
BBdEBBBF
BBDEeEFF
BBDHHEfF
gBBHHHFF
GBBHHhHH

Unique isn’t enough: rating with a human-style solver

A board with one solution can still be unfair: the only way through might be to try a castle and see what breaks, many steps deep. So every board also goes through a second solver that plays like a person. It keeps a grid of candidate cells and, at each step, applies the easiest technique that places a castle or rules a cell out, and it never guesses:

1. Last cell: a row, column or realm with one candidate left takes the castle.
2. Confined line: a realm whose candidates lie in one row (or column) rules out the rest of that line, and the reverse.
3. Moat squeeze: a candidate whose castle would wipe out every candidate of another unit is ruled out.
4. k realms, k lines: k realms whose candidates lie in k rows (or columns) rule out the rest of those lines, and the reverse.
5. One-step what-if: suppose a castle, apply 1 to 4, and if some unit is left with no candidate, the supposition was wrong.

A board this solver can’t finish is thrown away. One it finishes gets a rating: the hardest technique it needed, and how often. On the 190 unique boards, every one was finished, and the hardest techniques were spread like this:

Difficulty is a band, not a size

That rating is what the tiers are made of. Easy boards need nothing beyond confined lines; Medium needs the moat squeeze, or two realms in two lines once; Hard needs k realms in k lines with k of three or more, or two realms in two lines more than once; Super Hard needs a what-if. Board size grows slowly over the first 300 levels, but it adds time, not difficulty.

To get a board in its tier’s band, the generator tries sub-seeds in order, level:37#0, level:37#1 and so on, until one lands in the band. That keeps everything deterministic: level 37 is the same board on every phone, without storing a single board. A few timings from the real thing:

The times are from my laptop and vary with the device. There’s a cap of 2,000 sub-seeds, and the calibration suite checks it’s never reached for levels 1 to 400.

What I’d take to any generator

• Build the answer first. Generating and then checking almost never lands on a unique puzzle; shaping the puzzle around a known answer does.
• Kill the other solutions directly. Knowing why a move removes solutions (two castles in one realm) beats random changes and re-checking.
• Rate with a solver that thinks like the player. Uniqueness is a property of the board; difficulty is a property of the reasoning it needs.
• Use seeds and sub-seeds so endless content is reproducible, testable and free to store.

You can try it in your browser at moat.jonathas.net. The iPhone version is on its way to the App Store.