The 298 stages on this site were not drawn by hand. A generator produces candidate shapes, filters them, and names whatever survives. That raises an obvious problem immediately: what guarantees a generated board can be solved at all?
The answer is blunt. A board ships only after a solver has actually found a complete tour on it, and the test suite re-solves all 298 from scratch on every build. An unsolvable stage cannot be deployed.
The solver
It is a backtracking depth-first search, and the ordering is the whole trick. Among the squares you can reach, try the one with the fewest onward moves first. H. C. von Warnsdorff proposed this in 1823, and two centuries later it is still the best heuristic anyone has for this problem.
The intuition: squares with few ways in and out — corners above all — become stranded if you leave them for later, so deal with them while you still can. In code it is a single sort, and it is enough to solve most boards without ever backtracking.
Why the cheap filters run first
This search has a brutal asymmetry. Solvable boards finish fast; unsolvable ones burn the entire budget. If a tour exists, a lucky run ends after roughly as many nodes as there are squares. If none exists, proving that means exhausting essentially every arrangement. So candidates must pass a few cheap tests before the solver ever sees them.
- Parity — a knight changes square color every move, so a board whose two colors differ by more than one has no tour at all.
- Degree — no square may have zero onward moves, and at most two squares may have exactly one (those can only be the two ends of the path).
- Connectivity — every square must be reachable from every other by knight moves alone.
All three cost one pass over the board. A large share of candidates die here, which means these three checks account for most of the generator’s throughput.
Difficulty is not board size
Stages need to be ordered from easy to hard, and cell count turned out to be a terrible proxy. There are 100-cell boards that fall out in one Warnsdorff sweep, and 20-cell boards that need tens of thousands of backtracks.
So difficulty is measured as the number of search nodes the solver spent finding a tour. With no backtracking at all, that number sits near the cell count; the worse greedy intuition performs, the higher it climbs. Under 100 is easy, under 2,000 medium, under 50,000 hard, above that very hard. It tracks human difficulty surprisingly well.
The time I saved budget and lost two boards
In the Wrapped World chapter the left and right edges of the board are joined: step off the left edge and you come out on the right. What that chapter demanded of a candidate was not merely "solvable" but "solvable only if you use the wrap." If a board can be finished without ever crossing an edge, the whole rule is decoration.
So each candidate got two questions. Does it solve with the edges joined — must be yes. Does it also solve as an ordinary board — must be no. To save time on the second question I lowered the search budget to 300,000 nodes. These boards were supposed to be unsolvable anyway, I reasoned, so why look for long?
The test suite verifies with 2,000,000. It found ordinary solutions for two of them. The generator had read "not found within 300,000 nodes" as "does not exist," and two boards shipped in which the chapter’s rule meant nothing.
The lesson is one line: "the solver did not find one" is not "there isn’t one." When you are demonstrating existence you may economize — the moment you find it, you are done. When you are demonstrating absence, you may not. The filter went back to the full budget, and the test got a generous timeout instead.
What this does and does not guarantee
It guarantees exactly one thing: every stage has at least one complete tour. Not that it has only one. Most boards have many, which is why solving the same board twice rarely retraces the same path.
It also does not mean a human will find it easily. If the machine had to backtrack fifty thousand times, you are going to wander too.
Next: A 4×4 board has no knight’s tour — a proofStages