Sixty-four levels, none written by hand: how Millrace finds and proves its puzzles

A puzzle level is real when thinking is the only way through it. Checked by machine, that idea turns into a list of testable properties. Every one of the 64 levels in Millrace, a tile logic puzzle, was found by search, and none ships unless these hold:

1. It is solvable within its move limit.
2. Its shortest solution is known exactly. A breadth-first search walks the level’s states, and the first win it reaches is provably the minimum. The game calls that number the best possible; my own estimate plays no part.
3. Random play rarely wins it. A level that falls to random moves isn’t a puzzle, so the gate holds it back.

The 64 levels that pass sit in six chapters: Warm-up, which teaches the rules, then Tactics, Pressure, Precision, Deep Water, and Mastery.

Why greedy-friendly goals fail

A slide-and-merge board suggests obvious goals: clear the board down to a few tiles, or reach a tile of a certain size. Both make poor puzzles, and the reason is almost embarrassing once written down. A goal that a one-move greedy habit directly optimizes can’t be a puzzle. A player who grabs the most empty cells is pursuing the clearing goal; one who grabs the biggest tile is pursuing the reach goal. Thoughtless play wins them.

Delivery survives because it can be lost twice over. The target must rest on one marked cell, so the number has to end up exactly there. It must also be an exact value, so building past it (a 128 when the level asked for a 64) loses the goal for good. No local score approximates either condition. That is why Millrace has one kind of goal: build exactly N on the marked cell.

Why the arriving tiles are fixed in advance

The other half of the design is the arrival queue. Tiles enter one at a time at the arrival cell. If that cell is blocked when the next one is due, the run ends. That brings back the tension a slide-and-merge board depends on, because it fills while you merge.

Chance stays out. The queue is fixed, so every position is a pure function of the moves played. With random arrivals, “the shortest solution” isn’t a number, since it depends on tiles nobody has drawn, and a solver can only average over futures. With a fixed queue there is nothing to average, and breadth-first search is the exact model. On screen, the status line tells you how many tiles are still to arrive and which one is next.

How a candidate level is generated

The generator is simple, and the rigor sits in the gate. A candidate gets a starting board, a fixed queue, an arrival cell, a marked cell, and a target. The solver measures its shortest solution, and the candidate stays only if that solution exists within the move limit and the rest of the checks pass.

Thoughtless play has to fail

The test suite plays every level against random moves, and a level random play wins easily is gone. The point is to certify that the content has depth. The skill a level asks for is looking ahead: where will the next arrival land, and which merge should wait? How to plan moves ahead in Millrace shows that lookahead in play, with Level 1 worked move by move.

Why the gate lives in the test suite

The checks live in the test target and run every time, not once. The suite asserts each property over the shipped levels, so a level that stops passing fails the tests. Tare’s balance puzzles are made by hand, but a solver checks them in the same spirit; here is how it proves each level has exactly one answer.

The Hint inside a level runs the same solver, so the move it suggests always leads to a solution. For Chessful’s forty opponents, difficulty was a matter of character. Here it had to be a number the tests check.

What you see of it

Almost none of this is on screen.

• The result card says “Solved in N moves”, shows your best, and says “Best possible is X moves”, where X is the proven minimum.
• Hint draws a move on the board with a one-line reason, and in a level that move lies on a winning line.
• In chess, search depth is an engine setting, and more of it doesn’t help a club player. Here the shortest solution is a measured property of the board.

Millrace is free on iPhone and iPad; the app page has the rules and the privacy details. If a level ever feels impossible, somewhere in its states is a line exactly as long as the card says, and the tests have walked it.