Checkerboard parity

Shade the board like a checkerboard and you get a counting rule that every full-fill square board has to obey. It rarely hands you a move on a well-made puzzle. It does catch most misplaced dots at a glance, and mid-solve it can kill a bad move without playing it out.

Every step changes shade

Call the top-left cell dark. A cell is dark when its row number plus its column number is even, and light when the sum is odd. A step up, down, left or right changes exactly one of those numbers by one, so every step lands on the other shade. A path reads dark, light, dark, light, all the way along.

That fixes the length of any path from its two dots:

• Both dots on the same shade: the path covers an odd number of cells, with one more cell of the dots' shade than of the other.
• Dots on different shades: the path covers an even number of cells, split evenly.

Two dots that touch diagonally sit on the same shade, so the path between them needs at least 3 cells, and can only ever be 3, 5, 7 or some other odd length. Two dots side by side are on different shades, so any route between them covers an even number of cells.

The whole-board count

On a full-fill board every cell belongs to exactly one path. Add up what each path contributes. A pair on two dark squares adds one extra dark cell, a pair on two light squares adds one extra light cell, and a mixed pair adds nothing. Over the whole board that gives one equation.

dark cells minus light cells = pairs on two dark squares minus pairs on two light squares.

On a plain rectangle that gives two quick rules:

• If the board has an even number of cells (6×6, 8×8, 5×6), the shades are equal, so the board has as many dark-dark pairs as light-light pairs.
• If both sides are odd (5×5, 7×7, 9×9), the corners are dark and there is one extra dark cell, so there is exactly one more dark-dark pair than light-light pairs. At least one pair has to sit on two dark squares.

Check it against the solution above. The 5×5 board has 13 dark cells and 12 light ones. Blue runs from row 1, column 1 (dark) to row 5, column 4 (light) in 8 cells. Orange (4 cells), Green (6) and Red (4) also join a dark square to a light one. Purple joins row 4, column 4 to row 5, column 5, both dark, in 3 cells. That one odd path is the board's whole surplus.

A board that fails the count

Now move a single Purple dot one cell to the right, from row 4, column 4 to row 4, column 5.

Purple's dots are now on a light square and a dark square. No pair sits on two dark squares, so the paths can only cover equal numbers of each shade, and the board has one dark cell too many. You could try routes for an hour and never fill it. The Python solver that checks every board on this site does this count before it searches, and rejects a board like this for breaking the "full-cover bipartite endpoint balance."

The same thing happens whichever dot you move. Moving any one dot a single step puts it on the other shade, which changes the right-hand side of the count by exactly one. A board that balanced before can't balance after.

Holes change the count

A hole removes a cell from its shade's total, so the target changes. Take the broken board above and punch a hole in the center cell, row 3, column 3, which is dark.

Now the board has 12 dark and 12 light cells, so the count asks for equal numbers of dark-dark and light-light pairs. Zero and zero is fine, and the board has a solution. Red bends around the hole through row 4, column 4, and Purple simply joins its two adjacent dots.

Two things to keep in mind with holes:

• Recount the shades every time. A hole on a light cell of the 5×5 would leave 13 dark and 11 light, and the board would need two more dark-dark pairs than light-light ones.
• If holes split the board into separate pieces, each piece has to balance on its own, using only the pairs inside it.

Passing the count proves nothing by itself. Put the hole in row 1, column 3 instead (also dark) and the count still balances, but that board has no solution. Parity rules boards out. It never rules them in.

Using it while you solve

Check the setup. Before working a puzzle you copied by hand or imported from a screenshot, count the pairs by shade. If the count fails, a dot is in the wrong place, very often one cell off. It takes a minute on a 9×9 and saves a long, hopeless solve.

Test a sealed area. The count works on any part of the board that has to be finished by the paths already inside it. Mid-solve, pick an area that has been closed off. Count its empty cells plus the tips and dots of the unfinished paths in it. Each of those colors has to run from tip to tip through that area, so the area's dark-minus-light difference must equal its dark-dark tip pairs minus its light-light tip pairs. If it doesn't, the position is dead and an earlier move was wrong. This is a fast way to reject a move when thinking ahead, because you can see the failure without drawing the forced moves.

Pockets with one color. If a single color has to fill a pocket in one stretch, the pocket's shades fix where that stretch can start and end. The ends are the cells where the path crosses into or out of the pocket, or a dot inside it. A pocket with equal dark and light cells needs one end on each shade. A pocket with one extra dark cell needs both ends on dark cells. A 3×3 pocket has five cells of its corner shade (the four corners and the center) and four of the other, so a path that crosses in and out has to do it at the pocket's corners, never at the middle of a side. That often leaves only one way in.

Where it doesn't apply

The rule needs a square grid where every cell is filled once. On hexagonal boards three cells can touch each other, so there is no checkerboard to draw. A bridge cell can carry two paths at once. A warp that joins two cells of the same shade, such as the two ends of a row on a five-wide board, breaks the alternation too. On those boards, count something else.