Grid & Constraint Boards

Grids and game boards are backtracking with a shared board as the state. On a grid you walk from cell to cell and must not reuse a cell on the current path. On a board like N-Queens or Sudoku you place pieces and must keep every rule satisfied. Both follow the same rhythm: modify the board, recurse, then undo the move.

The idea#

These problems come in two shapes: walking a grid, and filling a board under rules. Both change the shared board before the recursive call and restore it after.

Grid DFS: mark, explore, unmark#

On a grid, a path may not visit the same cell twice, but a different path may. So "visited" belongs to the current path, not to the whole search:

Mark the cell before exploring its neighbors.
Try all 4 directions.
Unmark it on the way back, so other paths can use it.

The first step has 4 directions and every later step at most 3 (you can't step back onto the cell you came from). So a path of length L from each of the $R \cdot C$ start cells costs $O(R \cdot C \cdot 3^L)$ .

Constraint boards: sets instead of scans#

Before placing a piece, you need an is_valid check. Scanning the board costs $O(N)$ per check. Keeping a set of what each rule has already used makes it $O(1)$ .

For each rule, find a key that is the same for every cell the rule covers. A column's key is c. A diagonal or a box also has a key you can compute from (r, c); working it out is part of each problem. Add to the sets when you place a piece and remove from them when you undo it.

If you do scan instead, you only need to look upward (the same column and both upper diagonals): the rows below the current one are still empty.

Why it works: the board and the sets always describe exactly the pieces on the current path. Undoing a move restores them to the state the sibling branch expects.

How to spot it#

These cues point to grid or board backtracking.

"Find a path in the grid that spells…", "visit every empty cell exactly once".
"Place N pieces so that none attack each other".
"Fill the board so that every row, column and box…".
A small grid or board, where trying every placement is feasible.

Template#

Here is the constraint-board version. It places one piece per row and keeps one set per rule, so each check is $O(1)$ .

track(r):
    if r == n:                          # a piece in every row
        record the board
        return
    for c from 0 to n - 1:
        if any rule set already holds the key for (r, c):
            continue                    # attacked: O(1) check
        add the keys for (r, c) to every rule set
        place the piece at (r, c)
        track(r + 1)
        remove the piece from (r, c)    # undo every piece of state
        remove the keys from every rule set
track(0)

Grid DFS shape#

The grid version follows the same mark, explore, unmark rhythm, with the grid itself holding the visited marks. Check the cell before you mark it. Overwriting the cell with a marker such as "#" doubles as the visited mark, so no separate visited grid is needed.

dfs(r, c, i):
    if the path is complete: return True
    if (r, c) is off the grid or the cell does not match step i:
        return False
    save the cell, then overwrite it with "#"    # mark
    found = dfs on any of the 4 neighbors with i + 1
    restore the saved cell                       # unmark
    return found
try dfs(r, c, 0) from every cell

Stop at the first direction that succeeds (Python's any short-circuits).

Stop at the first solution#

The board template above records every solution. When the question wants only one filled board, make the recursive call return True on success. Write if track(next): return True so the search stops. Without the short-circuit, the search keeps going and undoes the finished board.

Pitfalls#

Shared board state is where these go wrong.

Forgetting to unmark. The next path then finds cells blocked that are free.
A global visited set. Visited must be scoped to the current path in grid backtracking.
Missing the success base case. When you fill a board, moving past the last cell means every cell is legal. Without "return True" there, the solver never stops cleanly.
Undoing only part of the state. Remove the piece from the board and from every constraint set.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Word Search and N-Queens.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Word Search

Use the grid DFS shape with i as the index into the word. The path is complete when i == len(word). Restore the cell to word[i] when you unmark it.

Hint: N-Queens

One queen per row, so rows need no set. Keep three sets: columns c, one diagonal keyed by r - c (constant along ↘) and the other keyed by r + c (constant along ↙).

Hint: N-Queens II

You need only the number of solutions. Increment a counter (or return 1) at the base case and drop the board entirely. The three sets are the whole state.

Hint: Sudoku Solver

Keep sets for each row, column and 3 × 3 box; the box index is (r // 3) * 3 + c // 3. Fill empty cells in order with digits 1 to 9. When the column passes 8, move to the next row; when the row passes 8, the board is solved, so return True and short-circuit.

Hint: Sudoku Solver: speed

The cost is $O(9^M)$ for M empty cells. Trying the most constrained cell first (the one with the fewest legal digits) usually finds the answer much faster.

Hint: Unique Paths III

A path counts only if it covers every non-obstacle cell exactly once. Count the free cells first. At the end cell, accept the path only if it has used all of them.

Key takeaways#

Modify the board, recurse, undo: the board is shared state.
Grid paths: mark before exploring, unmark after; a path of length L costs $O(R \cdot C \cdot 3^L)$ .
Constraint boards: one set per rule, keyed by a value constant along that rule's cells.
To stop at the first solution, return True and short-circuit the recursive call.
Most-constrained-first ordering speeds up constraint puzzles.

Core idea#

Grids and game boards are backtracking with a shared board as the state. Modify the board, recurse, then undo the move.

Key points#

Grid paths: mark the cell, try 4 directions, then unmark it. Other paths may reuse the cell.
Visited belongs to the current path, not the whole search.
Word Search is $O(R \cdot C \cdot 3^L)$ : 4 directions for the first letter, at most 3 after.
Overwrite the cell with "#" as the visited mark. No separate visited grid is needed.
Constraint boards keep sets of used values, so each validity check is $O(1)$ instead of $O(N)$ .
Sudoku: when the index moves past the last cell, return True. Write if track(next_cell): return True.
Sudoku costs $O(9^M)$ for M empty cells. Try the most constrained cell first.
N-Queens II counts solutions. The three sets are the whole state.

Constraint set keys#

Board	Constraint	Key
N-Queens	column	`c`
N-Queens	diagonal ↘	`r - c`
N-Queens	diagonal ↙	`r + c`
Sudoku	row, column	`r`, `c`
Sudoku	3 × 3 box	`(r // 3) * 3 + c // 3`

N-Queens needs no row set, because each row gets exactly one queen.

Template#

track(r):
    if r == n: count one solution; return
    for c from 0 to n - 1:
        if c in cols or r - c in diag or r + c in anti:
            continue
        add c, r - c, r + c to their sets
        track(r + 1)
        remove c, r - c, r + c from their sets
track(0)

Pitfalls#

Forgetting to unmark. Later paths find free cells blocked.
A global visited set in grid backtracking.
Missing the Sudoku success case, or not short-circuiting. The search then undoes the finished board.
Undoing only part of the state. Remove the piece from the board and from every set.

Say it in an interview#

"The board is shared state: modify, recurse, undo."
"Sets on column, r minus c and r plus c make each queen check O(1)."