Backtracking on a grid

Key idea

The choice is a direction

On a grid, each level of the search steps to a neighboring cell. The four directions are the branches, and the cell being stood on has to be marked so the path does not immediately walk back over itself.

The mark is temporary. When the search returns from a cell, that cell becomes available again for other paths, which is exactly the undo step.

Why it works

Restore the original, not a blank

The cell's previous contents are saved before marking and put back after. Writing a fixed value back instead would destroy the board.

The final print exists to check exactly that: after the search completes, the grid is identical to what was passed in. Any search that mutates its input should leave it as it found it, and printing the input afterward is a cheap way to verify it.

Key idea

Why the unmark makes this different from a flood fill

Unit 12 will use almost identical code to explore connected regions, and in that setting cells are marked visited and never unmarked, because visiting a cell once is enough to know it belongs to the region.

Here every distinct path matters, so a cell used by one path must be free for another. That single difference, whether the mark is permanent or undone, is what separates a traversal from a search.

It is also the difference in cost. A traversal touches each cell once and is linear. This search can visit a cell once per path through it, and is exponential.