Path Find — The Parity Check

Path Find (#25) asks you to draw a single unbroken line that visits every cell of a grid exactly once. It is a Hamiltonian-path puzzle, and like most Hamiltonian puzzles, it has a single dominant failure mode: isolating a cell or region the path can no longer reach. This guide is about the parity-check technique that lets you avoid that failure mode reliably.

The parity insight

Imagine the grid coloured like a chessboard: alternating black and white cells. Every step of your path moves to an adjacent cell, which means every step flips the colour. Starting on a black cell, the next cell is white, the one after is black, and so on. A valid path alternates colours perfectly.

For a 4×4 grid, there are 8 black cells and 8 white cells. A 16-cell path must alternate B-W-B-W... ending on whichever colour the path requires. For a 5×5 grid, there are 13 cells of one colour and 12 of the other; the path must start and end on the more common colour. For a 6×6 grid, 18 and 18; the path must alternate evenly. This parity constraint rules out many tempting-looking moves before you even try them.

How to use parity in practice

When you reach a cell with two unvisited neighbours and are not sure which to pick, count the remaining cells of each colour. If the cell you would move into has the same colour as the cell you would skip, parity does not distinguish them. But if your current cell is black and you have, say, 6 black cells and 5 white cells remaining to visit, and your two options are both white — pick the one whose subsequent neighbours include the unvisited black cells. The parity count tells you which direction the path must eventually go.

This is especially useful at corners and dead-ends. A corner has only two neighbours, so the path is nearly forced through it; the question is which order. Parity-checking the remaining grid tells you which order is consistent and which would leave a parity mismatch (and thus an unreachable cell) at the end.

Corners first

Independent of parity, the second technique is to solve corners early. Each corner has exactly two neighbours, so the path through a corner must use both of those neighbours — one as the entry, one as the exit. This forces a specific local shape on the path. Identifying these forced segments at all four corners (or wherever the start is) before making any choices in the open middle removes a huge amount of degrees of freedom and prevents you from accidentally walling off a corner.

The Warnsdorff heuristic

For larger grids (6×6 and up), the most useful general technique is Warnsdorff's heuristic, originally developed for the Knight's Tour problem. The rule is: from your current position, always move to the unvisited neighbour that has the fewest unvisited neighbours of its own. In plain English: always move toward the most constrained cells first. This works because constrained cells (corners, narrow gaps) are harder to reach later — solving them early prevents stranding them.

Warnsdorff is a heuristic, not a guarantee; it occasionally fails. But it succeeds far more often than naïve play, and on the 4×4 and 5×5 grids of Path Find it almost always works. On the 6×6 grid (level 3 and beyond), about 90% of starts can be solved by Warnsdorff alone; the remaining 10% require explicit parity checking or back-tracking.

When to back up

If you have moved several cells and you suddenly notice that the un-visited region has split into two pieces, you have made a mistake. Back up to the step where the split happened. The path cannot enter both pieces — once you walled off one, you committed to visiting only the other, but you cannot visit cells you have already trapped behind your own line. The undo function exists specifically for this; do not start a new game, just back up to the wrong step.

Published · 14 May 2026 · Written and signed by Bill