Jon McGee
← All notes

· 3 min read

How Mainspring makes sure every puzzle has exactly one solution

How every Mainspring puzzle is built to have exactly one solution, and how the best possible score is calculated exactly instead of estimated.

Game developmentAlgorithmsPuzzle games

Mainspring is a swap puzzle. A grid of enamel gear plates starts scrambled, and you swap pairs of plates until every row and column holds each gear exactly once and every clue is satisfied. The stars you earn depend on how close you get to the shortest possible solution. For that to feel fair, two things have to be true: each board has exactly one answer, and the shortest solution is a number I know, not a guess.

One solution, every time

Each puzzle starts as a random valid grid. Then I remove clues one at a time, and after each removal a constraint solver checks that the solution is still unique. If removing a clue would allow a second answer, the clue stays. When the process finishes, every clue left on the board is necessary, which is why there is never a clue that exists only for decoration.

Par is calculated, not estimated

The shortest solution, which the game calls the Master’s best, comes from a little graph theory. Build a graph of the mismatches: every plate in the wrong place becomes a line from the gear it holds to the gear that belongs there. Those lines form cycles. The minimum number of swaps equals the number of wrong plates minus the maximum number of separate cycles you can find. I find that maximum with a memoized search, and I cross-checked it against a full breadth-first search. The two agree on all 1,680 possible 3 by 3 arrangements, and on more than a thousand 4 by 4 ones that can be solved within three swaps.

Difficulty by technique, not by search size

My first attempt at grading difficulty counted how many branches a brute-force solver explored. It turned out to have almost no range, so every puzzle looked about the same. I replaced it with a grade based on the technique a human would need: a single obvious gear, a hidden single, an arrow bound, a pair, or finally a careful guess. The four worlds in the campaign use those grades, and each world introduces a new kind of clue.

What testing taught me

  • The simple strategy of fixing the first wrong plate each time already reaches par on 32 of the 48 campaign puzzles. So three stars is mostly about working out the answer without wasted moves. I added a test floor so boards do not drift toward trivial.
  • The technique grade sets the difficulty range of each campaign world, which gave the four worlds a clear step up from one to the next.
  • Par tops out at 16 swaps on a 7 by 7 board, not the 18 I planned, because seven gear types split a scramble into many short cycles.

Behind all of this are 966 unit checks and a 58-step test that plays the real interface, including the tutorial and the Lens hint.

Play it

Mainspring is free and runs in your browser on the home page. The walkthrough page covers every clue type and mode.