A sudoku solver

In a sudoku, some cells of a 9 × 9 grid hold digits from the start, and you fill in the rest. Each row, each column and each of the nine 3 × 3 boxes must end up with all the digits from 1 to 9, none of them twice. A person looks for a cell where only one digit can go. A program can get away with far less thought: it guesses, and takes the guess back when it leads nowhere. One call of the solver does this:

1. Look for an empty cell. When there's none left, every cell holds a digit, and the puzzle is solved.
2. Collect the digits that are allowed in that cell: the ones its row, its column and its box don't have yet.
3. For each of them in turn, write it in the cell (choose) and call the solver on the grid as it is now (explore). If that call solves the puzzle, stop and report success.
4. Otherwise rub the digit out (un-choose) before trying the next one. If none of the digits leads to a solution, report failure (False) at once: some digit written earlier, in another cell, was wrong, and the call that wrote it goes on to its next digit.

Here is the whole recipe on a 4 × 4 sudoku, with the digits 1 to 4 and 2 × 2 boxes. The grid is a list of lists, with 0 for an empty cell:

def allowed(grid, row, col):
    used = set(grid[row])                          # the row
    used.update(grid[r][col] for r in range(4))    # the column
    top = row // 2 * 2
    left = col // 2 * 2
    for r in range(top, top + 2):                  # the box
        used.update(grid[r][left:left + 2])
    return [d for d in range(1, 5) if d not in used]


def solve(grid):
    for row in range(4):
        for col in range(4):
            if grid[row][col] == 0:
                for digit in allowed(grid, row, col):
                    grid[row][col] = digit         # choose
                    if solve(grid):                # explore
                        return True
                    grid[row][col] = 0             # un-choose
                return False                       # nothing fits here
    return True                                    # no empty cell: solved


grid = [[0, 0, 0, 0],
        [0, 1, 4, 0],
        [3, 0, 0, 2],
        [0, 0, 0, 0]]
print(solve(grid))
for line in grid:
    print(*line)

True
4 3 2 1
2 1 4 3
3 4 1 2
1 2 3 4

Only 4 digits are given, so the solver guesses a lot: it writes a digit 26 times and hits a dead end 14 times before every cell fits.

How it works

allowed collects the digits in the cell's row, column and box in a set. used.update(...) adds every item it's given to the set, as add does for one item. The 0s of the empty cells go in too, which does no harm: 0 is never a digit to try. The box of a cell starts at row row // 2 * 2 and column col // 2 * 2: // rounds down, so the rows 0 and 1 give 0, and the rows 2 and 3 give 2. On a 9 × 9 board the boxes are 3 × 3, so it's // 3 * 3, and cell (7, 4), in the eighth row and the fifth column, is in the box that starts at (6, 3):

>>> [row // 3 * 3 for row in range(9)]
[0, 0, 0, 3, 3, 3, 6, 6, 6]
>>> row, col = 7, 4
>>> row // 3 * 3, col // 3 * 3
(6, 3)

Two lines of solve are easy to get wrong:

• return False stands right after the loop over the digits, inside the if. Leave it out, and when nothing fits a cell, the loops go on to the next empty cell, and the return True at the end reports a grid with holes in it as solved.
• grid[row][col] = 0 is the un-choose. Leave it out, and a failed digit stays in its cell, so the search treats that cell as filled from then on.

Which empty cell first?

The recipe fills the empty cells in reading order, which can be a very bad order. A smarter solver first looks at every empty cell and takes the one with the fewest allowed digits. A cell with one allowed digit is a forced move, with no guessing. A cell with none means this branch is already dead, and the solver backs up at once, where the reading order might find out only millions of placements later. On a typical 9 × 9 puzzle with 56 empty cells, the reading order writes a digit 6,649 times; fewest-first writes 56, one per cell, with no wrong guess at all. On some puzzles the reading order needs tens of millions of placements, minutes of Python, and fewest-first still needs about 60.

What it costs

Checking a digit looks at the 27 cells of a row, a column and a box: on a 9 × 9 board that's O(1). What can explode is the number of placements: in the worst case, the search tries every digit in every empty cell, exponential in the number of empty cells. The givens and good choices prune nearly all of it. The recursion goes one call deeper per filled cell, at most 81, far from Python's limit.