Board and Logic Puzzles
Graph theory, constraint solving, and puzzle math
A Field Guide to Board and Logic Puzzles
Board games, paper-and-pencil puzzles, and reasoning games usually get filed as three genres, yet from a computer’s point of view they are one thing: the board is a graph, the puzzle is a set of constraints, and the win or the unique solution is a target on that graph or inside that system. This post brings together eight long-form articles: the graph-theoretic account of game difficulty and rule cores, Euler paths leading into Slitherlink and Hashi, one constraint solver unifying the logic-puzzle family, the mechanization of deduction, the bookkeeping art of six paper puzzles, Sudoku’s puzzle machine, and four mathematical tools inside 2048, Minesweeper, Lights Out, and the sliding puzzle. Every section has a playable version on the site; open one as you read.
Five Games, Five Kinds of Difficulty
There is a class of games that has barely changed in centuries: one board, a handful of pieces, one public rule set. They usually get filed under board and card games, but from a computer’s point of view they are all the same thing: a state graph plus a table of legal moves.
Seen this way, depth immediately splits into several unrelated sources: how big the state space is, whether information is complete, whether moves are reversible, whether a usable heuristic exists. Chess is hard because of branching, checkers because it has to be exhausted to the bottom, Sokoban because moves are irreversible, bridge because you cannot see the whole picture, and sliding puzzles because of one hidden invariant.
Formalising takes only three objects. A state , the complete description of the current position. Moves , the legal actions available from . A terminal test, the win, loss, or draw condition over some set of states.
Whether the state carries history is the key difference between chess and Sokoban. In chess you do not need to know how you got here; in Sokoban you must, because a box may already have been pushed somewhere it cannot come back from.
The table below is the skeleton for every subsection that follows.
| Game | State magnitude | Information | Reversible moves | Where the difficulty lies |
|---|---|---|---|---|
| Chess | positions, game tree | Perfect | Partial | Branching factor |
| Checkers | Perfect | Partial | Must be exhausted to the bottom | |
| Sokoban | Exponential, decision PSPACE-complete | Perfect | No | Deadlocks from irreversibility |
| Sliding puzzle | Perfect | Yes | Invariants restrict reachability | |
| Bridge | Hand combinations on the order of | Imperfect | No | Information must be bought with bids |
Chess, Turning Deep Calculation into Something Executable
The Shannon number is , the branching factor 35. Searching ten plies directly is nodes; no machine will ever finish that. So every technique in an engine is subtraction applied to the same search.
The first subtraction is minimax. Your moves take the maximum, the opponent’s take the minimum, recursively alternating. It translates “what should I play” into “assuming both sides play optimally, what is this position worth”. The second is alpha-beta pruning: once a branch can no longer affect the decision above it, the whole subtree is thrown away.
The demo above uses a complete binary tree of depth 4; the two sides show the node visit order without and with pruning. In theory, given an optimal move order, alpha-beta compresses the search from to — the same time, twice the depth. That is why move ordering is the most valuable engineering detail in an engine: try captures first, try the high-scoring entries from the transposition table first. Pruning efficiency depends entirely on whether you run into a good enough branch early.
The third subtraction is not really subtraction but substitution. Leaf nodes must be scored, and the standard recipe is material value plus piece-square tables: pawn 1, knight and bishop 3, rook 5, queen 9, with the same piece worth different amounts in the center and in a corner.
Evaluation always carries error, and error brings the horizon effect. The engine sees a good result at depth , cannot see the counter-blow at depth , and cheerfully walks into the trap. The engineering patch is quiescence search: keep expanding capture sequences at leaf nodes until the position goes quiet.
The site’s Chess bundles two-player, blitz, and human-versus-machine into one. The machine mode does not carry a whole engine around; it enumerates every legal move and picks the best one under a heuristic score. It only looks one ply ahead. The value of that sentence is that it gives you an honest yardstick: beat it and you are calculating two moves ahead; fail to beat it and your blunders are within one move. A lightweight implementation should not be dressed up as an AI opponent — it is closer to a sparring partner that never makes a beginner’s mistake.
Checkers, the One Proved by Exhaustion
Checkers has far simpler rules than chess: move diagonally, jump to capture, crown a king on the back rank. But simple is not small — the state space still holds , merely twenty-odd orders of magnitude below chess.
That magnitude happens to fall inside what humans can chew through by main force. In 2007 a Canadian team announced, with Chinook, that checkers is a draw when both sides play optimally. The weight of the result lies not in the program playing better than people, but in the complete solution of the entire state graph. Chinook took the US championship in 1990, inherited the 1994 world championship when its opponent withdrew for health reasons, and then spent another decade refuting the remaining branches one by one into draws.
The key to checkers being solvable is forced capture. Having to take means a large number of branches get cut away, and the branching factor sits far below chess. The price is depth: in many positions the optimal line needs twenty-plus moves before anything is decided. This also draws the line between exhaustion and heuristics — few branches and great depth suit exhaustion; many branches and shallow depth suit evaluation.
Sokoban, Where Irreversibility Is the Difficulty
Sokoban looks like a spatial puzzle but is in fact the theoretically hardest of these five: its decision problem is PSPACE-complete. That conclusion has to be understood precisely. It does not mean nobody has found a polynomial algorithm yet; it means that if one did exist, PSPACE would equal P and computational complexity theory would have to be rewritten wholesale. A general solution is not something to count on.
The mechanism behind the difficulty is irreversibility: boxes can only be pushed, never pulled. The state graph is directed, one wrong move cannot be undone by walking back, and you can only circle inside a bounded region. So a solver’s performance rests almost entirely on deadlock detection.
A box pushed into a corner, walls on two sides: permanent deadlock. Two boxes side by side against a wall, neither pushable: permanent deadlock. A box parked just outside a goal square looks like free space, yet it blocks another box’s only route — that is a spatial deadlock.
All of these judgments are local pattern matching: extremely cheap, enormously profitable. Cutting deadlock branches early in the search is faster than any heuristic.
Human players use another kit entirely. Work backwards from the goals and assign a goal to each box — that is a bipartite matching problem, solvable with the Hungarian algorithm to minimise total distance — then abstract walking around behind a box into a macro move.
The site’s Sokoban ships levels and hints only, with no built-in solver. That is not laziness. A solver has no value to the player; it is a tool for verifying that a level is solvable, and only the level-designing side needs it.
Sliding Puzzles, Where Half the Permutations Are Unsolvable
The Sliding Puzzle is the classic 15-puzzle shape: a 4×4 grid, 15 tiles, one blank. The state count looks like , but only half of it is actually reachable.
The test is two lines of arithmetic. Read every number except the blank row-major into a sequence and count the inversions. Then look at the parity of the blank’s row number counted from the bottom. Same parity means reachable, different means unreachable — leaving .
The invariant yields two immediate consequences. Shuffle a board at random and there is a fifty-fifty chance it is unsolvable — no amount of trying will get you there; it is not that you are bad, it is that mathematics forbids it. Pop two tiles out, swap them, put them back: physically perfectly doable, logically an unreachable state. Physical reversibility and logical reachability are two different things, and that is the loveliest part of invariant puzzles.
One common confusion, cleared up while we are here. The site also has Grid Games, which slices one image into nine 3×3 pieces in Z order so they stitch into a long image on social platforms — that is image slicing. Similar name, unrelated mechanism.
Bridge, a Compression Problem
The first four all have perfect information: you and your opponent see the same position, and the result depends only on who calculates deeper. Bridge breaks that premise. You see only your own 13 cards; the distribution of the other 39 has to be bought back bit by bit through bidding.
Start with the encoding. A hand’s strength is pressed into a single number by a four-tier point count: ace 4, king 3, queen 2, jack 1, forty points to a deck. Those 4-3-2-1 weights are not guesswork; they roughly match the actual trick contribution of each honour in double-dummy analysis. So “how strong is this hand” collapses from the shape of 13 cards into an integer between 0 and 37.
The bidding system is a decision tree grown on that scalar. Standard American Yellow Card opening logic can be written out as plain if-else: under 12 points, pass; 12 or more with a five-card major, bid 1H or 1S; no five-card major but a four-card minor, bid 1D or 1C; a balanced strong hand of 20 or more goes through the 2C strong opening. The site’s Bridge Bidding Trainer implements exactly this tree — it does not judge your card sense, only whether your opening sits inside the rule table.
So bridge’s difficulty is not in reasoning but in encoding. You and your partner share a codebook; each bid spends one call, about 4-5 bits, in exchange for part of the opponents’ shape. Bid more economically and you can ask more; bid more accurately and you are more likely to reach a contract before interference. In information-theoretic terms this is compressed transmission over a noisy channel, and the cost of memorising a system is the dictionary size of that code.
Flow Typing, Where the Opponent Is Entropy
One outlier that is not in the table, to close: Flow Typewriter. The rule is that once you stop, the text you have already typed begins to fade out and vanish. No opponent, no board, no terminal test.
Yet it is still a game of state plus a time budget — only the budget runs the other way, a negative time budget. In a normal game time is a resource and you spend it for score; here time is the enemy, and not producing means losing stock. Its design goal is to turn procrastination, an abstract problem, into a visible physical consequence. Writers get stuck because they keep revising the first sentence, so this mode simply removes the chance to go back and revise.
From game theory it degenerates into a single-player game. From behavior design it is a commitment device: voluntarily accept a constraint up front so that the future you cannot go back on it. Mechanisms like this are everywhere in real life — handing your phone to a friend, setting a non-refundable deadline, announcing a goal in public — all of them essentially installing a fade-out timer on yourself.
Practice splits along the same lines. To train calculation depth, solve tactics on Chess — one problem beats ten careless games. To train backward planning, work back from the goal squares in Sokoban. To train invariant thinking, count inversions in the Sliding Puzzle. To train information compression, bid a hand clean in the Bridge Bidding Trainer.
Reading the board as a graph shows where difficulty comes from. The next section flips to the rules themselves: the source code of four concrete board games contains not one line of “chess” — it is all graph.
Topology on the Board: Compiling Rules into Graphs
Read a board as a graph and the rules of board games explain themselves. Placing a stone adds a vertex to the graph, moving looks for a path on the graph, and deciding the winner asks about a graph property: connectivity, coverage, or a count of odd vertices. This section takes four board games on the site apart; their source contains not one line of “chess” — it is all adjacency lists, flood fill, and reachable sets. Read that graph skeleton correctly and the rulebook can be thrown away. Hands-on versions: Go, Hex, the Euler Path Challenge, Chinese Checkers.
The Board Is a Graph
A graph has two parts, and a board supplies both for free. Vertices are the positions a piece can occupy; edges are the “reachable in one step” relation. What’s left is geometry. Different boards are, at bottom, different adjacency structures.
Both the Go and Hex implementations on the site flatten the board into a one-dimensional array, indexed by , with neighbors enumerated by a function of the same shape:
function neighbors(i) { const [r, c] = rc(i); const out = []; if (r > 0) out.push(idx(r - 1, c)); // up if (r < N - 1) out.push(idx(r + 1, c)); // down if (c > 0) out.push(idx(r, c - 1)); // left if (c < N - 1) out.push(idx(r, c + 1)); // right return out;}Four boundary checks are the entire topology of a 9×9 square lattice.
Chinese checkers runs one notch harder. Its holes sit on a triangular grid, every interior point has six neighbors, Cartesian coordinates stop cooperating, and the source switches to cube coordinates. Each hole carries a triple under the constraint , and the six move directions are written .
Which triples count as legal holes? Two rules. If every component’s absolute value is at most 4, it’s the central hexagon. If one component falls between 5 and 8 while the other two lie in , it’s one of the six pointed arms.
Two rules assemble the standard star-shaped board of 121 holes. 61 in the central hexagon, 10 in each arm.
The Euler path challenge tears off the “board” skin altogether. No lattice, no pieces — vertices and edges drawn straight onto an SVG canvas. What the player faces is the graph itself. Probably the most honest of the four.
There’s one more correspondence that’s easy to miss: a board state evolves under local rules, and a change in one place affects only its neighbors. That makes boards and cellular automata close relatives.
The Game of Life and the wildfire model in the site’s Cellular Automata post run on exactly the same “lattice plus neighbors” skeleton. The only difference: a cellular automaton has no opponent, a board does.
Go’s Liberties
The most central concept in Go’s rules is the liberty. A block’s liberties are the empty points orthogonally adjacent to it.
Translated into graph theory, that’s a two-step compound operation. Find the same-color connected component, then count its boundary empty points.
The group function in the source squeezes both steps together. Starting from one stone, it spreads along same-colored stones with a stack-based depth-first search, collecting two things as it goes. All the stones of the connected block in cells, and every empty point bumped into along the way in libs:
function group(start, b) { const seen = new Set(), libs = new Set(), cells = []; const stack = [start]; while (stack.length) { const i = stack.pop(); if (seen.has(i)) continue; seen.add(i); cells.push(i); for (const n of neighbors(i)) { if (b[n] === "") libs.add(n); // empty point → liberty else if (b[n] === color && !seen.has(n)) stack.push(n); // same color → keep spreading } } return { cells, libs };}That’s flood fill. On each move the program runs group on every opposing block adjacent to the played point, and whichever has zero liberties disappears from the board whole.
Then the program runs it again on its own new block. If that also has no liberties and the move captured nothing, it’s suicide and ruled illegal.
A block left without a single liberty is, on the graph, a “fully severed connected component”. Its death needs no special code, only the boolean test libs.size === 0.
Ko
Ko is the most convoluted part of Go’s rules, and its implementation is unexpectedly plain.
The source remembers the position from before the previous move (joining the whole board array into a string as a hash), and before each move computes the hash of the candidate position. If the new position is identical to the one before the last move, the move is rejected on the spot.
In a ko fight, recapturing one stone restores the position exactly, so the hash gate blocks it.
The code carries one more marker, for single-ko forbidden points. When a move captures exactly one stone and the player’s own new block is that single stone, the point involved is flagged as forbidden.
Two layers of defense stacked together reduce full superko (a global ban on repeated positions) to “you may not immediately recreate the position from before the last move”. On a small 9×9 board, the simplification suffices.
The semantics of liberties also hide a piece of bookkeeping.
A lone stone has four liberties. Two adjacent same-colored stones join into one block, one of their eight boundary sides becomes an internal connection, and liberties shrink from eight to six.
In general, if stones form a tree-shaped block, there are exactly same-color adjacent pairs inside, each pair eating two potential liberties, so the bound is . Condense the stones into a solid mass and liberties grow with the perimeter instead, only on the order of .
Connection trades liberties for thickness. The block is harder to cut apart, but it has comparatively less room to breathe.
The other fundamental trade-off of Go, next to “better to lose several stones than to lose the initiative”, and one piece of grade-school arithmetic makes it visible.
Counting
Both sides pass, the game ends, and the counting begins.
The source’s scoring formula is: captures + stones alive on the board + empty points enclosed by a single color.
The third item is another flood fill. Fill each unclaimed empty region and look at which colors its boundary touches. Black only, and the whole region counts as Black’s territory. Both black and white, and it’s neutral (dame), counted for neither.
Both flood fills — life and death, territory — share the same neighbors function. That’s the entire size of Go’s adjudication logic.
On a 9×9 board all of it is verifiable by eye. A block’s life or death is whether its set of liberties gets wiped to zero. To “blockade” a stone is to occupy its boundary liberties one by one with your own stones. This is a cut on a graph, not mysticism.
One aside: the Go route on the site runs two tempos side by side. Standard mode sets no time limit. Blitz mode gives each move a 30-second countdown, and whoever overruns loses outright. The same graph engine under different time constraints is two different games.
Hex
Hex’s rules fit in one sentence: Red wants to connect its two sides into an unbroken band of its own stones, Blue wants the same, and whoever connects first wins.
The site’s implementation is a lattice, each row offset 16 pixels to the right of the one above, drawing out the slanted feel of a rhombus. Connectivity testing shares the trick with Go: BFS flood fill from every own stone already touching the starting edge, and see whether it spills over to the far side. Win or lose is one connectivity query.
But Hex holds a title that is mathematically rare among games: it is one of the very few games proven to be a first-player win while nobody knows how to win it.
The argument comes in two steps.
Step one, existence.
Hex is finite, perfect-information, and (on the classic hexagonal board) draw-free. Gale has a beautiful theorem: on a completely filled hexagonal board, exactly one side is connected — it’s impossible for both to be, or for neither.
The proof deserves a one-sentence sketch. Treat the filled board as a map in two colors and walk the border between them from end to end. That border is a one-dimensional path; it starts at a corner of the board and can only end at one of two specific corners. Where it ends uniquely decides which side’s two edges got connected.
That winding red-blue frontier is itself constructive evidence for “exactly one side wins”.
Three conditions in place, and Zermelo’s theorem guarantees that one of the two players has a winning strategy.
Step two, reductio ad absurdum. This is the famous strategy stealing, credited to Nash.
Suppose the second player has a winning strategy . The first player drops a stone anywhere, then announces: “from now on I’m the second player”, and plays by .
There’s only one problem. The cell demands at some step is already occupied by the first player’s “extra” stone. The fix: play somewhere else, anywhere.
The engine of the argument is Hex’s monotonicity: one extra own stone can never hurt. Stones never block their own path. Your connecting band needs the presence of your stones, not the absence of the opponent’s. The extra stone is at worst idle, and under no circumstances turns a winning position into a losing one.
So the first player, one stone to spare, executes a winning strategy and wins. Contradiction with the assumption that the second player had one.
The argument’s sharpness and its uselessness are the same thing. It proves a winning strategy exists and doesn’t tell you a single stone to place.
The position count on a 9×9 board is bounded by , and deciding the winner of an arbitrary generalized Hex position is PSPACE-complete. “First player wins” and “no computable winning move” have settled into a long standoff on this game.
The topology of the board tells you a winner must exist, and refuses to say who or how.
The AI in the site’s implementation is a three-layer greedy, a fitting everyday footnote to that incomputability.
It scans every empty point first; if one move connects, it plays there (tentatively placing, testing connectivity, retracting). Otherwise it blocks the opponent’s one-move winning point. If neither holds, it scores heuristically.
Each empty point counts its four neighbors: +2 for an adjacent own stone, +1 for an adjacent opponent stone, plus a center-preference term , so cells nearer the main diagonal score higher.
Win when you can win, block when you must block, otherwise go by feel. An honest three-act structure.
The route keeps a two-player mode as well, the same board with a person sitting across it. Whether the opponent is a program or a human, that pause of some two hundred milliseconds between turns is how one browser, within its means, pays respect to positions.
One implementation detail deserves a second look.
Classic Hex is built on hexagonal cells with six directions of flow. To fit the board into square coordinates, the site uses four-direction adjacency, shared by both players.
That change has consequences. In a world of squares plus four-adjacency, both sides can fill the board alternately and neither connects; the classic theorem no longer backstops.
The source honestly keeps the escape hatch: if the board fills with no one connected, it declares a draw outright.
“No draws” is not a property of the game’s name but of its adjacency structure. Which is the sort of detail you only see by reading the board as a graph.
The Euler Path Challenge
In 1736 Euler solved the Königsberg bridge problem, and out of that paper came two things: graph theory, and the criterion for drawing a figure in one stroke. The criterion hasn’t changed since: in a connected graph, 0 odd-degree vertices means an Eulerian circuit exists; exactly 2 means an Eulerian path exists and you must start at one odd vertex and finish at the other; anything else means it does not exist. Why exactly 0 and 2 gets a full treatment in the next section; here, watch it become a game mechanic.
The Euler Path Challenge turns that criterion into part of the game.
Challenge mode generates a random graph of 9 to 11 nodes per puzzle. First it lays a shuffled Hamiltonian path, which guarantees connectivity and gives every point a base degree. Then it scatters to random chords to thicken the graph.
The key step comes after. With roughly seventy percent probability the program pairs up the current odd-degree vertices two by two, adding one edge to each pair, forcibly repairing the graph’s odd count to 0 or 2. That pass guarantees most puzzles are solvable. The remaining thirty percent go out as-is, making “no Eulerian path exists” a real recognition question rather than a failure penalty.
The generator’s two branches match the two skills the player must train: drawing it, and recognizing that it can’t be drawn.
The badge on the interface states the verdict outright. “Eulerian circuit: any node may be the start”, “Eulerian path: must start at a, end at b” (with the required endpoints labeled), or “no Eulerian path exists”.
The test itself is astonishingly cheap: count the degrees once, .
But deciding existence and drawing the solution are two different things. Knowing which odd vertex to start from isn’t knowing which way to go at each step.
Hierholzer’s algorithm builds an Eulerian circuit in linear time, and Fleury’s cautious “never cross a bridge when you can avoid it” also constructs the tour edge by edge, except that bridge detection is another piece of graph work. The tool hands you the verdict and leaves the drawing to your hand.
The dead-end hint “edges remain untraveled” is worth translating into graph theory too.
The program’s standard for “stuck” is blunt: every edge of the current node is used up, while edges remain elsewhere in the graph.
In the language of Euler’s theorem there are only two possibilities. Either you crawled early into the vertex that should have been your finish, sealing yourself inside. Or you have lost contact with the remaining edges and are standing on an island.
Fleury’s advice — don’t cross a bridge — guards against the latter. A bridge is the graph’s only retreat; burn it and the undrawn remainder is stranded on the far bank for good.
The whole frustration of the one-stroke game is walking into those two dead ends over and over with ordinary moves. The only escape is to start at an odd vertex, and to keep a retreat open for the unwalked edges at every step.
Tap adjacent nodes to walk edges, walked edges turn green, the dead-end hint reads “edges remain untraveled”, and solved/attempted counts live in localStorage. Under that set of interactions sits mathematics fully solved nearly three hundred years ago, and a puzzle that still makes hands slip today.
Chinese Checkers
The Chinese Checkers route hosts three boards side by side.
The standard mode is the 121-hole star board described above, Red and Blue fielding ten pieces each in two opposite arms. The mini star is an isomorphic scaled-down version, six pieces per side. Western halma returns to an grid, with camps of six cells in two corners ( and its opposite) and movement in eight directions.
All three boards share one move engine, and that engine is a precise graph algorithm.
Move rules: a piece steps to an adjacent empty hole. Or it hops — over an adjacent piece (its own or the opponent’s, either works) — landing in the empty hole directly behind it. After a hop the landing point becomes the new launch point, and it can keep hopping.
The three boards differ only in adjacency density. On the star board every hole connects six ways; halma on a square grid adds the four diagonals to the four cardinal directions, making both steps and hops eight-way. The diagonals double the density of the hop network and stretch a turn’s theoretical reach accordingly.
The source computes “where can I get to this turn” wholesale with one BFS:
function gReach(src) { const set = new Set(), q = []; for (const t of step[src]) // single step: adjacent empty hole if (t >= 0 && occ[t] === null) set.add(t); const hops = (from) => step[from].forEach((land, d) => { const mid = step[from][d]; if (land >= 0 && occ[mid] !== null && occ[land] === null && !set.has(land)) { set.add(land); q.push(land); // hop: a piece to leap over, an empty landing } }); hops(src); while (q.length) hops(q.shift()!); // chained hops: each landing re-enters as a new launch point set.delete(src); return set;}(The version on the standard star board only swaps the six directions for the triangular grid’s six-neighbor adjacency; the logic is word for word the same.)
Note that only hop landings enter and leave the BFS queue. Single-step landings join the set but never the queue, which means one turn is “a step” or “a run of pure hops”, never a step followed by hops — exactly what the formal rules say.
The graph reading follows. Treat each empty hole as a vertex of an auxiliary graph, “can hop over some piece” as an edge, and a turn is a path of arbitrary length on that auxiliary graph.
Pieces are obstacles on the main graph and stepping stones on the auxiliary one. Your own stones build bridges, and the opponent’s lend a hand just as well. All of checkers’ interactivity hides on this “anything can be a springboard” kind of edge.
The win condition is a pure graph proposition: move every one of your pieces (ten or six) into the opposite arm or camp. One wholesale translation on the main graph.
And the AI’s evaluation function is a distance table.
Standard mode computes hexagonal distance in cube coordinates, . That’s the exact formula for the distance between two points on a triangular grid: take the absolute difference of the three components and divide by two, which divides out the coordinate system’s redundancy precisely.
Enumerate every reachable landing of every own piece and pick the move that lowers the distance the most. Blue’s target is pinned to the tip of the opposite arm, .
The mini star and halma use Euclidean distance to the target camp’s centroid. A heavy penalty for leaving camp (+500), a reward for entering (−40), and a tiny random jitter to break ties.
This is the humblest tier of board-game AI. No search, no opponent model, no opening book. Yet the BFS reachability closure over chained hops makes it surprisingly decent. One enumeration “sees” the endpoints of every hop chain, and the greedy, leaping toward the farthest, produces moves that look as though they were intended.
One Engine
Looking back, each of the four games adjudicates one graph property: Go’s life-and-death and territory are flood fill, a checkers turn is a reachability closure, and the one-stroke game’s entire fate is written in the parity of degrees. The board gives board-game rules a single compilation target: every game compiles to a graph first, then runs.
Every AI in this section looks exactly one move ahead. Swapping them for search that expands the game tree — minimax, alpha-beta pruning, Monte Carlo tree search, and which position each suits — is the subject of Games and AI Opponents. The question there isn’t “what does the graph look like” but “how many plies down the tree is it worth looking”. Together the two posts are a two-layer anatomy of board-game programs: the topology layer owns rules and adjudication, the search layer owns decisions.
The four adjudications share one more temperament: the rules are local, the verdicts are global. Go’s liberties look only at adjacent points, yet life and death is a property of the whole block. The one-stroke game’s degrees are countable point by point, yet whether a one-stroke tour exists is a property of the whole graph. A checkers hop happens only among three adjacent cells, yet a turn’s reachable set can span the board. The gulf between local rules and global properties is exactly why flood fill and BFS exist — they are the bridges that push local information outward, layer by layer, into a global verdict. Board-game rules fit on one page and play out bottomless, and the reason hides in that gulf.
The one-stroke game is the most special of the four: its criterion was fully settled three hundred years ago, and it has since grown two popular puzzles, Slitherlink and Hashi. The next section lays that theorem out in full.
Euler Paths: From Seven Bridges to Slitherlink and Hashi
In 1736 Euler took on a seemingly dull piece of municipal business: Königsberg had four landmasses and seven bridges, and the citizens wanted to know whether a stroll could cross every bridge once without repeating any. Euler’s answer ruled that walking route out, and invented graph theory on the side. Shrink the landmasses to points, draw the bridges as lines, and the question turns from a geography problem into a one-stroke decision on a graph. Nearly three hundred years later that decision still lives inside two popular pencil puzzles: Slitherlink has you draw a closed one-stroke loop by hand, and Hashi has you reconnect an archipelago into a graph according to degrees.
The Seven Bridges Problem
Let me put the conclusion out in full first.
In a graph, a path that traverses every edge exactly once is an Euler path (one that does not return to its start is an Euler path, one that does is an Euler circuit).
The test only needs two things.
Connectivity. Apart from isolated vertices, all edges form one whole. If the graph is not even connected, one stroke obviously cannot finish it.
The number of odd vertices. Vertices of odd degree must number 0 or 2. Zero odd vertices is equivalent to an Euler circuit existing. Exactly 2 is equivalent to an Euler path existing (and it must start at one odd vertex and end at the other). More than 2 and there is no solution.
The two criteria together are the necessary and sufficient condition: connected + at most 2 odd vertices.
The weight of this condition is that both ends are solid. Fail it and the drawing is impossible (no luck involved); satisfy it and the drawing is possible (no inspiration required). It compresses an operation that looks like it depends on ingenuity into two counting passes.
The intuition for necessity takes one sentence: every time a one-stroke path passes through an intermediate vertex it goes in once and out once, spending two degrees.
So apart from the start and the end, every vertex’s degree must come in pairs. If start and end are the same (a circuit), every vertex’s degree must be even.
The four Königsberg landmasses have vertex degrees 3, 3, 3, 5. Four odd vertices, so the walking route does not exist mathematically, no matter how clever the route.
A small theorem that speeds up the test, while we are at it: the number of odd vertices in any graph is always even.
That is the handshaking lemma. The sum of all vertex degrees equals twice the number of edges (each edge contributes exactly one degree at each end), so the total is even, and the degree sum of an odd number of odd vertices cannot land in the evens.
This conservation law of odd vertices coming in pairs saves effort when testing. Count one odd vertex and a second must exist; count three and a fourth must exist.
It is also the instant-kill move on many one-stroke brainteasers. For “can this figure be drawn in one stroke”, scan the odd vertices first; three or more and it is condemned without a closer look at the figure.
There is one often-misunderstood detail about that abstract Königsberg graph worth clearing up. Euler’s original 1736 paper actually contains no such famous point-and-line drawing. He used letters and tables to enumerate the combinations of landmasses and bridges; today’s Euler diagram illustrations were added later by others working from his idea.
The detail only sharpens the weight of that step of abstraction. Even the act of drawing it as a graph was added later because it felt handy; what was really invented was the thinking that translates a geographic problem into combinatorial relations.
What puzzle players do every day on dot grids and island clusters is, at bottom, standing downstream of that translation.
Sufficiency is less obvious (“if odd vertices do not exceed 2, can it really always be drawn in one stroke?”), and the proof comes from an algorithm. That is more convincing than any constructive argument.
Hierholzer’s Algorithm
Existence is settled; now you have to walk it out.
The core observation of Hierholzer’s algorithm: splicing several loops together at a shared vertex is still a one-stroke drawing.
The procedure:
function euler(start): stack = [start], path = [] while stack is not empty: v = top of stack if v still has an unwalked edge (v, u): cross out that edge, stack.push(u) else: path.push(stack.pop()) # v has nowhere left to go path.reverse() gives an Euler pathIt first walks greedily along whatever edges the current position offers until there are none, then pops the stack and records an entry. The fragments recorded on pop are exactly loops, and after reversal and splicing they form the complete answer.
Each edge is pushed and popped exactly once, so the complexity is . Existence testing (counting odd vertices) plus construction (Hierholzer) presses the one-stroke problem from decision to solution into linear time.
When Odd Vertices Overshoot
The real world will not cancel your snow-plowing duty because your graph has too many odd vertices, so the decision problem upgrades to an optimization problem.
Allow repeated edges, minimize total repeated distance. That is the Chinese postman problem (posed by Guan Meigu in 1962, hence the name).
Its solution loops elegantly back to Euler. Repeating an edge is equivalent to adding edges to the graph, and the goal of the additions is to make every odd vertex even. Each odd vertex needs an odd number of extra degrees, and the minimal plan is to pair the odd vertices up and connect each pair along the shortest distance between them, which in the general dense case reduces to minimum-weight perfect matching (polynomially solvable).
Once the matching is done all vertex degrees are even, an Euler circuit exists, and Hierholzer takes the stage to walk the whole graph.
So the complete recipe for a snowplow route: find the odd vertices, pair and add edges, draw in one stroke.
The Euler test handles whether it can be done; the postman handles topping it up to done at minimum cost. A decision theorem and an optimization algorithm joined head to tail — a rare clean relay in graph theory.
This combination of cheap to decide and cheap to construct takes jobs everywhere. Road snow removal and garbage-truck routes want every street swept without repeats, circuit-board drills want the shortest idle travel, and DNA sequencing’s fragment assembly is modeled as an Euler path on a read-overlap graph. The same 1736 answer, clocking in across industries.
The DNA case deserves half a sentence more. Stitching the thousands of short reads a sequencer spits out into a complete genome is, in the overlap-graph view, “find a path that crosses every edge exactly once”. Modern sequencing algorithms dodge Hamiltonian paths (NP-hard) in favor of Euler paths (linear time), and it was exactly this change of problem that turned whole-genome sequencing from an academic gamble into routine work.
A three-hundred-year-old walking problem is solved thousands of times a minute inside sequencers today.
Slitherlink
The Slitherlink board is a dot grid, and the numbers 0 to 3 in the cells give how many of that cell’s four edges the loop occupies. The task is to draw one closed loop along the grid’s edges.
Euler is not an analogy here but the direct core of the rules: a loop is an Euler circuit by nature. It crosses each edge it uses exactly once, and every point it touches is entered once and left once.
The one-stroke constraint you must obey while drawing — “at each junction there can be only 0 or 2 line ends” — needs no extra attention, because it comes bundled with the definition of a loop.
The designer’s cleverness is using the decision problem backwards. The one-stroke test tells you what kinds of figures can be drawn; Slitherlink makes you find, among the countless drawable figures, the one that also satisfies the number clues.
Because of that core, Slitherlink has a one-vote-veto self-check: a loose end mid-draw (a junction of degree 1), or an early closure (the loop closes before the clues are consumed), means the current reasoning contains an error. In other puzzles a mistake waits for the checker; in Slitherlink the geometry gives it away on the spot.
So all solving reasoning happens on the conjunction of number clues and degree constraints. A few of the sharpest propagation rules.
The zero lockdown. All four edges of a cell containing 0 are empty. It is the strongest single-cell propagation, and often the breaking point of the board.
3 against 0. A 3 shares an edge with a 0. The shared edge must be empty because of the 0, spending the 3’s “exactly one empty edge” quota, so the other three edges are all forced solid. Two rules interlocking, four edges pinned at once.
A 3 in the corner. A 3 against the board’s corner has its two bordering edges solid. If either were empty, the corner vertex would be left with one solid edge, degree 1, violating the loop constraint.
The reasoning is worth savoring. It uses no rule beyond the number information; it is purely the specialization of “every vertex has degree 0 or 2” at a geometric corner.
Vertex degree as a global propagator. Whenever a vertex already has two solid edges, its remaining incident edges immediately go empty. With two empty edges already in place, pressing one more empty edge forces all the remaining solid edges solid.
These degree cap and floor checks have to rescan the whole board after every step. Human players scan with their eyes, solvers scan with a loop; the rules are the same.
How the patterns cooperate also matters.
The power of a 3 is not confined to its own cell. If one of a 3’s two adjacent outer edges is eliminated by another pattern, the other three immediately go solid. The number gives an equality constraint of “exactly three”, and any change on either side triggers a full re-solve of the cell.
That gives a skilled player a scan order. Sweep the 0s first (free lockdown), then the 3s in corners and on edges (where geometry tightens the equality automatically), and only then touch the 1s and 2s (loosest constraints, usually waiting to be fed by earlier reasoning).
The tightness ordering of constraints determines the scan order of reasoning. That experience holds for every constraint puzzle; Slitherlink merely performs it most plainly.
A deeper weapon than these patterns is parity.
A loop divides the plane into inside and outside, and going from outside the board to outside the board must cross the loop an even number of times.
So whether a hypothetical edge is really solid can be tested by “leaving the outside, going around, and coming back: how many times did I cross this edge”. This is the rigorous version of the human inside-outside intuition.
Slitherlink therefore has a charming double identity: it is an existence game for Euler circuits and a training ground for planar duality.
When the patterns stall, the human player still has assuming, which is depth-first search in manual mode.
Pick a branch edge, assume it solid, and push all subsequent reasoning (propagation) through. A contradiction flips it (the edge is empty); a completed board and you are done.
This corresponds word for word to a solver’s propagate + backtrack, except the human has to maintain an undo stack in their head.
Slitherlink is one of the few puzzles where assumption can be strictly checked. The loop constraint’s “every vertex has degree 0 or 2” is sharp enough that a wrong assumption usually detonates a vertex of degree 1 or 3 within a few steps, unlike some puzzles that only reveal the answer at the end. Fast error feedback is its extra kindness to reasoning players.
A word on the generator side. The site’s Slitherlink supports several sizes and ships a checker, and board generation still takes the old road of build a solution, then verify uniqueness.
Draw a legal loop first, then invert the clue derivation to get numbers, and verify cell by cell that the puzzle has a unique solution.
The generator also faces a choice peculiar to Slitherlink: how dense the clues should be.
For the same solution, marking every cell makes the reasoning trivial and dull. Removing clues raises difficulty, but remove too aggressively and you get a dead board whose clue combination yields no unique solution, and you have to back off and re-carve.
This shares its genesis with the no-guess board generation philosophy of Minesweeper in The Math in Four Puzzles: a puzzle’s quality ceiling is not on the solving side but in the uniqueness guarantee on the generation side.
Hashi
The rules of Hashi. The board is scattered with islands labeled 1 to 8, and the task is to connect islands in pairs with double or triple bridges (straight horizontal or vertical lines, up to three running side by side).
Each island’s bridge count must equal its number exactly. Bridges may not cross or pass over other islands. When finished, all islands form one connected graph.
Note that Hashi runs in the opposite direction from Euler paths. An Euler path is “the graph is given, find that edge sequence”. Hashi is “the degrees are given, reconstruct the graph”.
But the core tool Euler left behind is unchanged: degree.
The number on an island is, in graph language, the target degree of a vertex, and all the reasoning revolves around “how many degrees does each island still owe, and which neighbors can still pay”.
A few high-frequency patterns, all derivable from the two principles of degree plus connectivity.
An 8 must be full, a 6 on an edge must be full, a 4 in a corner must be full.
An island’s degree comes from four orthogonal directions, and the rules cap each direction at two bridges. So an island numbered 8 pulls two bridges in each of four directions and is full at once. An island numbered 6 on an edge (only three usable directions) pulls two in each of three, also full. An island numbered 4 in a corner (two directions left) pulls two in each of two.
Position limits the number of usable directions, the number gives the total, and whatever cannot be made up any other way must be executed in full.
1 does not connect to 1.
If two islands of degree 1 are connected, the component they form is sealed off from the world (each has spent its only quota), which violates whole-graph connectivity unless those are the only two islands on the board.
This negative rule does not tell you what to do, only what is forbidden. A first-class citizen of pruning.
The 3-1 diagonal pattern.
When a 3 and a 1 sit diagonally, the two directions of the 3 facing away from the 1 must each carry at least one bridge.
Intuition for the proof: if the 3 were empty in both of those directions, all its bridges would have to crowd into the two directions facing the 1, and the 1’s single bridge, whichever way it connects, would force an unavoidable crossing or blockage somewhere.
Veteran Hashi players recite it as a mnemonic; at bottom it is a joint propagation of degree budget and planar non-crossing.
The deepest reasoning in Hashi comes from actively using connectivity.
At any moment, contract the islands already joined into a supernode and ask which exits that supernode still has.
If an island group has only one outward bridge slot left, that slot must be used. If the remaining slots of some group of islands split the board in two while either half still contains islands, certain connections are immediately excluded.
This is cut-set thinking from graph theory, and implementations usually bring out union-find. Every bridge placed merges the two ends into one set; whether everything is connected becomes a single query, and “this slot cannot be placed” can be a reverse test — place it and the other half of the island group is isolated forever.
The site’s Hashi ships a checker for the backstop, and all the fun of reasoning happens before a bridge goes down.
Hashi has one habit, symmetric to Slitherlink’s, worth naming: elimination is not an assistant here, it is the main force.
Every candidate bridge excluded by 1-does-not-connect-to-1 removes one usable direction from the relevant island, tightening its degree quota. Pair that with the positive conclusion “this direction is full” and the two forces squeeze the board back and forth; most boards roll through without any assumption at all.
This two-way squeeze of positive quota plus negative elimination is the shared reasoning grammar of all build-a-graph-from-degrees puzzles: Hashi, degree-view vertex analysis in Slitherlink, even circuit netlist analysis.
A coincidence of vocabulary is also worth savoring.
In graph theory, an edge whose removal disconnects the graph is a cut edge, also called a bridge. Same name as the bridges over water in Hashi, different object.
But at the top layer of solving, the two bridges meet. A bridge structure placed early can constitute a cut edge in the graph sense. Once it exists, the internal quota and outward exits of the island groups on either side are locked by it exclusively, and all later reasoning has to proceed under the premise that this connection is irrevocable.
The puzzle’s name comes from the surface; deep in the reasoning you collide with the same concept of connectivity. Moments where the name is a coincidence and the mathematics is inevitable are the particular romance of graph-theory puzzles.
Put the two puzzles back side by side inside Euler’s frame and the comparison becomes clear. Slitherlink selects edges on a fixed grid graph, and the selected subgraph must have all-even degrees and be connected (a loop). Hashi selects edges on an invisible complete graph, and the selected subgraph must match degrees point by point and be connected (a spanning subgraph). One has the fingerprint even, the other the fingerprint quota. Yet the solving experience is strikingly isomorphic: both start from necessary conclusions (propagation) and only assume (backtrack) when stuck, and both hide their deepest pleasure in the plainest word of all, connectivity. The follow-the-wall mnemonic Slitherlink players use (the short runs of confirmed solid edges must eventually close into loops, and a run blocked at both ends is a contradiction) and the quota squeeze Hashi players use are two dialects of the same propagation principle.
Degree is a hard constraint handed down by the graph, but the logic-puzzle family has members of far more disparate appearance that share a deeper structure: every cell has exactly two fates, and the rules are all relations that must hold between cells. Precisely the standard shape of a constraint satisfaction problem.
One Solver to Unify the Logic Puzzles
The pencil-and-paper puzzle family has members of wildly different appearance. Nonograms use row and column numbers to hint which cells to fill, Hitori asks you to black out duplicate numbers, Akari has you place lights in rooms to illuminate every corner, and Nurikabe requires the black cells to connect into one mass without ever squaring off.
At first glance the rules share no kinship, yet they share one deep structure: every cell has exactly two fates, and all the rules are relations that must hold between cells. Precisely the standard shape of a constraint satisfaction problem (CSP).
Once unified into a model, the four puzzles can all be eaten by the same solver. And the solver’s skeleton has only two moves: propagation (pushing the certain conclusions all the way) and backtracking (guessing when propagation stalls).
The site’s four boards each pick one: Nonogram, Hitori, Akari, Nurikabe. Sudoku is the family’s most famous member, and the modeling approach carries straight over; how machines generate puzzles was covered in The Two Sides of Sudoku, while this section focuses on the four-in-one modeling and solving.
CSP
Formalization takes only three words.
Variables: each cell is a variable.
Domains: the values a variable can take. In pencil-and-paper puzzles this is almost uniformly the binary domain {black, white} (or equivalently {light, empty}, {struck, kept}).
Constraints: the rules translated into which combinations of variable assignments are forbidden.
A solution assigns every variable without violating any constraint. The core promise of puzzle design is that exactly one solution exists. A unique solution is what makes reasoning possible, giving every deduction step a single correct destination.
This viewpoint immediately pays one dividend: “playing well” and “solving well” part ways.
Humans play puzzles via learned patterns and intuition, the human-friendly version of constraint propagation. Machines solve puzzles via the same propagation plus untiring backtracking.
The four puzzles’ rules vary wildly, but translated into CSP the only remaining difference is what the constraints look like. And that is exactly the framework’s value: swap the puzzle without swapping the solver, only the constraint encoding changes.
Modeling the Four Puzzles
Nonogram
Nonogram’s variables are each cell’s black/white, but the constraints are not adjacency — they are the run structure of whole rows and columns.
A row’s left-side clue [2, 1, 3] means that row contains, left to right, three runs of consecutive black cells of lengths 2, 1, 3, with at least one white cell between runs.
This arrangement-type constraint cannot be decomposed into simple pairwise per-cell rules; the standard treatment is within-row enumeration. Given the clue [2, 1, 3] and the row width, all black/white layouts satisfying the run structure can be listed exhaustively (or counted with DP).
For a given row, compare the currently fixed cells against every legal layout. Cells that are black in all legal layouts must be black; white in all, must be white.
A puzzle with a dozen-odd cells per row usually has only a handful of legal layouts, and one sweep pins several cells down.
Nonogram is therefore one of the puzzles with the strongest propagation power. Almost every new piece of information shrinks some rows’ legal-layout sets, and the shrinkage feeds back into the crossing columns.
Row enumeration itself need not be brute force. Read the clue sequence as run-length encoding, and “generate the k-th run starting at position i” forms a recursive structure. fits(i, k) means “all ways to lay the runs from k through the last starting at cell i”.
Recurse over each feasible start, and a 2D memo table (position × run index) compresses an exponential number of arrangements into polynomial time. Dynamic programming in its plainest form: the state’s two axes are which cell we have reached and which runs are used.
Run clues also yield some search-free hard facts. A run of 8 in a width-10 row must cover cells 3 through 8 no matter where it sits. Overlaps of long runs are the human player’s favorite one-bite deduction, and in implementation that equals a bitwise AND over all legal layouts.
Hitori
Hitori’s board is filled with numbers, and the player blacks out some cells. Three rules.
In every row and column, the remaining white cells must not repeat a number. Black cells must not be orthogonally adjacent. All white cells must be connected.
Modeled, it is the entanglement of three constraint classes.
Non-repetition is a pairwise constraint (same-number white cell pairs in the same row or column, at least one must be black). Black non-adjacency is another batch of pairwise constraints (adjacent cells, at most one black). White connectivity is the most annoying global constraint: it belongs to no pair of cells and can only be checked board-wide.
Hitori’s solving patterns derive almost entirely from the first two families. If a number is flanked by a third of the same number, the middle one must be white. Among cross-adjacent same-number cells, the center must be black.
The third family’s connectivity usually only backstops the endgame. This structural ordering of priorities maps directly onto human players’ operating order: resolve crosses first, then look for islands.
Akari
Akari (the site’s localized name for it is Light Up, no relation to Lights Out, the algebraic puzzle of flipping switches) requires placing lights in white cells.
Every white cell must be lit by at least one light (along row and column lines, blocked by black cells). No two lights may see each other. Numbered black cells demand exactly that many orthogonally adjacent lights.
In the CSP view it has a beautiful dual structure: the exclusion constraint says each unobstructed line segment carries at most one light, and the coverage constraint says each white cell’s row segment or column segment carries at least one light. One forbids too many, the other forbids too few.
Numbered black cells are exact-count constraints.
The propagation rules for light cells and lit cells are therefore unusually sharp in all three directions. A black cell numbered 0 forces all four neighbors white for safety. A not-yet-lit white cell whose only possible lighting source is itself must be a light.
Pulling the segments out enables one more step. Each horizontal or vertical run of unobstructed white cells is an atomic unit; lights can only sit on segments. And a white cell is exactly the intersection of one row segment and one column segment.
So “light every white cell” equals “cover every intersection via its row segment or column segment”, and “no two lights see each other” equals “each segment chosen at most once”. That is nearly a textbook description of a covering problem.
The phenomenon of a classic combinatorial optimization problem standing behind the puzzle is no one-off. It explains why pencil-and-paper puzzle deductions always fit airtight: good puzzle rules are often just the rules of some classical mathematical structure, dressed in rooms and lightbulbs.
Nurikabe
Nurikabe’s rules.
Each number declares the size of an island of white cells; each island contains exactly one number; islands may not touch orthogonally. All black cells must be connected. Black cells may form no 2×2 block.
Of the four, it carries the heaviest global constraints: black connectivity, island isolation, island size, no 2×2 — four constraint families active at once.
The site’s Nurikabe packs this entanglement into a 5×5 board that takes a minute to pick up. The small board is not a simplification; it lets the core tension of “island size is constraint” show more clearly. For an island numbered 4 with three white cells already confirmed, the location of the fourth white cell becomes a strong propagation point.
Its high-frequency deductions deserve listing too, because both carry the flavor of two mutually exclusive possibilities.
An island numbered 1 must have all four neighbors black (islands may not expand). But if one of those neighbors is simultaneously a member of another island, the two rules collide on the spot, ruling out one connectivity plan for you.
The 2×2 constraint is the coldest local veto. Any L-shape of three black cells forces the fourth cell white. Even if that cell belongs to some not-yet-complete island, the conflict of the two rules travels down the propagation chain, forcing earlier assumptions to flip.
The combination of local veto and global conservation is exactly where Nurikabe’s reasoning depth comes from.
Laying the four models side by side, the commonality shouts louder than the differences: the variables are all 0/1; only the constraints’ shapes differ.
Nonogram’s constraints are arrangement-type, Hitori’s and Akari’s main force is pairwise, Nurikabe carries a pile of global types. This difference will directly determine each puzzle’s difficulty ranking at solve time.
The Propagation-Backtracking Framework
Once unified into a model, the solver is barely a dozen lines:
function solve(assignment): if any variable violates a constraint: return failure if all variables assigned: return success (record solution) propagate to fixpoint: repeat for each constraint: use known variables to shrink other variables' domains until no domain shrinks any further if any domain is empty: return failure pick an unassigned variable v (fewest candidates first) for each candidate value of v: if solve(assignment + {v: value}) succeeds: return success return failureThree parts, three jobs.
Propagation is the synonym of reasoning. Use partial assignments to repeatedly shrink the undecided variables’ domains until no new conclusion can be drawn. Nonogram’s “intersect all legal layouts”, Hitori’s cross patterns, Akari’s “the only possible light source must be a light” are all propagation rules on particular constraints.
Propagation is safe: it draws only necessary conclusions, never guesses.
Backtracking is the fallback when reasoning runs dry. Pick a variable, try a value, walk in and keep propagating; on failure, undo and retry.
Variable ordering (MRV, minimum remaining values first) is the highest-value optimization. Guess the variable with the fewest candidates first; wrong branches die fast and pruning comes early.
At the implementation level sits one unglamorous but performance-deciding component: the propagation queue.
Each assignment requires re-scanning only the affected constraints. Put “which constraints might still yield something new” in a queue, pop and process in turn, enqueue newly affected constraints as processing produces new shrinkages, and the fixpoint is reached when the queue empties.
The queue-less approach re-scans all constraints indiscriminately each round. Same conclusions, at a constant-factor waste.
Among the four puzzles Nonogram has the fewest constraints (rows plus columns, 2n in total) and Nurikabe the most (connectivity and 2×2 checks number countless board-wide), so queueing’s payoff differs completely. The same framework’s performance profile across puzzles is decided by the constraints’ number and shape.
This framework’s division of labor has one property worth singling out: propagation and backtracking have entirely different cost structures.
Propagation is polynomial, its conclusions certain. Backtracking is exponential, its conclusions hypothetical.
So a widely used criterion for whether a puzzle suits humans is: can pure propagation, zero backtracking, solve it.
If yes, every human step has grounds. Boards that need deep backtracking are, for humans, continuous blind guessing. Generated puzzles that skip this check degrade reasoning games into luck games.
Propagation Strength Has Gears
Propagation itself has gear settings, and choosing one is a classic engineering trade-off.
The lowest gear is forward checking. A variable just got assigned, so check only the constraints it directly participates in and delete the immediately conflicting values from the neighbors’ domains. Cheap, but half the information is wasted (the neighbors’ shrinkages do not propagate further).
The middle gear runs the propagation loop to fixpoint. Every shrinkage triggers re-scanning until nothing more can be pushed. Costlier, far more conclusions; pencil-and-paper puzzles basically all get this gear.
The highest is full arc-consistency maintenance (the AC-3 algorithm, say). At any moment, for either end of any constraint, every value of one side must have a partner on the other, or it is deleted. Theoretically the cleanest, but the queue-maintenance overhead is often not worth it in the small-domain world of 0/1 puzzles.
The common answer for puzzle solvers is to start in the middle gear and upgrade on demand: run the cheap fixpoint loop first, consider stronger propagation once backtracking runs deep. Propagation strength is one more adjustable gear, and how far to turn it depends on how often backtracking appears.
Propagation to Fixpoint
Walk the propagation chain with Hitori’s classic triple pattern to feel what two rules meshing means.
Say some row has three consecutive cells all showing 4: [4, 4, 4].
The non-repetition constraint says at most one of these three white cells can remain, so at least two must go black. The black non-adjacency constraint says black cells cannot touch. Picking two mutually non-adjacent cells among three consecutive ones has exactly one solution: black the ends, keep the middle.
Each rule alone only offers loose talk of at most or at least; at their crossing point, one strike kills: the middle must be white, the two ends must be black.
And the chain does not stop. Once that middle 4 is confirmed white, all other 4s in its row and column must be blacked out for duplicating it. These new black cells then carry black non-adjacency to constrain their own neighbors.
One pattern fires, and the constraints roll outward like dominoes until some round of propagation draws no new conclusion. That is the literal meaning of propagation to fixpoint.
Akari’s counterpart is the unique light source. A white cell is not yet lit; scan its row segment and column segment and find that among all the places a light could go, only itself has not been ruled out. Then it must be a light.
Nonogram’s version is row-column intersection. In some row, all legal layouts paint the third cell black; in some column, all legal layouts paint the third cell white; the two pieces of information cross, and the contradiction immediately forces one side to recompute.
The three puzzles’ reasoning looks endlessly varied on the surface, but underneath it is all one thing: use the known to shrink the unknown, until some unknown has one candidate left.
Backtracking’s fallback deserves a demo too.
Late in a Hitori game, two cells’ fates are undecided (black or white) and propagation stalls. The solver tries black. Within three steps some region’s white cells get cut off by black cells, the connectivity constraint fails, roll back. Try white. The propagation chain rolls across the whole board in one breath.
In human post-mortems this is called the hypothetical method; in the program it is just two levels of depth-first recursion. The same action is cleverness when a human does it and enumeration when a machine does it, and the only difference is that the machine never forgets to undo.
Unique Solutions and the Puzzle-Generating Machine
The solver has a reverse use too: generating puzzles.
The flow: generate a complete finished board satisfying all rules, then dig holes step by step. Each time a portion is covered, call the solver to verify the remaining board still has a unique solution. The moment multiple solutions appear, revert that step.
This is the same machine as Sudoku generation. The Two Sides of Sudoku called it a solution counter, verifying uniqueness hole by hole.
All four puzzles’ generators take this road. The site’s Nonogram and Hitori boards, randomly generated, likewise rely on this step for playability. Nonogram even adds a difficulty knob (black-cell density): the higher the density, the tighter the row and column constraints and the more reasoning the solve demands.
The biggest chunk of generation cost is precisely the repeated solver calls: a puzzle’s difficulty is solved out, not set.
The solver can go one step further: quantify difficulty itself.
Run the solver over a puzzle with statistics on. Record how many propagation rounds, how many backtracks, how deep the deepest hypothesis chain. These counters are the objective readings of difficulty, far more reliable than “the author found it hard”.
The Sudoku community’s technique grading (this puzzle needs unique rectangles, that one needs chains) is essentially the same thing: define difficulty as the reasoning strength the solve requires.
Human difficulty grading leans on experts memorizing technique tables; machine grading leans on the solver emitting counters. When the two agree, it shows the technique table really does cover every shape propagation takes. In reverse, that is also a side door for validating the completeness of human solution methods.
Where Difficulty Comes From
Finally, answer the question planted at the opening: why do the four puzzles’ feel-based difficulty rankings roughly go Nonogram smoothest, Hitori in the middle, Akari one thought deeper, Nurikabe easiest to dead-end on?
The answer hides in the constraint shapes.
Nonogram’s run constraints carry strong propagation (one clue, one row of information), and row-column crossing forms natural linkage amplification.
Hitori’s pairwise constraints have many deterministic propagation rules, but global connectivity hides rework in the endgame.
Akari’s coverage-exclusion duality demands watching both too few and too many at once.
Nurikabe’s global constraints (connectivity, no 2×2) have the weakest propagation. Many conclusions only surface once the board is mostly settled, the propagation fixpoint arrives late, and backtracking, the hypothetical method, shows up often.
The more global the constraints, the blunter the propagation, and the more brain-burning the human experience of reasoning. This law also feeds back into puzzle design: to make a puzzle humane, lean on pairwise and arrangement-type constraints and depend less on global connectivity.
Back to the solver itself: two low-cost weapons deserve recording.
The first is the variable ordering mentioned above. Here the fail-first principle gets completed: pick the variable with fewest remaining values to guess first, so the node with the smallest branching factor gets processed first, and a wrong guess exposes the contradiction in the search tree’s shallow layers, cutting off whole subtrees rather than a few leaves.
The second is conflict learning. Each backtrack records the variable combination that caused the failure (the nogood), and isomorphic situations get pruned on sight. It fits the search with the memory of burned once, never burned again.
Neither changes the modeling itself, yet both often press the search volume down by an order of magnitude. The cost is a little bookkeeping time per decision, which may not pay off when boards are small and constraints simple. Pencil-and-paper puzzles rarely reach that critical point: after propagation to fixpoint, the cells that genuinely need guessing usually number in single digits, and the plain framework is the best buy.
One solver, four faces.
Before closing, widen the view one more notch: CSP variables need not be 0/1.
Sudoku’s variable domain has nine values, and its “no repeats in any row, column, or box” is an all-different constraint. A set of variables pairwise taking distinct values can be modeled as a bipartite matching problem and handled wholesale by the Hungarian algorithm, propagating faster and farther than a heap of pairwise ≠ constraints.
But the pencil-and-paper family’s collective preference for 0/1 domains is no accident: binary states make the physical act of filling cells the perfect carrier of constraints. Propagation can be executed with a pencil in hand; nine-valued systems have no corresponding bodily motion and only appear in the special case of Sudoku, where the numbers themselves serve as symbols.
From Nonogram to Nurikabe, from Sudoku to the Zebra Puzzle, constraint satisfaction is a unified substrate spanning every logic game. The next section’s Zebra Puzzle pushes this unification one step further: the clues swap cells for sentences, and the skeleton stays exactly the same.
Three Routes of Deductive Reasoning
One class of games advertises itself as needing no knowledge, only reasoning. The Zebra Puzzle hands you five houses and fourteen clues, Mastermind gives you ten guesses of black-and-white feedback, and Logic Puzzles gives you a run of shapes and numbers to find the pattern in.
What they share is that the solving process admits not one gram of legitimate inspiration. Every step is either necessary inference or a conclusion not yet due.
Taken apart, though, the three have completely different deductive structures. The Zebra Puzzle’s clues arrive all at once, Mastermind’s clues have to be bought one guess at a time, and the logic collection’s patterns are not guaranteed unique at all.
First, set the standard for the word deduction; this whole section uses it as a ruler. A piece of reasoning is deductive if and only if the conclusion is already hidden in the premises and the reasoning merely digs it out. Put otherwise, correct reasoning may not introduce any information beyond the premises.
By that measure, guessing, intuition, and getting a feel for it all fail. The qualifying moves are in fact quite limited: write the premises as explicit constraints, then work them over and over with two actions — contraction and case-splitting.
The three genres correspond to three different mixtures of these actions, and that is the roadmap for this section.
Einstein’s Riddle
The most popular version of the Zebra Puzzle carries the billing of “devised by Einstein, solvable by only 2% of people”. The site’s Einstein’s Riddle uses exactly that classic board: a row of five houses, each with five attributes — color, nationality, drink, cigarette, pet — with the five houses covering all five values in each category; fourteen clues such as “the green house is immediately to the right of the white house” and “the Old Gold smoker keeps snails”.
Legend and marketing aside, the fact is: the clues are complete, the solution is unique, and every clue is a strict proposition — this puzzle needs no step beyond mechanical reasoning.
It has been used as a teaching example repeatedly since the 1970s; the “2%” was always a slogan, never a statistic.
Formalize first. Five attribute categories with five values each is equivalent to a 5×5 Latin-square constraint system. Treat each category as a permutation from value to house number, and the puzzle is solving for five permutations at once.
Translate the fourteen clues one by one and all of them fall into four types.
Affirmative: “the Brit lives in the red house”. One attribute value is bound to another.
Negative: “the Dane doesn’t drink tea”. One binding is excluded.
Adjacency: “the man who keeps horses lives next door to the blue house”. The two values’ house numbers differ by exactly 1 in absolute value.
Ordering: “the green house is immediately to the right of the white house”. A comparison of house numbers, tighter than adjacency (the direction is fixed).
Four types map to four constraint operators, and that is the entire vocabulary. The puzzle’s language is small enough to list in one table, which is exactly why it suits mechanization.
The Human Method
The human “cross out the table” method deserves to be taken seriously, because it is constraint propagation in manual form.
Draw a 5×5×5 table (attribute × attribute × house number); every confirmed binding crosses out a whole row and column (the same value cannot live in two houses — the human version of the all-different constraint), and every excluded binding crosses one cell.
Cross out enough that a cell’s row has one slot left and that binding holds automatically. It is what Sudoku players call the “single candidate”; the two puzzles run on the same underlying reasoning.
Sweep the fourteen clues across the paper in turn, add the row contraction from all-different, and the vast majority of boards converge on the unique solution within two or three passes.
Take two opening moves on the classic board to feel the propagation chain.
Two anchor clues land first: “the Norwegian lives in the leftmost house” and “the man in the middle drinks milk”. House 1 and the drink “milk” are pinned on the spot.
Then “the Norwegian lives next door to the blue house” dyes house 2 blue. Now pair “the green house is immediately to the right of the white house” with “the green house’s owner drinks coffee”: the green-white pair cannot occupy (1, 2), since house 2 is blue, and the green house cannot land on 3, where milk is pinned and the green house’s owner drinks coffee. The candidates narrow in an instant to (3, 4) and (4, 5).
Four clues each saying their own piece, stacked, have already cut the color and drink arrangements nearly in half. Each clue alone is filler; combined they interlock layer on layer, and that “combination producing necessity” is the entire mechanism of the Zebra Puzzle.
The Machine Method
The most direct machine approach enumerates permutations by category.
Try a 5! permutation for the color category, then one for nationality. The upper bound is ; full enumeration is inelegant, but pruning collapses it immediately.
Two prunings matter. Run every given clue the moment each category is added (adjacency clues are not judged while a category is undetermined; clues involving it are suspended). And cut on prefix conflict: ordering and affirmative clues can chop whole swathes of permutations during a category’s prefix enumeration.
A reverse approach recurses by house number. Starting at house 1, try one five-tuple per house (a combination of color, nationality, drink, smoke, pet), testing adjacency clues between houses on the fly. The depth is only 5, and each level’s candidates are heavily compressed by the exclusions from earlier houses.
In engineering terms this solves in milliseconds. The more refined version wraps it in the general framework of constraint satisfaction problems (CSP), with the house number of each value as variables, domains 1 to 5, and the clues as propagators — the same ten-odd milliseconds.
Human and machine collide here: both sides are propagation plus search, only the human’s propagator is called a pattern and the machine’s a loop.
The site’s Einstein’s Riddle implements the classic fixed board (the version where the Norwegian drinks water and the Japanese keeps the zebra), with step-by-step hints and answer checking online. It is more a carefully equipped reasoning gym than a fresh random quiz.
A fixed board has an underrated benefit: the solution can be passed along by word of mouth. You can tell someone the chain you pinned down, which rarely holds for randomly generated puzzles.
A note on the generation side. Making a machine generate new Zebra Puzzles still runs the same three steps of constraint solving. Draw a complete solution at random (one random permutation per category), then generate candidate clues at random and test each one for whether the intersection of all clues determines exactly that solution. Delete redundant clues until deleting one more would give multiple solutions.
The minimal clue set is a natural scale for difficulty. Equally uniquely solvable, a board needing fourteen steps of reasoning and one needing twenty are two different grades.
That pipeline — solution, clues, uniqueness check — is the same machine as Sudoku generation and no-guess Minesweeper, filmed from a different angle.
Mastermind
The Zebra Puzzle’s clues are given; Mastermind’s have to be guessed.
The rules: a four-slot code is hidden from six colors (repeats allowed), and every guess returns feedback — how many are right color in the right slot (black pegs), how many are right color in the wrong slot (white pegs).
The site’s Mastermind implements exactly that: six colors, four slots, ten guesses at most, feedback shown peg by peg, and step-by-step undo for a post-mortem.
The problem shifts from solving a given constraint system to designing a sequence of clue purchases within a budget.
Candidate-Set Filtering
The skeleton of the deduction is still mechanical: the feedback to any guess cuts the candidate set down.
The initial candidates number . Guess 1122, get one black one white, and every candidate whose feedback under that assumption would not be one black one white is removed. The consistency filter runs once a round, and the candidate set shrinks monotonically.
As long as more than one candidate remains, keep buying information. After each feedback, filter first, then decide. That chassis is shared by every Mastermind solver; they differ only in what to guess next.
The filter has a counterintuitive property worth isolating: a guess does not need to possibly be the answer.
You can deliberately guess a combination you know cannot be the code (four of one color, say, when you are certain the code has no repeats), as long as its feedback splits the candidate set wide enough. It is a question, not an answer, and a sharper question is worth more than a closer answer.
Human players resist this almost by instinct, always feeling they should close in on the answer, while optimal play often slashes sideways in the first two rounds and only starts closing in on the third.
That crack between a deduction game’s intuition and its optimal strategy is the sharpest lesson Mastermind teaches.
Knuth’s Minimax
The strategy Donald Knuth published in 1977 remains the theoretical benchmark: each round, for every possible guess compute how large a candidate set it leaves in the worst case, and take the guess whose worst case is smallest.
That minimax choice guarantees a hit within five guesses whatever the code is. The 1296 candidates get sliced clean in five layers under minimax.
Intuitively it favors guesses with a wide information front. Opening with something like 1122, which carries repeats, spreads the feedback branches most evenly and minimizes the worst branch.
Later work replaced minimax with information entropy (pick the guess that on expectation splits the candidate set finest), shaving a few tenths off the average, but nothing simpler has replaced the elegance of the five-step ceiling.
The feedback itself has an algorithm worth unpacking.
Counting black pegs is trivial (compare slot by slot); counting white pegs is easy to get wrong. With repeated colors, right color in the wrong slot cannot be judged independently per slot.
The clean two-pass method: first count black pegs and strike each matched color from both sides. Then build a count table for the remaining guess colors and code colors, and white pegs is the sum over colors of the smaller count on each side.
Those few lines of arithmetic are the game’s physics engine. All the determinism of the feedback rests on them, and the information flow in Shannon’s sense is measured through them.
Six colors and four slots give only 14 possible feedback outcomes (of the 15 black-white combinations, 3 black 1 white cannot occur). One guess splits at most 14 branches, so bits is the information ceiling of a single guess.
Against bits of unknown, the theoretical lower bound is exactly three rounds. What sits between Knuth’s five steps and that bound is precisely the cost of uneven branching.
Put Mastermind back on the mechanization throughline and it supplies the link the Zebra Puzzle lacks: when clues are not free, the core decision of deduction shifts from how to derive to how to ask.
Every guess is both a probe and an experiment design. A good guess is not necessarily close to the answer; it is one that splits the space of possible worlds whatever the answer is.
That experimental-design view leads up to the information-theoretic bound of Twenty Questions and down to every algorithm in active learning.
The portability of this machinery also far exceeds the game itself. The numeric version — guess the number, be told how many digits are right and how many are right but misplaced (Bulls and Cows) — is the same machine with a different alphabet. The word-guessing hit of recent years swaps the candidate set for a dictionary and the feedback for green, yellow, gray; at bottom it is still filtering and splitting over 1296 candidates, and Knuth’s framework takes it in unchanged, with each candidate moved from a four-tuple to a word.
Change the object being guessed; keep the skeleton that splits possible worlds. That is the part of Mastermind far bigger than the phrase color-guessing game: it is the smallest complete model of active learning, choosing the experiment with the greatest expected information each round and narrowing the hypothesis space to one point in the fewest rounds.
Logic Puzzles
The first two share a faith in the unique solution.
Logic Puzzles turns the camera the other way: its five exercise types — analogies, numbers, sequences, figures, and spatial imagination — each ask what pattern the next item most resembles.
It looks like deduction, but strictly speaking it is induction.
The next term of 2, 4, 8, 16 is, logically, any number. Lagrange interpolation guarantees that any n known terms are threaded uniquely by some polynomial of degree n−1, so whether you want the next term to be 33 or 1024, a strict polynomial is standing by.
We answer 32 not by derivation but by Occam’s razor. Among all patterns that explain the known terms, the simplest one wins.
The rigorous version is Solomonoff induction: assign higher prior probability to shorter generating programs. Doubling is far shorter than some carefully built high-degree polynomial, so 32 wins.
Note that simplest never achieves mathematical uniqueness (Kolmogorov complexity is uncomputable); induction’s legitimacy is pragmatic, not theorem-grade.
This is not nitpicking but the watershed between the three games’ difficulties.
The Zebra Puzzle’s difficulty lies in clue-combination depth. Each clue alone is weak (ruling out one or two possibilities), and three or five must stack before a necessary conclusion appears; the stacking order and the memory burden are the difficulty. It tests working memory and the diligence of propagation.
Mastermind’s difficulty lies in the information-purchase strategy. The reasoning itself, filtering candidates, is mechanical; the hard part is what to ask at each step. It tests experimental design.
The logic collection’s difficulty lies in the size of the induction space. Candidate patterns are infinite, and simplest has no strict definition (Kolmogorov complexity is uncomputable). What the exercises really train is familiarity with common pattern families: arithmetic, geometric, Fibonacci, alternating, nested. They test a pattern library, not logic itself.
The five exercise types’ difficulty mechanisms deserve naming too, because the abilities they recruit are not the same.
Analogies test relational mapping (carrying the “A is to B” relation over to “C is to what”), and the difficulty is the abstraction level of the relation. Shape change is shallow; combined quantity and orientation relations are deep.
Sequences test pattern-family recognition, the difficulty being the induction space described above.
Figure reasoning tests visual operators such as rotation, symmetry, and superposition, a strong suit of human parallel processing.
Spatial imagination tests 3D unfolding and mental rotation, its difficulty climbing steeply with the number of degrees of freedom.
Four different muscles hang under the same logic signboard. That is also why some people glide through sequences and flounder on figures: not a difference in intelligence but in the distribution of their pattern library.
So using “logic” as the umbrella term does an injustice to the Zebra Puzzle and Mastermind. Those two are pure deduction; the logic collection is in fact the most dependent of the three on “having seen the world”.
The Difficulty Ledger of Three Genres
Condensed into one table:
| Game | Source of clues | Deductive core | Fulcrum of difficulty |
|---|---|---|---|
| Einstein’s Riddle | All 14 at once | Propagation (crossing out) + search | Depth of clue stacking and memory |
| Mastermind | Bought with each guess | Candidate filtering + minimax | Design of information purchases |
| Logic Puzzles | The prompt is everything | Induction (pattern-family matching) | Space of candidate patterns |
The ordering of training transfer among the three is clear. The logic collection trains the breadth of the pattern library, the widest transfer: reading comprehension and bad-smell detection in code review both feed on it. Mastermind trains designing experiments that buy the most information for the least money, which transfers straight to debugging (which log to add first, which stretch of code to bisect first). The Zebra Puzzle trains the rigorous execution of long reasoning chains, the narrowest transfer but the purest — nearly a standardized test of whether you can stay clear-headed through a ten-step derivation. Playing each of the three for a while is cheaper and more honest than any logical-thinking course.
One final test runs through all three: can someone else re-verify your reasoning step by step. Every step of the Zebra Puzzle can be told to a friend and picked apart one by one; every Mastermind guess can be asked “how big is this choice’s worst case”; the logic collection’s answers often only earn a “look again”, because an inductive conclusion has no derivation to show. Only reasoning that can be re-verified step by step deserves the name mechanization — which is also why formalization deserves to come before all cleverness: it does not make reasoning rigid, it makes reasoning discussable, correctable, and accumulable for the first time.
Beyond reasoning games, paper-and-pencil puzzles push mechanization further still: the rules are few enough to explain in a minute, yet a unique solution is demanded, forcing you to work every rule to its limit.
The Bookkeeping Art of Six Paper Puzzles
Paper-and-pencil puzzles are a genre that pushes “rule economics” to the extreme. Each puzzle hands you only two or three rules yet demands a unique solution. The rules are few enough to explain in a minute, and uniqueness forces you to work every one of them to its limit.
So the human solving process becomes a craft of bookkeeping: no brute force, no luck, just a ledger of candidates that keeps narrowing until only one answer remains.
This section dissects the rule cores and solution skeletons of six classic paper-and-pencil puzzles; each one corresponds to a playable widget on the site, and the source code is authoritative for each widget’s judging details. Hands-on versions: Dominosa, Tents, Kakuro, Shisen-Sho, Pipe Mania, Dots and Boxes.
Domino Pairing
Dominosa’s board is a grid filled with digits, and the player has to cut the whole grid into non-overlapping two-cell dominoes. Click a cell and then an adjacent cell and the two join into one domino; click again to split them.
The classic rules hide one more constraint: each domino type may appear at most once.
A domino’s type is defined by the unordered pair of its two cells’ digits. The digits form 28 unordered pairs (doubles included); a board cuts into 8 dominoes, and those 8 must all differ.
The site widget ships four preset puzzles: two , two 20-cell rectangles, digits 0–6, with New Game, Next Puzzle and Check buttons.
The judging logic deserves a look of its own. The source’s check verifies coverage completeness only: placed dominoes equaling half the total cell count passes, with no check for duplicate dominoes. The widget accepts a wider answer space than the classic rules — “just cover it all” lights the green light too.
But anyone playing by the classic rules won’t stop there. The uniqueness constraint is this puzzle’s engine. Lenient judging, strict solving, and the fun loses not one bit. This is also the usual division of labor when paper puzzles go electronic: the machine handles coverage, the human handles rigor.
The core of the solution skeleton is a pairing ledger.
Watch it run on a mini-board: the first row is , the second .
A board has only three ways to be cut. All vertical gives , , . Top horizontal, bottom horizontal and a right vertical give , , . Left vertical plus two horizontals gives , , .
The first and the third both contain two s — a collision; strike them. Only the cut with top and bottom horizontal plus a right vertical gives three mutually distinct dominoes. Once the ledger has eliminated the duplicates, the solution surfaces on its own.
In practice the ledger rolls cell by cell. When a digit has only one unpaired instance left, its partner is uniquely determined. Once a domino type is booked, every cell combination that could reproduce it is voided, and the other domino type competing for those cells is promoted automatically.
Every line struck from the ledger shrinks the neighboring cells’ candidate sets. A paper player’s skill is entirely a matter of how diligently the ledger is kept.
The ledger can save a few more entries.
Corner cells are natural breach points. A corner digit has only two neighbors, so its pairing candidates halve by construction. If its two neighbors also carry the same digit, the ledger immediately records “this domino’s combination is fixed, direction pending” — direction undetermined but combination settled, which is enough to rule out that domino type elsewhere.
Doubles (, and the like) are another cheap entry. The digits 0–6 hold only 7 doubles, and reproducing a double requires adjacent equal digits on the board; such cells are scarce, so once one is booked a whole region can be struck out.
Run the sparsity math the other way. A cuts 8 dominoes, but there are 28 candidate types; the solution occupies only of the candidate set. The supply of constraints far exceeds demand — the arithmetic backing of a good puzzle’s “necessarily has a unique solution”.
The widget’s interactions stick to the bookkeeping logic as well. An occupied cell cannot take a second domino (degree capped at one per cell), and one more click dismantles a mistaken connection. An electronic ledger allows erasure, a paper one doesn’t — a perk of going digital.
From a graph-theory viewpoint the cut is a perfect matching on the grid graph, and a board alone admits 36 coverings. But “each type at most once” upgrades a plain matching problem into matching plus bookkeeping, and the ledger is the tool that compresses those dozens of coverings into a single line.
Tents
Tents has three rules.
Several trees are already planted on the board, and you must place the same number of tents in empty cells. Every tent must be orthogonally adjacent to its own tree (touching up, down, left or right). No two tents may be adjacent — note, the eight-neighborhood: not even diagonally.
The numbers at the head of each row and column give that row’s and that column’s tent total.
The site widget is four puzzles, each with exactly 6 trees and 6 tents; click an empty cell to place or remove, and the tent and tree counts sit permanently in the top bar.
One implementation detail deserves a pause. The real-time red-flag checks are only two: row or column counts mismatching, and tents touching each other. “Each tent must hug its own tree” has no independent runtime check; the final verdict closes on the preset unique solution.
The machine watches two ledgers for you (the row and column accounts, and the exclusion-zone account); the third, pairing tents with trees, you keep yourself.
This pinpoints exactly the division of labor that paper puzzles train: the fewer rules written down, the more implicit constraints the human must maintain.
The human solution skeleton has four steps.
Step one, count and close. When a row’s placed tents equal its clue, every remaining cell in that row is struck empty; same for columns. The row or column whose count account zeroes first “closes its doors” first.
Step two, forced cells. If the placeable cells around a tree are squeezed by the row and column counts and the exclusion zone down to a single one, the tent lands there, and that cell is simultaneously struck from the other trees’ candidates.
Trees and tents are essentially a perfect matching on a bipartite graph: each tree corresponds to one tent, each tent claims one tree, and necessity on one side of the matching infects the other.
Step three, exclusion propagation. Place a tent and its surrounding eight cells all become forbidden ground. This cascade often forces another tree’s unique placement outright, or compresses a row’s or column’s remaining placeable cells to exactly the remaining count.
Step four, cross-referencing the two ledgers. A row still owes one tent and a column still owes one tent; if the intersection of those two debts holds a single cell, that cell is the answer.
Four steps cycling round and round, each drawing a line through candidates. On a board a human never needs to “try”, only to keep accounts.
Counting has one global check worth doing at the start. The sum of row counts necessarily equals the sum of column counts, and both equal the number of trees. All four site puzzles have 6 trees, rows and columns totalling 6 each, so the three ledgers reconcile against one another; reconciling once up front catches the rookie mistake of misreading a row or a column.
There are two positional shortcuts as well. A corner tree has only two candidate cells, a non-corner edge tree only three, so their tents almost always land first. Conversely, if all of some tree’s candidate cells crowd into one row or one column, that tree’s tent immediately consumes one quota there, and the row and column accounts move together.
String these three shortcut families into an opening routine — reconcile, lock the corners, count the edges — and usually within ten moves a is down to two or three undecided spots, the rest left to cross-referencing.
Kakuro
Kakuro is Sudoku’s addition-table cousin.
White cells run in continuous horizontal and vertical segments, each segment carries a clue number, and you fill the segment with 1–9 so the sum matches the clue exactly. The classic rules additionally demand no repeats within a segment.
Those are the only two rules, but the table you solve with belongs to combinatorics. The range of sums of distinct digits is:
The lower bound is , the upper bound .
This range table is the source of all of Kakuro’s firepower. Sums nearer the two ends have fewer possible combinations; sums in the middle have the most. The distribution of combination counts along the sum axis bulges in the middle and collapses at the ends — the very shape of a normal curve.
The author hides “information” as far from the center as possible; the solver has to engrave that curve into the brain first.
Four fundamentals of combinatorial splitting unfold from here.
First, extreme-value lockdown. Two cells summing to 17 can only be , to 16 only , to 3 only . A clue hugging the end of the range nails the whole segment down.
Second, small-sum enumeration. Three cells summing to 6 can only be , to 7 only , to 8 either or . Small-sum segments have so few combinations that a three-cell sum of 6 hands you three knowns for free.
Third, cross filtering. Where a horizontal and a vertical segment meet on a cell, that cell’s candidates must lie in both segments’ combination sets; after the intersection often only one digit survives.
Fourth, remainder bookkeeping. Once part of a segment is fixed, the remaining cells’ sum compresses into a smaller subproblem, and the combination table is drilled down layer by layer. A three-cell sum of 12 with a 5 placed leaves two cells summing to 7, either or , and one collision with the crossing column’s candidates settles it.
Beyond the combination table there is a global identity. With no repeats in a segment, the digits 1 to 9 always total 45, so any full segment covering nine cells must sum to 45. On standard boards the “45 rule” is killer: in a full segment one cell short of complete, the last cell equals 45 minus the known part.
A mini-board has no room for a full 45, but the identity’s idea still works. A crossing cell is booked by the horizontal and the vertical segment at once, each side’s equation gives an answer, and the books balance only if the two agree. A two-cell sum of 10 crossing a two-cell sum of 12, with 3 as the horizontal’s other cell and 5 as the vertical’s, means and yield the same — the books balance. If they don’t, something is filled wrong somewhere; go back and check.
Kakuro’s solving experience is therefore double-entry bookkeeping of “combination table × system of equations”, more algebraic in flavor than the other paper puzzles here, and closer to the “sole candidate” taste of the Sudoku family.
The site widget is one preset puzzle with a numeric keypad for 1–9, clearable and resettable, and it also offers show-solution. There is a random mode as well, generating clue-less random boards — more of a calculation sandbox.
The interface does the board and the input full justice; the reasoning ledger still lives on paper. Which is rather faithful to the literal meaning of “paper-and-pencil puzzle”.
Authoring this genre is harder than solving it. First every clue must have a unique landing spot in the combination table, then the whole-board solution must be unique, and finally the clues must be dug out to exactly the right degree. A randomly generated board almost never satisfies all three at once, so genuinely solvable puzzles are always hand-calibrated.
Shisen-Sho
Shisen-Sho (implemented on the two-player mahjong / Shisen-Sho rules) fits in one sentence: remove two tiles bearing the same pattern, provided a path with at most two bends can be drawn between them, passing only through empty cells.
The site board is , 48 tiles in 10 patterns paired up. The board’s outer ring is padded with a ring of virtual empty cells so paths can detour outside the border. That is a classic implementation trick: it makes “going around the edge” a legal path, and it is often the escape route out of a deadlock.
Two bends is the game’s soul boundary.
Zero bends: same row or same column, everything between empty, straight connection.
One bend: an L shape, both straight runs clear at the corner.
Two bends: a Z or a U, equivalent to “there exists a horizontal or vertical corridor to transfer through”.
The source’s check is a breadth-first search over (cell, direction, bend count) triple states. From the start, launch in four directions, advance along straight lines through empty cells only, count one for each turn, and after two bends allow straight travel only. Translating “a path with at most two bends” into a state machine’s transition cap is far more elegant than enumerating all two-bend paths, and it incidentally guarantees the path found uses the fewest bends.
The hint button is implemented far more plainly. A double loop exhausts every same-pattern cell pair, calls the same check function on each, and selects one of the first connectable pairs it finds.
One function serves as both path checker and deadlock detector. When no pair is connectable, the board is dead.
The generator guarantees only that patterns are paired, not that the board is solvable end to end; deadlock is a real state. This is also where Shisen-Sho parts temperamentally from the other puzzles in this section: the other five preset a unique solution per level, while Shisen-Sho is a process game — a random deal may run clear to the end or jam halfway, and the only way out is a restart.
The solution skeleton is a three-layer scan. Sweep zero-bend pairs first (adjacent, or truly clear along a line), then one-bend pairs, and only then spend two bends — because every removal rewrites the distribution of empty cells, and zero-bend pairs are the cheapest with the most certain payoff.
The real decision point is choosing which pair when one pattern offers several. Of 10 patterns, each usually has two or three pairs on the board at once, and which pair you clear decides which corridor opens for later paths. Novices clear whatever pair they see; experts ask first whether the path is useful for the board to come. Treating “removal order” as “spatial resource allocation” is the watershed where this genre crosses from casual into strategy.
Run the state-space numbers and you see why this check is cheap. The board with its outer ring has positions, each with 4 travel directions and 3 bend tiers (0–2), so the total state count is under a thousand and breadth-first search answers in milliseconds. The hint button’s brute force is on the order of cell pairs, each running the same search — still instant for a web mini-game.
“At most two bends” is itself a carefully chosen difficulty valve. One bend is too loose: same row or column suffices and the game degenerates into an eyesight test. No limit at all degrades the check into ordinary graph reachability, where with enough empty space almost everything connects and decision depth drops to zero. At exactly two bends, path existence depends jointly on the pattern distribution and the shape of the empty space, and only then does removal order genuinely affect what follows.
“Paths may pass through empty cells only” also turns empty corridors into a resource. Leaving a passage open is sometimes worth more than clearing another pair — an idea that echoes Dots and Boxes’ “leave a chain”.
Pipe Mania
Pipe Mania’s board is a 6-column 5-row grid of pipe pieces, four kinds: straight, elbow, T-junction, cross. Some row on the left edge is the water source (green frame), some row on the right edge the outlet (red frame).
Clicking any piece rotates it 90° clockwise; the goal is to get water from source to sink.
The verdict is not “it looks connected” but graph traversal. Depth-first search from the source, with water spreading only into neighbors that interlock in both directions. This cell opening eastward is not enough — the eastern neighbor must open westward; a one-way opening is a wall. Connectivity counts only on reaching the sink cell with the sink’s opening facing right.
Two-way interlock is the rule novices trip over most. Intuition says “my cell opened toward yours, so water should pass”, but in the implementation an opening is a contract that takes effect only when both parties sign. The dead end is not on your side; it is the other side not answering.
From this follow three principles of the solution skeleton.
One: don’t look at the opening, look at the other side’s reply. Before checking any connection, confirm the neighbor’s reverse opening exists.
Two: order by degrees of freedom. Straights and elbows have the fewest valid orientations (straight 2, elbow 4), T-junctions have 4, and crosses need no rotation at all. Lock the low-freedom cells first, boundary cells above all: a straight in the top row that wants to join the flow has no use for an outward opening and must lie parallel to the boundary. Leave the high-freedom T-junctions and crosses for last — the hand-rolled version of the minimum remaining values (MRV) heuristic from constraint solving.
Three: push from both ends toward the middle. The source’s and the sink’s cells are the two strongest known constraints on the board; fixing the must-pass cells from those ends and propagating outward beats wandering the board’s middle by a lot.
The generator guarantees every level is solvable. The path between source and sink is laid down first; path cells are fixed as straights or elbows according to the path’s direction, with only their orientations scrambled, and every remaining cell is fully random.
Note, though, that the win condition is wider than “restore the buried path”. DFS reachability plus the sink’s opening facing right passes, and those randomly scattered non-path cells join the connectivity too: route a second line through a T-junction and it still flashes “Connected!”.
Guaranteed solvable and leniently judged, the widget plays without frustration — which also means it trains connectivity analysis rather than unique-solution reasoning. It stands at exactly the opposite end of the paper-puzzle lineage from Dominosa: one end forces you to find the single closing of the ledger, the other asks only for any live route.
The rotation itself has an account to run. Each cell’s orientation has only 4 positions and clicking cycles them. A straight’s correct orientation arrives within 4 clicks, elbows and T-junctions likewise, and crosses behave the same clicked or not. Trial and error is a finite loop with no deadlock; the only real cost is deciding which cell is worth turning first.
That breeds a plain priority order. Boundary cells (an outward opening is waste) first, source- and sink-adjacent cells next (strong constraints), ordinary cells after, crosses last (no rotation needed).
Note also that the verdict runs whole-chain DFS from the source, and partial connectivity gets no feedback. Water either runs from source all the way to sink, or the whole chain quietly fails. The human player has to maintain a mental map of “which region is already interlocked into a network”, expanding cell by cell from the source and, on each expansion, going back to check the new cell’s other openings — the Pipe Mania version of bookkeeping.
Dots and Boxes
Dots and Boxes has almost no entry threshold. Players take turns drawing lines between adjacent dots; whoever draws the last edge enclosing a square claims that square and moves again. When every square is owned, the majority wins.
The site widget uses a dot grid enclosing , 9 squares and 24 edges, with human-vs-computer and two-player modes. The computer picks a uniformly random empty edge each turn — an opponent honest to the point of endearing.
But “claim a square, move again” is the spark of the whole game theory.
It means that once a square with three edges drawn (a capture) appears, its captor can chain captures. A run of connected capturable squares forms a chain, and whoever is forced to draw the chain’s third edge first (open the chain) hands the opponent a run all the way to the chain’s end.
So the whole game’s macro structure reduces to two questions: how chains form, and who is forced to open the first one.
Most early moves avoid creating captures (safe moves), and the move that exhausts the safe edges is the handover ceremony of “the right to open a chain”. A 3×3 board has few edges, so the handover comes early, and every safe move deserves a slow count of the captures.
Sacrifices and double-crosses are the craft of receiving that handover.
When the opponent opens a chain and you face one of length , the standard answer is not to take it all. After taking the first squares, draw the “double-cross” edge at the chain’s tail. Give up the last two squares, let the opponent take them and be forced to open the next chain.
The ledger: you gain , lose 2, and in exchange pin “the next chain-opener” on your opponent. As long as other chains remain on the board, the trade is a sure profit.
A loop chain’s sacrifice price is 4 squares.
The essence of sacrifice play is demoting squares from “goal” to “currency”. Squares are the money that buys the right to open a chain; the winning move is not how much you take this round but who still holds the opening obligation after the last settlement.
The chain-forming phase holds one more slow-play craft worth recording. Of the 24 edges, every early move should maintain “at most two edges per square”. That is the graph-theoretic definition of a safe move: once any square takes its third edge, a capture has appeared.
Both sides are therefore adding edges to a degree-constrained graph, and the moment safe moves run out is decided by the graph’s structure, not by anyone’s wish. On a small board that moment arrives quickly, and what an expert is really doing is setting up two or three moves early — controlling whether long or short chains, chains or loops, appear when it comes.
9 squares is an odd count, so the first player holds the parity dividend. With both sides playing optimally the first player wins 5–4. The second player’s counter is to split the position into an even number of chains, dropping the “last chain-opener” obligation back on the first player.
Every precondition of sacrifice craft is laid in these few safe moves.
It must be said that this craft is useless against the random computer. A uniformly random opponent does not know how to accept your kindness. The Dots and Boxes widget’s value lies in demonstrating this rule skeleton in two-player mode; competition-grade sacrifice play needs a bigger board and an equally clear-headed opponent.
Six puzzles laid out, the master of the bookkeeping art is Sudoku: it owns the most complete technique ladder and the most industrialized puzzle machine, and the two mirror each other — the first half about how people solve, the second half about how puzzles are made.
Sudoku’s Two Sides: From Technique Ladder to Puzzle Machine
Sudoku’s rules are minimal: each row, each column, each box holds 1–9 exactly once.
But between “can play” and “can crack hard puzzles” runs a clear ladder of technique, and behind every puzzle ever played stands a generator that guarantees it is “solvable and unique”.
The two are mirror images: the human technique ladder defines a puzzle’s difficulty, and the machine’s uniqueness check decides whether the puzzle holds up at all.
The practice board is at Sudoku, with a pencil-mark candidate mode. Every technique below builds on marked candidates.
Level 0: Naked and Hidden Singles
- Naked Single: a cell whose candidates are down to one. Usually the natural accumulation of row/column/box eliminations, sudoku’s breathing. Most of the filling is done by it;
- Hidden Single: a cell with several candidates, but some digit has only one possible position in that row/column/box. It hides in the candidate pile and demands scanning by digit rather than by cell. The hidden single is the workhorse of almost every beginner puzzle.
Beginner puzzles (newspaper grade) usually clear with just these two levels.
Level 1: Intersection Removal
The trigger: digit k’s candidate positions inside a box all fall on the same row. You still cannot tell which cell, but one thing is certain: no other cell in that row can be k (otherwise the box’s k would escape the row).
The “whole box constrains the row” inference is called Pointing; the reverse, “whole row constrains the box”, is Claiming.
Intersection removal never fills a digit directly; its job is deleting candidates.
And once candidates are cleaned out, level-0 naked singles appear in bulk.
Intermediate puzzles live or die here.
Level 2: Pairs and Triples
- Naked Pair: two cells in the same unit (row/column/box) whose candidates are exactly the same two digits {a, b}. Then a and b must be split between those two cells. a and b can be deleted from every other cell in the unit;
- Hidden Pair: two digits in a unit that can only appear in the same two cells (even if those cells carry other candidates). Then every candidate except {a, b} is deleted from those two cells;
- The Triple generalizes the pair: three digits split among three cells, same reasoning.
The pair family fits into one sentence: naked means “n cells can hold only n digits”, hidden means “n digits can live only in n cells”.
The two are duals under the cell/digit view, with opposite deletion logic (naked deletes those n candidates from the unit’s other cells, hidden deletes everything but those n from the two cells).
Triples and quads are that same sentence at n=3 and n=4; in implementation it is just “enumerate combinations of candidate sets within a unit”. For k=2 to 4 the number of combinations is small, and manual scanning is barely feasible. At k≥5 the enumeration and the observation cost explode together, and practical value drops off.
Once the unified structure clicks, pairs and triples are no longer two rules to memorize.
They are one rule pointing in two directions.
This is the first technique that requires holding several cells’ information at once, and the observation difficulty steps up noticeably.
Level 3: Chained Structures
By this point, inference between cells starts reaching across the board.
X-Wing: digit k’s candidate positions in two rows are exactly the same two columns.
However k lands (two arrangements, pick one), no other cell in those two columns can be k.
A 2×2 rectangular constraint, exerting force across four units.
An example: the 5s in row 2 have candidates only in columns 1 and 8, and the 5s in row 7 also only in columns 1 and 8. The rectangle’s four corners hold.
If row 2’s 5 is in column 1, row 7’s 5 is forced into column 8; the reverse holds too.
Either way, candidate 5s in the remaining cells of columns 1 and 8 can be crossed out.
Swordfish is its three-row version (three rows, three columns), same principle, harder to spot.
XY-Wing: three cells form a hinge.
A pivot cell with candidates {x, y}, and two wings with {x, z} and {y, z}.
Both wings share a unit with the pivot, and both wings “attack” some target cell (both can see it).
Whether the pivot is x or y, one of the wings must become z.
So z can be deleted from the target cell.
This is the first “if… then… either way” two-dimensional reasoning, the watershed between counting and logical chains.
Beyond Level 4
Stronger techniques (Simple Chain, X-Chain, coloring) string strong/weak links into long chains: “must be true / must be false” propagates along the chain, and deletions converge at its two ends.
They are uniform in form and powerful, but the observation cost is the highest.
Most manual solvers get through intermediate and most hard puzzles up to XY-Wing; chain techniques are left to the enthusiasts.
Past that sits a family of moves that work differently: uniqueness arguments.
The representative is the Unique Rectangle: if some four-cell structure allows two arrangements that are both legal, the puzzle has two solutions.
That contradicts the “unique solution” convention of sudoku, so candidates can be deleted safely.
Note that its footing is not sudoku’s own rules but the setter’s habit of promising a unique solution; it cannot be used where the puzzle bank does not guarantee uniqueness.
Deep into the ladder, even “which premises may be borrowed” becomes a discipline of its own.
And that unique-solution promise is exactly what the machine half strains to guarantee.
A Full-Grid Scan Order for When You Get Stuck
“Stuck” usually means undisciplined scanning, not missing technique.
The eyes wander at random, miss a hidden single in some unit, then grind away at the wrong spot.
It pays to turn the scan into a fixed pipeline, each round from top to bottom:
- Naked singles: scan every empty cell, fill the ones down to a single candidate;
- Hidden singles: scan by digit (1 through 9), asking in each unit “where else can this digit go”;
- Intersection removal: each digit × each box, check whether the candidates lock into one row/column;
- Pairs/triples: in each unit, find groups of cells with identical candidate sets;
- X-Wing and above: scan row/column candidate positions across the whole grid, digit by digit.
If any step produces something, go back to step 1 and start over (a new digit triggers a cascade).
Only after all five steps come back empty do you admit you are “really stuck”, and need a heavier technique or a check for mis-marked candidates.
The value of a fixed order is reproducibility: the same board scanned twice gives the same result, and “I missed it” turns from mysticism into a process error you can fix.
Two habits go with it: keep pencil mode on the whole time so candidates are fully marked (every later technique depends on candidates being visible). Deliberately record the kind of deadlock that traps you. Most people always get stuck on the same one or two structures, and patching that level specifically pays best.
The Flip Side: How a Computer Solves the Same Puzzle
An amusing contrast: a computer solves sudoku without any of these techniques, going straight to backtracking + constraint propagation.
Pick the cell with the fewest candidates, try a digit, propagate, backtrack on conflict, and any 9×9 finishes in milliseconds.
Then what are human techniques for?
They buy readability of the information structure.
Backtracking is “try and undo”; a logical technique is “every step is certainly true”.
The human brain has no stack and undo is expensive, so it needs inference that cannot be taken back.
The relationship is like proof versus search: the answer a computer finds and an elegant proof are two different things.
A sudoku’s “difficulty grade” is actually assigned by the technique ladder required, not by backtracking step count.
That is also why bank grades feel closer to human experience than “the difficulty the program believes”.
And this contrast leads straight to the next question: since machines solve so fast, how are puzzles made?
The heaviest machine in the answer happens to be a variant of the solver.
Generation Flow
Sudoku generation runs backwards: you do not compose a puzzle from an empty grid, you build a complete legal solution first, then remove cells.
Step one: build the solution.
Start from an empty grid and fill cell by cell with backtracking, shuffling the candidate digits before trying each cell.
The randomness makes every generated solution different.
Backtracking is startlingly fast on this problem: constraint propagation (candidate filtering) plus fewest-candidates-first (MRV, always fill the cell with the fewest candidates) fills the grid in milliseconds.
Box constraints are held in bitmasks (next section), so candidate filtering is a single bitwise operation.
Step two: dig holes.
Remove digits from the solution one at a time, and after each removal ask: does the remaining puzzle still have a unique solution?
Yes: keep the hole.
No: put the digit back and move to the next cell.
Dig until the target number of empty cells is reached.
The whole generator’s quality depends on the checker in step two.
The Heart: The Solution Counter
The naive way to decide uniqueness is “solve it once and see whether it comes out”.
That is wrong.
Solving it only shows “at least one solution”, never “exactly one”.
The right move is to turn the solver into a solution counter:
countSolutions(board, limit=2): find the empty cell with the fewest candidates if no empty cell: return 1 # found another complete solution for each candidate digit d: place d count += countSolutions(board, limit) undo d if count >= limit: return count # prune: stop once we have enough return countThree key points:
- Stop at 2. Uniqueness only cares “is it one, or more than one”; once a second solution is found, return straight up the stack. This pruning makes multi-solution detection very fast, cheaper in fact than “solving fully once”;
- MRV pruning (fewest candidates first) is the counter’s other source of speed: branch on the least-branching cell and the search tree stays smallest;
- The result has only two uses: 1 = may dig, ≥2 = must restore. There is no third case (0 is impossible; the puzzle before digging comes from a solvable parent).
A generator runs the counter dozens to hundreds of times per puzzle; luckily a single run takes microseconds to milliseconds, so real-time generation is no trouble.
Bitmasks
The foundation under all this absurd speed is the bitmask.
Three length-9 integer arrays record which digits have appeared in each row, column, and box; bit k set means k is used:
candidates(r, c) = ~(rows[r] | cols[c] | boxes[box(r,c)]) & 0x1FFOne OR takes all three constraints at once, one “negate and AND” yields the candidate set. Placing a digit = setting three bits, undoing a backtrack = clearing them.
The traditional “check all 9 digits for conflict one by one” — nine comparisons — becomes a single bitwise operation.
Cell selection uses MRV, which needs a candidate count (popcount), and the lowest candidate comes from the lowbit trick (x & -x).
Sudoku’s constraint structure suits bitmasks naturally: 27 constraint units, 9 states, all aligned to 9 bits.
Half of the generator’s “milliseconds per puzzle” confidence is backtracking pruning, half is right here.
The Unique Solution Is Sudoku’s Soul
Why such insistence on uniqueness?
Because every human solving technique rests on “each inference is necessarily true”.
In a puzzle with several solutions, some cells take different values in different solutions. Any “deterministic inference” aimed at them (hidden singles, pairs, X-Wing) breaks down, and the player can only push forward by guessing.
A multi-solution “sudoku” is a different game to play: not a logic puzzle but a crossword of luck.
The unique-solution promise that the Unique Rectangle borrowed in the first half is redeemed right here.
So strict sudoku banks (competitions included) write uniqueness into the definition.
This is also the line between “program-generated” and “hand-set”: hand-setting relies on experience and verification, program generation makes verification a hard gate at every step.
Hole Count ≠ Difficulty
A widespread misunderstanding: the more cells you dig out, the harder it gets.
The truth is that difficulty correlates weakly with empty-cell count and strongly with “which technique level solving requires”.
Two extreme examples:
- A 50-empty-cell puzzle where every step has a hidden single available is a beginner puzzle;
- A 30-empty-cell puzzle that must reach for an X-Wing halfway through is a hard one.
The empty-cell count does have one hard edge: a unique-solution sudoku can carry as few as 17 givens.
In 2012 a team proved by exhaustive computation that no 16-given sudoku with a unique solution exists.
The generator never has to worry about hitting it: the checker puts digits back before the puzzle turns multi-solution, so the floor of 17 is “stopped naturally by the checker”, with no special code.
The Difficulty Simulator
How does a decent generator control difficulty?
Sudoku difficulty is governed by counting techniques, not empty cells.
Solve with a “human simulator” that translates the first half’s technique ladder straight into code:
difficulty = 0loop: solve with all techniques of level ≤ the current cap, until no move is left if solved: difficulty = highest technique level used this round; done if the counter says unsolvable: discard the puzzle (should not happen); done allow the next level up, continueEach level of technique is itself fixed code: a naked single is “a cell with only one candidate”, a hidden single is “a digit with one position left in a unit”, intersection removal, pairs… added level by level.
The simulator stalling does not mean the puzzle is unsolvable. It only means “the next technique up is not implemented yet”.
So the loop has to work with the counter: the counter says unique, the simulator cannot move, therefore the difficulty is the current cap plus one level.
Implementation order matters too: getting the low levels complete (miss one hidden-single variant and difficulty is inflated) affects grading quality more than rushing in an X-Wing.
The digging stage can even use it in reverse: re-evaluate with the simulator after each candidate removal, and if difficulty falls short, keep digging or roll back.
This “grade by solving method” scale and grading by backtracking steps (the program’s view) are two completely different rulers; only the former matches what human players feel.
Symmetry and Aesthetics
Most sudokus in print have rotationally symmetric hole patterns (the dug cells mirror about the center).
It is easy in engineering terms: treat digging candidates in symmetric pairs, so digging a always tries its mirror a′ at the same time.
The cost is less freedom. At equal difficulty, a symmetric puzzle can usually dig slightly fewer cells.
It is a purely aesthetic decision, but it contributes a lot to the “looks like a real publication” impression.
Beyond Sudoku there are four games most easily mistaken for “games of luck” — 2048, Minesweeper, Lights Out, and the sliding puzzle. Each of them hides a complete solution method that takes no talent, only method.
Mathematical Tools in Four Puzzles
Four games are the easiest to mistake for “games of luck”: 2048 (new tiles appear at random), Minesweeper (the mines are laid at random), Lights Out (which looks utterly lawless at the start), and the sliding puzzle (shuffled at random, half the openings can never be solved again).
But each of them hides a complete solution method that takes no talent, only method.
2048 tames randomness with structural strategy, Minesweeper puts every wager on the table and computes it, Lights Out is simply a linear algebra exercise disguised as a game, and the sliding puzzle contributes the most elegant tool of all: a quantity that “never changes”, used to decide solvability.
This section takes all four games apart, with four mathematical tools — strategy structure, probabilistic reasoning, linear algebra, invariants — taking turns on the same board-shaped stage. All four games live on this site: 2048, Minesweeper, Lights Out, the Sliding Puzzle, and the classic Klotski.
1. 2048
Below is a playable 2048 — open a game as you read, and every discipline in the text can be verified on the spot.
See the randomness first
The rules of 2048 take thirty seconds to learn: slide tiles on a 4×4 grid, equal numbers merge on collision, and after every move a new tile appears at random.
But between “can play” and “reliably pushes to 4096” sits a layer that the rules never mention: planning the order of merges.
After each move the system drops a new tile into a random empty cell — 90% chance of a 2, 10% chance of a 4 (the ratio used by the common implementation).
This asymmetry has two direct consequences:
- 2s are the staple, 4s are a skip ahead. Building a takes fours as raw material. One 128 costs 32 fours; built entirely from 2s it costs 64, so the overwhelming majority of the material actually comes from that 90% of random 2s. The value of a 4 is the skip: every random 4 saves one round of the “two 2s make a 4” process, and the more big numbers on the board, the more expensive that process gets;
- The calculation of the theoretical upper bound gets stuck here too — we will see it later.
The core principle
2048 has no undo, and a merge is an information-decreasing operation: two 64s become one 128, and what you lose is “two units that could be scheduled separately”.
The most common beginner death is merging out of order. Collapse a whole row of 2, 4, 8 into a lump, then suddenly no two adjacent cells anywhere hold the same number: the move produces zero merges and still forces another tile.
Every move of a strong player maintains one structure: the monotone chain.
Pin the largest number in a corner, keep the second-largest right beside it, the third beside that, with the whole row or column decreasing in one direction.
Once the tail of the chain merges upward, the new big number is automatically adjacent to the next link. Merges travel along the chain like dominoes, and one move can trigger a cascade (128+128→256, which then merges with the 256 beside it into 512…).
Corner strategy
The monotone chain needs an anchor — that is the reason behind “keep the big number in the corner”:
- A corner can be broken from only two directions (with the big number in the corner, any move that slides toward the corner never drags it away);
- In practice there are two disciplines: never wreck the big structure for a small merge. An isolated 32 merge is trivial; dragging the 512 out of the corner for it is a disaster. Keep at least one “recovery direction”. Of the four directions, always keep one that can press the whole board back into monotone shape (usually the “push everything toward the corner” one), and never press it until it matters.
Another discipline that is easy to overlook: fill rate matters more than score.
The number of empty cells is the buffer. With plenty of empties a bad opening can still be saved; below three or four empties, a single random 4 in the wrong place ends the game.
So in the midgame, clear “fragments” (scattered small numbers that are not part of the chain) first, instead of rushing the score.
The serpentine chain
A strictly decreasing row holds only 4 cells, while in high-scoring games the chain carries far more than 4 numbers.
So the monotone chain in practice is never a straight line but serpentine: decrease from the corner along the first row to the end of the row, fold back, and keep decreasing in the opposite direction on the second row.
For example 512, 256, 128, 64 across the first row, then 32, 16, 8, 4 right to left on the second, so that 64 and 32 sit next to each other at the fold.
All 16 cells are thus strung into one 8-segment polyline, and any two adjacent links of the chain are physically adjacent.
The serpentine chain has 8 equivalent placements (4 corners × two winding directions, clockwise or counterclockwise), and they are essentially the same. Pick one and never reverse halfway — between two reversals the board must pass through a fragile period with a broken chain.
Serpentine brings one more discipline: new big numbers must land on the chain’s extension line.
Merges happen at the tail of the chain, and the upgraded tile must be able to join the next link. If fragments that are not part of the chain pile up near the tail, the new big number is isolated into an island instead.
The preferred direction for clearing fragments is to push them away from the chain, opening a corridor at the tail.
Three typical ways to die
Reviewing lost games, the vast majority fall into three patterns:
- Corner drift. The largest number stays put only while you “push toward the corner”. Press a sideways direction midway to grab a small merge and it gets dragged out. Pinning it back means rebuilding the whole monotone structure, and during the rebuild the board has no anchor, so every random tile landing is dangerous;
- The head shake. With the chain lying across the top two rows, a big vertical move may drag the big numbers away, so you dare only shuffle left and right. Every move forces out a new tile while the row structure keeps degrading, and deadlock arrives within a few moves. Head shaking is not a mistake but a symptom — the chain is already broken: when you notice yourself shaking, consider abandoning the local position and rebuilding the structure;
- Premature merge. A pair of equal numbers in the middle of the chain gets merged “while you are at it” — say the chain 256, 128, 64 merges that pair of 64s into a 128. The chain snaps in the middle and the two halves no longer line up. Merges should run along the tail; a mid-chain merge opportunity is better kept as a spare part.
Opposite the ways to die there is an often-ignored resource concept: alignment.
When two pairs waiting to merge sit in the same row (column), one slide triggers both merges — one move doing the work of two.
When alignment is scattered, the same merges must be split into two moves, each paying for an extra random tile.
The rhythm of a game
Putting “monotone chain + serpentine” onto a whole game, the three phases have completely different jobs:
- Opening (roughly the first 30 moves): the goal is not score but standing up the serpentine skeleton. Big numbers are not settled yet, so bold merges are allowed and temporarily breaking monotonicity is allowed. The only thing to truly avoid is letting random tiles fill the board before the skeleton sets. The opening has many empty cells and mistakes are cheap; it is the only free-improv phase;
- Midgame: once the chain forms, switch to advancing along the tail. Ask two questions every move: did this merge happen at the tail? Can the new tile join the next link? Midgame score is a byproduct; the real ledger is “empty cells ≥ 4” and “no break in the chain”;
- Endgame (three or four empty cells or fewer): switch to survival mode. Use only the “push everything toward the corner” direction, letting random tiles land on the far side of the chain. Save the accumulated merge opportunities for one burst at the tail. One cascade that clears half a row of fragments frees several times the buffer of ten scattered small merges.
To tell which phase you are in, the empty-cell count is enough: eight or more is the opening, four to eight the midgame, four or fewer the endgame.
Many games die from “playing the endgame with opening moves”.
Diagnosing a concrete board
Take a midgame position and practise putting the rules above to work:
512 256 128 64 4 8 16 32 2 4 2 4 8 4 2 4The first row decreases strictly left to right, and the second continues from the right with 32, 16, 8, 4. The serpentine chain is intact across the top two rows, with 64 and 32 adjacent at the fold.
All eight cells in the lower half (2, 4, 8 and the like) are fragments outside the chain.
The diagnosis for this board: the structure is healthy, and the current task is clearing fragments.
Gather them downward to free the third row for the chain’s extension, instead of rushing to merge the 128 and 256 in the upper half.
Now a sick board:
128 512 64 32 8 16 4 2 16 4 8 2 2 8 4 2Three lesions: the largest number 512 is not in a corner (top row, second column — pushing right or down keeps it drifting); the second-largest 128 sits to its left, so the order of the chain is already inverted and this misalignment must be handled before “pressing back into the corner”; every pair in the lower half is offset (16 against 16, 8 against 8, 2 against 2, all one cell apart), so no merge opportunity fires in a single move.
In such a position the best move is often counterintuitive. Leave the 512 alone for now, align the pairs at the bottom, bank up a cascade, and let the freed space leave room for “re-pinning the corner”.
Diagnostic skill is the strategy itself: on the same board, the player who sees “where the chain broke and how much buffer is left” and the player who only reads the total score are playing two different games.
How much luck is involved
Because new tile positions are random, the same strategy has variance.
Treat “the final board under a fixed strategy” as a random variable and you can talk about expectation.
The community consensus from extensive playtesting is: the monotone chain with a corner anchor reaches 2048 reliably and 4096 with high probability. Past 8192, results start to depend significantly on luck (when the 4s appear).
Beyond that, a human cannot process the expectation of every move, and needs expectimax search. Model “how do I move this step” and “where does the system place the next tile, and which one” alternately, compute the expected utility of each branch, and backtrack. A written AI reaches the 32768 range reliably.
A side note on how expectimax leaf nodes score a board, because those scoring terms are exactly the human disciplines turned into math: monotonicity (does the board decrease along the serpentine direction), smoothness (how close adjacent values are, which decides how many merges are in sight), empty cell count (liquidity), and whether the largest number is pinned in a corner, summed with weights into one score.
Open-source 2048 AIs are almost all this recipe.
To improve your own play, self-checking against these four items is more effective than memorizing any mantra. It is a strategy checklist sorted by importance.
The theoretical limit
The community-accepted analysis: on a 4×4 board the theoretical limit is 131072 (), and the conditions for reaching it are so strict they are practically fantasy.
The reasoning works backward from “material conservation” to what the board looks like at the moment of achievement.
One move before merging into 131072, two adjacent 65536s must be on the board, and for those two to “each grow up without consuming each other”, the other 14 cells must hold exactly a complete descending chain from 32768 down to 4.
Two s plus a chain from down to — 16 cells, a full board, not one empty.
The chain bottoms out at 4: placing one more 2 below it would be 17 cells, and the board cannot hold them. If any link of the chain is missing, the total material is immediately short.
Where luck really bites is the last cell: the random tile that fills the perfect chain must be a 4 (only a 10% chance); a 2 cannot merge with anything and the perfect structure is void on the spot.
So 131072 is a counted upper bound. Perfect structure throughout, plus drawing that one 4 at the very end — in practice, treat it as nonexistent. Human records usually land between 32768 and 65536.
The general value of this reasoning is the method itself: count the limit with material conservation.
Just work out “how few cells the moment of achievement can occupy”: building needs at minimum two s plus a chain down to 4, k−1 cells in total, so the limit on an n×n board is .
4×4 gives , 3×3 only reaches (1024), and 5×5 rises to — nine extra cells, a ceiling nine doublings higher.
The ceiling of any “merge-type game” can be counted the same way.
A minute of rules, infinite depth of strategy. That is why 2048 wears better than it looks.
2048 tames randomness with structure. The next game puts randomness on the table and does the accounting directly.
2. Minesweeper
Minesweeper is a severely underrated math game.
Most people can read the numbers and do basic inference, but at the moment where “nothing more can be deduced and a guess is required” they leave it to fate.
In fact every wager in the middle and late game of Minesweeper has a computable risk, and comparing those risks is exactly where strong players separate from average ones.
First tell the two kinds of inference apart
Minesweeper inference has two layers:
- Deterministic inference: a cell is necessarily a mine or necessarily safe. In a position where one wrong click kills, the more certain conclusions you can derive, the fewer wagers you need.
- Probabilistic inference: after deterministic inference is exhausted several options remain, and each candidate cell has a “probability of being a mine”; you pick the one that is best in expectation.
The vast majority of players work only on the first layer; on the second they go purely by feel.
Three deterministic patterns
A number n means exactly n mines among its eight surrounding cells.
The most basic operation is “subtract what is already flagged”: if the flagged mines around a number equal n, all remaining adjacent cells are safe; if the number of unopened cells equals the remaining mine count, all remaining adjacent cells are mines.
On top of that come two classic edge patterns:
The 1-2-1 pattern (the numbers 1, 2, 1 in a row along an edge, three unknown cells above):
□ □ □1 2 1Name the three unknown cells x₁, x₂, x₃ (each above one of the numbers, each adjacent only to those three).
Three constraints: x₁+x₂=1, x₁+x₂+x₃=2, x₂+x₃=1.
Substituting the first into the second gives x₃=1 (mine), back into the third gives x₂=0 (safe), and substituting again gives x₁=1 (mine).
Conclusion: mines directly above the 1s at both ends, the middle safe. No memorization needed — three lines of elimination derive it.
The 1-2-2-1 pattern: the same method over four numbers gives the equations x₁+x₂=1, x₁+x₂+x₃=2, x₂+x₃+x₄=2, x₃+x₄=1.
From the first, x₁=1−x₂; from the last, x₄=1−x₃. Substituting into the second gives x₃=1, and into the third gives x₂=1.
So x₂=x₃=1 (two mines above the two 2s) and x₁=x₄=0 (the outer cells are safe).
Patterns are just a lookup table for systems of equations.
A 1 in the corner: a corner 1 has only three surrounding cells; if all three are unopened and carry no other constraint, each is 1/3.
This is the cheapest “constrained blind spot” in Minesweeper.
Summaries of these patterns are all over the web, but what really frees you from memorizing charts is the unified method below.
Probabilistic inference
The single-constraint case is simple: a number n with m unopened neighbors gives every unopened neighbor a probability of n/m.
A “1” next to 7 unknown cells: 1/7 each. A “3” next to 4 unknown cells: 3/4 each.
Multiple constraints are the normal case. A cell is often the neighbor of several numbers at once, the constraints hold each other in check, and computing them one at a time is then wrong.
The unified solution is counting enumeration: group the interconnected unknown cells (usually a run of cells along the boundary) and enumerate every mine configuration of the group that satisfies all the constraints. For each cell in the group, the fraction of legal configurations in which it is a mine is its posterior probability.
Walk through the smallest example.
Three unknown cells a, b, c, with two constraints from adjacent numbers: the 1 has only a, b around it (so a+b=1), and the 2 has a, b, c (so a+b+c=2).
Only two configurations are legal: (a=1,b=0,c=1) and (a=0,b=1,c=1).
So the probability that c is a mine = 2/2 = 1 (certain — flag it), and a and b are 1/2 each.
One enumeration, and a conclusion invisible from any single number falls out.
The 1-2-1 pattern is just this method with one more equation.
A complete solver adds two more steps so that counting enumeration runs on real boards.
First, component splitting: interconnected boundary cells naturally fall into several independent connected components with no shared constraints, each enumerated on its own and then combined. The total configuration count is the product of the components’ counts, never touching the exponential blowup of enumerating the whole boundary at once.
Second, the global mine count constraint: the remaining mine count is a hard cap. A combination “component A uses a mines × component B uses b mines” is legal only if a+b plus the free cells’ mines stays under the cap.
This step subtly shifts the probabilities inside each component. The same cell’s “nominal probability” often differs between the early game and the endgame, and this is why.
Do not forget the cells outside the groups either: a “free cell” adjacent to no opened number has a probability equal to the global mine density (remaining mines ÷ remaining total cells).
Beginner is 10/81 ≈ 12%, intermediate about 15.6%, expert about 20.6%.
That is why free cells are not free either: on expert, a free cell is more dangerous than some cells touching a “1”.
When you must guess, where do you click?
Once the probabilities of all candidate cells are computed, the choice rule is plain: click the lowest probability.
But two details are often overlooked:
First, when probabilities are close, consider whether you can keep playing after a wrong guess.
Two cells are both 50%, but losing one wager ends the game while losing the other leaves a position that can still be won back. Pick the one whose loss costs less.
The classic case is the 50/50 at the end: no information helps, both are the same. So make fewer deterministic mistakes early and do not corner yourself into one.
Second, reducing future variance is also a gain.
Some cells have a slightly higher probability but release a lot of information when opened (at an information crossroads, say), turning several later 50/50s into deterministic inference.
The rigorous approach computes expected moves all the way down; the pragmatic one: among two candidates with close probabilities, click the one that untangles more constraints once opened.
One popular claim deserves clarification: “opening in the middle at the start beats opening in a corner”.
Most modern Minesweeper implementations guarantee the first click is safe (and common ones also keep the first-click area mine-free), so the difference between starting positions is smaller than legend says.
What really affects the value of the first click is the inferable area it opens, which depends on the implementation’s first-click protection rules and differs between versions. Do not take one version’s regularity as universal.
3BV
For comparing results there is a fairer ruler than time: 3BV (Board View Value).
Definition: the number of connected “zero regions” on the board (blank areas that flood open when clicked), plus the number of numbered cells adjacent to no zero region.
Its meaning is the minimum number of clicks needed to finish using only safe clicks. A zero region opens wholesale in one click; isolated numbered cells must be clicked one by one.
3BV quantifies “was this board born good or bad”: a low-3BV expert board ends after a dozen clicks, while a high-3BV board forces you to click through four hundred-odd numbers one at a time.
Speedrunners measure mechanical efficiency as “time ÷ 3BV”, factoring out board luck.
When writing an automatic solver it is a ready-made benchmark too: a solver whose click count approaches 3BV has an “understanding” that hugs the lower bound.
There is a practical by-product to knowing the metric: glance at how many zero regions the first few moves open and you can estimate where this board’s 3BV is heading, and decide whether it is worth playing seriously.
The win-rate ceiling
On expert (30×16, 99 mines), even playing every move by method, the win rate has a ceiling: some boards still contain forced gambles after inference is exhausted.
Say two cells at the end are 50/50; no probabilistic method can save you.
That is the fate of the generation method: lay the mines at random first and talk about inference second, and there will always be positions inference cannot crack.
For an experience where “every board deserves inference”, the fix is on the generation side: the no-guess board.
The procedure: after laying mines, first try to solve with a pure-logic solver (deterministic inference plus restricted probabilistic inference); the moment it is forced to guess, re-mine the whole board, until a “logically solvable” board comes out.
The cost is longer generation (an expert board may need many retries); the gain is that the win-rate ceiling moves from “depends on the sky” to “depends on you”. Every remaining loss is your own mistake.
Which category this site’s Minesweeper belongs to, and how far its first-click protection goes, is worth checking before you start: the rules differ, and so do the probabilistic play and the value of your results.
Reading these methods once is worth less than computing them once: start a game of Minesweeper, pause for ten seconds in the midgame, work out each boundary candidate’s probability by hand before clicking, and the change in win rate is immediate.
In Minesweeper randomness is the opponent. The third game is more extreme: it looks the most lawless and in fact has no randomness at all.
3. Lights Out
The rules of Lights Out take a minute: every light on the grid has two states, pressing a cell toggles itself and its up, down, left, and right neighbors, and the goal is to turn every light off.
It looks like a game of luck; in fact it is a linear algebra exercise disguised as a game.
Solving Lights Out is equivalent to solving a system of linear equations in a world made only of 0s and 1s.
Writing “pressing a light” as a vector
The key observation is that the order of presses does not matter: pressing a cell twice equals not pressing it, three times equals once.
So a solution does not need to record “the order of presses”, only whether each cell is pressed.
An n×n board corresponds to an n²-dimensional 0/1 vector x, where a component of 1 means this cell is pressed.
The effect of pressing a cell is also a vector: itself plus its four neighbors, 5 positions flipped to 1.
Arrange the “effect vectors” of all cells as columns and you get an n²×n² matrix A.
Solving Lights Out then becomes solving:
where b is the vector of “which lights are currently on”.
The goal — every light off — is equivalent to flipping exactly the positions equal to b.
GF(2)
The Gaussian elimination here runs on a special field: GF(2), with only the elements 0 and 1, addition as XOR (1+1=0), and multiplication as ordinary multiplication.
“Pressing twice equals not pressing” is exactly “1+1=0” made physical.
Elimination over GF(2) is completely isomorphic to ordinary linear algebra: choose pivots, eliminate rows by XOR, determine the rank.
The difference is only one point. There is no “numerical error”; every operation is exact.
Which means solvability and the number of solutions both get a clean criterion: whether b lies in the column space of A.
Light chasing
Naively enumerating press or not for every cell gives cases; for 5×5 that is ≈ 33 million. It runs, but it is not elegant.
Light chasing exploits the structure:
- The presses of the first row determine everything. Chase lights row by row from the top: which cells to press in row i has exactly one purpose — to extinguish the lights still on in row i−1 (press the corresponding positions in row i). Advance this way to the last row;
- If lights are still on after the last row is pressed, the choice of the first row was wrong.
So only the first row needs enumerating. n cells give cases, 32 for 5×5.
For each one, chase to the last row and check whether everything is cleared. Cleared means a complete solution.
Why does the first row determine everything? Because the second row’s presses are uniquely fixed by “extinguish the first row”, and the third by the second.
The whole decision tree is compressed into a single chain.
The method can be practised by hand: given any opening, at most 32 tries among the 32 first-row combinations produce the answer.
Writing light chasing as code
Light chasing is just as compact in code; the core is “enumerate the first row, then force the derivation row by row”:
for press[0] in 0 .. 2^n - 1: # first-row presses, bitmask enumeration for r = 1 .. n-1: # row r's presses are forced: exactly "the lights still on in row r-1" # (lit state from the initial state, press[r-1], press[r-2], XOR-ed bitwise) press[r] = remainingLits(r-1) if all lights are off: record press as a solutionremainingLits is a small pure bit-operation function: a row’s new light state = initial state XOR that row’s presses XOR the influence of the neighboring rows’ presses — all XORs on aligned bitmasks, no loops, no branches.
The whole solver — enumerate 32 first rows, derive row by row, verify the last row — fits in a hundred lines and returns all solutions on the order of 0.1 ms.
Writing it is more useful than reading ten analyses, because every “why” forces you back into matrix language.
Some openings have no solution at all
Light chasing can hit the outcome “all 32 first rows fail”. That means b is not in the column space: this opening has no solution.
This is not mysticism; it is decided by the rank of the matrix.
The accepted result for the classic 5×5 board (Anderson & Feil’s well-known 1998 analysis): the 25×25 press matrix has rank 23 and its null space has dimension 2.
Two corollaries:
- The column space covers only 2²³ / 2²⁵ = 1/4 of openings. A randomly generated opening without a solvability guarantee draws an unsolvable board three times out of four. Mature implementations generate a solution first and back-derive the opening;
- If an opening is solvable it has exactly 2² = 4 solutions. Adding any null-space vector to a solution gives another solution. Of the 4 vectors in the null space, the 3 nonzero ones correspond to quiet patterns: press combinations that change nothing — they leave the light state untouched, and are pure redundant degrees of freedom of the solution.
The null-space dimension varies with board size: not every n×n has a nontrivial null space (some sizes give a full-rank matrix, where an opening either has a unique solution or none, never several).
This is the most interesting point of “Lights Out math”: the structure of the solutions is decided by number-theoretic properties of the board size.
5×5 happens to be the class whose null space has dimension 2.
Read in matrix language, light chasing is block forward substitution made physical: given the first row’s presses, every other row’s presses are solved uniquely, row by row.
Enumerating the first row means enumerating free parameters; everything after is a deterministic row operation.
The engineering implementation is surprisingly small too: store the 25×25 matrix as 25 integers, one row each (a 25-bit bitmask per row); elimination is XOR, and deciding whether b lies in the column space plus back substitution all fit in a few dozen lines.
Variants and generalizations
Lights Out is a “family”: change any one parameter and the linear algebra framework stays untouched — only the matrix changes:
- Adjacency rule: change the press effect from “the five-cell cross” to “the diagonal nine cells” or “only itself and the cell below-right”, and the structure of A differs, with rank and null space shifting accordingly. A variant’s solvability has no intuitive shortcut; you recompute the rank;
- Boundary conditions: the standard board’s boundary is “out of bounds, no effect”. Switch to a torus (left and right joined, top and bottom joined) and the matrix becomes circulant and the rank changes. For the same size, a torus board and a plain board can have completely different proportions of unsolvable openings;
- Higher dimensions and odd shapes: 3D Lights Out and oddly shaped boards (an L-shaped board with a corner cut out) model the same way; just swap the “cell index → vector dimension” mapping.
The power of the framework is exactly here: however the rules change, the answer “solve a linear system” does not.
A side note on the “All-Ones problem” common in the literature: it asks whether an all-on board can be cleared.
It is this same system with b replaced by the all-ones vector, and mathematically there is nothing new. Only whether the all-on position lies in the column space for a particular size must be judged separately, and the conclusion need not match the “solvable proportion of random boards”.
Back from the game to the classroom
Looking back, Lights Out makes several core concepts of linear algebra concrete:
- Column space = the set of all boards reachable by “press combinations”;
- Null space = the press combinations with no effect (quiet patterns);
- Rank = the degrees of freedom that can be controlled independently;
- Existence of a solution = whether the current board lies in the column space.
Next time you meet a “turn all the lights off” puzzle, do not test your luck. Light chasing produces a solution mechanically within 32 tries; if all of them fail, congratulations, you have stepped on one of the unsolvable three-quarters.
Go pick another opening, or write 50 lines of Gaussian elimination and let the matrix finish the game for you.
4. Sliding puzzles
Lights Out taught “how to solve”. The fourth puzzle teaches “how to prove there is no solution”.
Every 15-puzzle player has met the spooky event: pry the numbered tiles off the tray, put them back at random, and it can never be solved again.
That is not clumsy hands, it is mathematics. Exactly half of randomly permuted 15-puzzle openings are unsolvable.
The judge is a very elegant invariant (the parity of a permutation), while the other great branch of sliding puzzles, Klotski, is entirely free of this restriction.
The corresponding practice: the numeric version is the Sliding Puzzle, the classic version is Klotski.
Half the openings are doomed
The 15-puzzle: a 4×4 board, 15 numbered tiles plus one blank. Slide tiles into the blank; the goal arrangement is 1 to 15 in order with the blank at the bottom right.
Key observation: no slide ever changes the quantity formed jointly by “permutation parity + blank position”.
Broken down:
- Blank moves left or right: a tile shifts one cell horizontally. Reading the tile sequence as one dimension, this tile crosses the blank (crossing no tile), so the relative order of the numbers in the sequence is unchanged. The inversion count does not change;
- Blank moves up or down: a tile skips exactly 3 tiles in the sequence (a 4-column board, crossing the 3 tiles of that row or column), the inversion count changes 3 times and the parity flips. At the same time the blank’s row number (counted from the bottom) changes by 1, flipping its parity too.
So define the quantity S = parity of the inversion count ⊕ parity of the blank’s row number (from the bottom).
Both kinds of slide flip the two components together, or leave both alone.
S never changes.
The goal state’s S is fixed (inversion count 0, blank on the bottom row), so any opening whose S differs from the goal’s can never reach the goal, however it slides.
Pry the tiles off and put them back at random, and the inversion parity is half and half.
Exactly 50% of permutations are unsolvable.
That is also why a serious 15-puzzle never “shuffles at random” and reassembles, but starts from the goal and random-walks backward a few thousand moves. What comes out is guaranteed solvable.
A side note: this criterion uses “inversion count + blank row number” for even-width boards, and is simpler for odd widths: only the inversion parity matters (the row number no longer matters, because a vertical move crosses an even number of tiles).
The 3×3 8-puzzle belongs to this class.
Another perspective
The same fact admits a more “algebraic” reading, done in two lines: count the blank as a tile too, and every slide is a swap between the blank and one numbered tile.
A swap is an odd permutation, so every slide flips “the parity of the permutation of the 15 numbered tiles” once. At the same time the blank’s row number (from the bottom) changes by 1, and its parity flips once too.
The two quantities rise and fall together, so their XOR is naturally constant.
This reading hides all the arithmetic of “crossing 3 tiles” inside the word “swap”, and it holds for sliding puzzles of any size and any shape.
As long as you can count “from start to goal, how many times the permutation parity flipped and how many times the blank’s position changed”, solvability is decided at once.
Put the two derivations side by side and the invariant’s “invariance” reaches the same quantity by two roads. It is a small demonstration of why the invariant method is reliable.
Deciding an opening by hand
Given an opening, decide solvability within thirty seconds, with a fixed procedure:
- Read the sequence: read out all numbered tiles left to right, top to bottom (skipping the blank);
- Count inversions: the number of pairs where “the earlier number is larger than the later one”. No need to count them all — scan left to right, and for each number count how many smaller numbers lie to its right, then accumulate;
- Apply the criterion: odd width (3×3, 5×5) — an even inversion count is solvable, an odd one is not. Even width (4×4) — compute “inversion parity ⊕ parity of the blank’s row (from the bottom)” and compare it with the same quantity for the goal state; equal means solvable.
Take the classic 8-puzzle counterexample:
1 2 34 5 68 7 _The sequence is 1 2 3 4 5 6 8 7, and the only inversion is (8, 7). The inversion count is odd: unsolvable.
It is the goal state with tiles 7 and 8 swapped: one swap, parity flipped, never reachable again.
This example also explains why “prying off and reassembling” produces unsolvable boards: reassembly is an arbitrary permutation, and exactly half the time it lands outside the goal’s parity class.
Why Klotski does not have this problem
Classic Klotski (a 4×5 board) looks like a close relative: slide pieces into the blank, and the goal is to move Cao Cao to the exit.
But it sidesteps the parity curse, for two reasons:
- Pieces differ in size. A 2×2 Cao Cao, 1×2 horizontal and vertical generals, 1×1 soldiers. This is not a permutation problem over 15 equivalent elements; “inversion count” cannot even be defined;
- The goal condition is open. Cao Cao only has to reach the exit; the poses of the other pieces do not matter. The goal is an “existence” condition, not a unique arrangement.
So every Klotski opening (as long as the blanks allow sliding) is worth searching. There is no “inherently unsolvable” verdict, only the question of “how long is the path”.
How to find the shortest solution
Sliding puzzles are naturally graph search problems: every board configuration is a node, every legal slide an edge, and you want the shortest path from start to goal.
All edge weights are equal (each move costs 1), which is exactly BFS’s home ground:
- Starting from the initial configuration, expand level by level; the level at which the goal configuration is first reached is the minimum move count;
- The key engineering detail is deduplication: the same configuration is reachable by different paths, and without dedup the search explodes. Serialize the board into a string (or a bit encoding) and put it in a hash table, O(1) per lookup;
- The accepted result for the classic layout “Heng Dao Li Ma” (“blades drawn, horse reined” — Cao Cao centered, four generals around him, four soldiers in the corners) is a minimum of 81 moves. Align the yardstick: “one move” counts one slide of one piece, possibly several cells at once. The earliest recorded 81-move solution was published in 1964 in Martin Gardner’s Scientific American column, and later computer enumeration confirmed nothing shorter exists. Converted to “one cell slid = one move”, the optimal path for the same layout runs to over a hundred moves. Align the yardstick before comparing counts; the two conventions differ by tens of percent;
- How large is the state space? The number of piece arrangements in Klotski’s 4×5 is far below 15!, and the practically reachable configurations are on the order of tens of thousands to hundreds of thousands (depending on the layout); a modern phone searches the whole thing within a second. The 15-puzzle’s full space is 16!/2 ≈ 10¹³ (divided by 2 because exactly half the permutations are unreachable by parity — the criterion above). A full-space BFS is not impossible to compute, it just does not fit in memory: even a few bytes per configuration makes 10¹³ of them terabytes. So in practice use IDA*: in a depth-first framework memory scales only with the solution length, paired with Manhattan distance as the heuristic (the full mechanics are in the graph search article).
From BFS to A*
BFS counts shortest paths on the premise that all edge weights are equal, which sliding puzzles satisfy (every move costs 1).
But once the state space grows, “expand every level completely” becomes unaffordable.
A*‘s idea is to estimate for each configuration a lower bound h on “how far it still is from the goal”, and to expand first the branch with the smallest “moves taken + h”. As long as h never overestimates (admissibility), the first path to reach the goal is still a shortest path.
Manhattan distance (the sum, over all tiles, of the horizontal and vertical distance to the goal position) is a natural lower bound: one slide reduces one tile’s Manhattan distance by at most 1, so the true remaining move count is never below the current configuration’s Manhattan distance.
Only an overestimating h risks missing the optimum.
IDA* then replaces A*‘s open list with iterative deepening, compressing memory from “store the whole visited set” to “store only the current path”.
The full mechanics are in the graph search article; this site’s Shortest Path shows the difference between Dijkstra and A* node expansion directly.
Manhattan distance also has a ready-made upgrade: linear conflict.
Two tiles in the same row have their goal positions in that row too, but in reversed order. Then no matter how they move, one of them must leave the row and come back, costing at least two extra moves.
Detect these conflicts and add them to the heuristic (+2 per conflicting pair): h stays admissible, but the pruning gets noticeably stronger.
The evolution of the heuristic is exactly this: from “how far each tile still is” to “how much awkwardness is squeezed between tiles”. The closer it hugs the problem’s real structure, the cheaper the search.
Another weapon worth knowing is bidirectional BFS: search half from the initial configuration and half from the goal, meeting in the middle.
Depth halves from d to d/2, and the search volume, in powers of the branching factor, drops from to about .
In spaces with a modest branching factor like Klotski, the constant saved is substantial. The larger the branching factor, the more striking the accounting.
Keep one dedup structure on each side, and splice the two path halves together on meeting.
There is exactly one engineering pitfall: the “edges” point in opposite directions on the two sides (one side is “how to get there”, the other “how to get back”), so do not reverse the direction when splicing the path.
On this site’s Sliding Puzzle and Klotski you can try “an opening verified solvable by the criterion” and “the traditional layout” respectively.
The former always has a solution; for the latter it is worth counting how far your move count is from 81.
How far from the goal can it get
“Keep the one with the largest distance” can be pushed to the extreme: among solvable positions, how many moves is the farthest one from the goal?
This is the same as asking for the “diameter of the state-space graph (over the reachable half)”, and the answer is counted by full enumeration: the hardest 8-puzzle position takes 31 moves, the hardest 15-puzzle position takes 80 moves.
Exact values, not estimates.
80 moves means: given any solvable 4×4 board, the goal is reached within 81.
Any 15-puzzle problem claiming a “shortest solution of 120 moves” either has a non-shortest solution or is not a 15-puzzle at all.
These numbers have two practical values.
First, they are IDA*‘s natural acceptance test: finish the solver, feed it the farthest opening, and see how many milliseconds it takes to output 80. The strength of the heuristic opens a huge gap on this one test.
Second, they give “difficulty” a precise definition: the difficulty of a problem = its shortest move count to the goal.
This is the same spirit as Sudoku’s skill-based grading. Good difficulty calibration always anchors on the resources solving requires, not on the superficial “how scrambled the tiles look”.
How far can random sliding go
The opening generation method “start from the goal and random-walk backward a few thousand moves” has another property worth knowing: difficulty is directly tied to the number of slides.
A position reached in n slides has a total Manhattan distance of at most n.
An opening made in 30 slides has a maximum “total distance” of 30, and you can see at a glance that it will not be too hard.
To make an opening sufficiently scrambled, either slide a lot (after a few hundred moves the distribution is quite spread out, and further moves have diminishing returns), or change approach: generate candidate positions in batches by random sliding, compute each one’s actual shortest distance to the goal with BFS, and keep the one with the largest distance.
With the same generation cost, difficulty is noticeably more consistent.
That is also why “random difficulty” in serious sliding games fluctuates so much: whether the generator does this filtering is obvious to a player’s hands.
Put the four games side by side and the common ground is the same: they all translate “by feel” into “computable”.
Of the four tools, the invariant deserves a separate look, because it is the universal weapon for “proving it cannot be done”.
The unsolvability of the 15-puzzle does not rely on enumerating every move, but on finding a quantity that “nothing changes” and showing that start and goal take different values on it.
The same idea appears everywhere in mathematics. The mutilated chessboard domino problem (counting by black-and-white coloring), the cycle length of card shuffles (the order of a permutation)… When you meet a problem where “nothing seems to work”, ask first:
Is there a quantity that every operation leaves unchanged?
If there is, compute it; the answer may come out in one line.
The shared meta-method of the four tools: first find “a quantity hidden in the game’s rules” (the integrity of the chain / the constraints of a configuration / the rank of a matrix / the parity of a permutation), then hold every decision accountable to it.