Skip to content
Tutorials Center
My learning

Topics

Lesson 66 of 225 ยท Recursion and Backtracking

Sudoku and Constraint Puzzles

Solve constraint puzzles with backtracking in Python: a fast Sudoku solver with row, column and box sets, word search in a grid, rat in a maze and the knight's tour.

N-Queens showed the core of constraint solving: place one piece at a time, reject placements that break a rule, and undo them when you hit a dead end. Real puzzles such as Sudoku, mazes and word searches are the same idea with more rules and a bigger board. The difference between a solver that finishes in a blink and one that runs for hours is almost always how cleverly you choose the next decision and how cheaply you check a rule.

In this lesson you will build a complete Sudoku solver, then reuse the same template for a word search, a maze and the knight's tour. Along the way you will meet the two most useful tricks in constraint solving: keeping the used values in sets so a check costs O(1), and always branching on the most constrained choice first.

The constraint-puzzle template

Every puzzle in this lesson fits the backtracking template:

TEXT
solve(state):
    if state is complete:       return True
    pick an undecided variable  (a cell, a step...)
    for each candidate value that breaks no rule:
        apply it
        if solve(state): return True
        undo it                 # backtrack
    return False

Three things decide the speed:

  1. Rule checks should be O(1). Keep sets or boolean tables of what is already used instead of rescanning the board.
  2. Variable order: pick the cell with the fewest legal candidates first. A cell with one candidate is not a guess at all, and a cell with zero candidates tells you at once that this branch is dead.
  3. Pruning: reject a branch as early as you can.

Sudoku: the rules as sets

A Sudoku board is 9x9. Each row, each column and each of the nine 3x3 boxes must contain the digits 1 to 9 exactly once. A cell at row r, column c belongs to box number (r // 3) * 3 + c // 3:

TEXT
box numbers
 0 0 0 | 1 1 1 | 2 2 2
 0 0 0 | 1 1 1 | 2 2 2
 0 0 0 | 1 1 1 | 2 2 2
 ------+-------+------
 3 3 3 | 4 4 4 | 5 5 5
 ...

The legal candidates for an empty cell are the digits not yet used in its row, its column or its box. If we store three lists of sets, rows[r], cols[c] and boxes[b], the candidates are one set operation:

Python
candidates = set(range(1, 10)) - rows[r] - cols[c] - boxes[b]
Python Candidates for one empty cell

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A simple Sudoku solver

First the plain version: scan for the next empty cell in reading order, try each candidate, recurse, undo.

TEXT
fill cell (0,2): try 1 -> recurse...
                 try 2 -> recurse...  (dead end, undo)
                 try 4 -> recurse...  (works)
Python Sudoku solver: first empty cell

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This works and the recursion is only as deep as the number of empty cells (at most 81), well within Python's limit. Notice the undo step: every add has a matching remove. Forgetting one is the most common bug in backtracking solvers, because the board then "remembers" digits from dead branches.

Choosing the most constrained cell

Reading order is arbitrary. A smarter solver picks, at each step, the empty cell with the fewest candidates. This is called the minimum remaining values (MRV) heuristic. It helps in two ways: cells with one candidate are filled for free (no branching), and cells with zero candidates make the branch fail immediately, before you waste time deeper in the tree.

Python Sudoku solver with the MRV heuristic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The call counts show the effect: reading order needs 4,209 calls on the easy puzzle against 52 for MRV, and on the hard puzzle (designed to be awkward for plain backtracking) it needs 475,306 against 1,146. The MRV version spends a little more work per call (it scans for the best cell) and wins by an enormous margin overall. That trade, a bit more thinking per node for a much smaller tree, is the heart of constraint solving.

Most real solvers add constraint propagation: when you place a digit, immediately remove it from the candidates of its peers, and if a cell is left with a single candidate, place it too. MRV gets part of that benefit with far less code.

Word search in a grid

Problem. Given a grid of letters and a word, decide whether the word can be traced by moving up, down, left or right between adjacent cells, using each cell at most once.

Brute force. Enumerate every path of the right length and compare: far too many paths.

Backtracking. Try each cell as the start. From a cell that matches the current letter, mark it used, try the four neighbours for the next letter, then unmark it. A wrong letter prunes the whole branch immediately.

TEXT
grid        word = "SEE"
 A B C E     start at (1,3) 'S' -> (0,3) 'E' -> ... needs another 'E' adjacent
 S F C S     start at (1,3) 'S' -> (2,3) 'E' -> (2,2) 'E'   found
 A D E E
Python Word search with backtracking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the word has length L, each step has at most 3 new directions (you cannot go back to where you came from), so the search is O(R x C x 3^L) in the worst case, with O(L) recursion depth plus the O(R x C) used table. A useful speed-up: if the word's first letter is rarer than its last in the grid, search for the reversed word.

Rat in a maze

Problem. A grid has open cells (0) and walls (1). Starting at the top-left, find a path to the bottom-right moving right or down only.

This is a path-finding backtrack: step into an open cell, mark it as part of the path, try to go on, and unmark it on failure. Because we only move right or down, we never revisit a cell and need no visited table, but a maze that allows all four directions needs one (and for the shortest path you should use breadth-first search, not backtracking).

Python Rat in a maze: all paths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The knight's tour

A knight must visit every square of a board exactly once using L-shaped moves. Plain backtracking explores a gigantic tree. A famous heuristic, Warnsdorff's rule, says: from the current square, always move to the neighbour that has the fewest onward moves. It is the MRV idea again: visit the hard-to-reach squares first before they become dead ends. The rule is a heuristic with no guarantee, so we add backtracking as a safety net.

Python Knight's tour with Warnsdorff's rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Puzzle Worst case Why
Sudoku (9x9) exponential in empty cells up to 9 choices per empty cell, but pruning makes it fast in practice
Word search O(R x C x 3^L) each step has about 3 new directions
Rat in a maze (right/down) O(2^(2n)) each step branches into 2, about 2n steps
Knight's tour exponential with Warnsdorff the search usually never backtracks

Sudoku boards generalise to n x n x n x n grids, and that version is NP-complete (see P, NP and hard problems). The 9x9 case stays easy only because 9 is small and the pruning is strong.

Common mistakes

  • Forgetting to undo one of the structures you updated (set, board cell, used flag). Always pair each change with its reverse.
  • Checking rules by rescanning the row, column and box every time. Sets make the check O(1).
  • Modifying the input (the original board) and then trying to reuse it. Copy first, or restore it.
  • Returning a result too late. Return True as soon as one solution is found, or you will keep exploring.
  • Using backtracking where BFS fits. Backtracking finds a path, not the shortest.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which expression gives the box number of the Sudoku cell in row r and column c?

    Integer division by 3 gives the box row and box column; multiplying the box row by 3 and adding the box column numbers the nine boxes 0 to 8.
  2. 2. What does the MRV heuristic choose next?

    Choosing the most constrained cell exposes dead ends early and fills forced cells without branching, which shrinks the search tree.
  3. 3. Why does word search unmark a cell after exploring from it?

    A cell may be used only once per path, not once per search. Undoing the mark lets a different path through the same cell succeed.
  4. 4. Warnsdorff's rule moves the knight to the neighbour with:

    Visiting the squares that are hardest to reach first stops them from becoming isolated dead ends later in the tour.
  5. 5. Why use sets for row, column and box contents in a Sudoku solver?

    Membership in a set is O(1) on average, so checking a candidate against its row, column and box takes constant time.

Summary

  • Constraint puzzles are backtracking: choose, check the rules, recurse, undo.
  • Keep used values in sets or tables so rule checks are O(1).
  • Branch on the most constrained variable first (MRV); it can cut the search tree by orders of magnitude.
  • Word search and maze path-finding mark cells on the way in and unmark them on the way out.
  • Warnsdorff's rule is a heuristic for the knight's tour; backtracking remains the safety net.
  • Backtracking finds a solution; use BFS when you need the shortest path.

Next: Meet in the Middle and Branch and Bound