Sudoku by Backtracking

1A board is a partial assignment

A Sudoku state is a grid with some cells filled and some empty. The filled cells are the assignment so far. The empty cells are the remaining variables. A digit is legal in a cell when it does not already appear in that cell's row, or column, or box. The goal test is 'no empty cells left' — every variable has a value, and every placement was legal when it was written, so the finished grid is a solution.

The campus running board is 4×4 with eight givens. Boxes are the four 2×2 corners. Digits run from 1 to 4. A 9×9 board is the same story with 3×3 boxes and digits 1 to 9. Nothing about the search changes except the size of a box and the length of a domain.

Figure. The campus 4×4. Givens are the numbered cells. Dots are empty variables. Terracotta marks the empties — they are the work, not errors. Box boundaries are the four 2×2 corners; the renderer does not draw a heavy box line, so read them as top-left 1 and 4, top-right 4 and 1, and so on.

2Pick the emptiest cell

Any empty cell is a legal next variable. The cheap habit from Graph Colouring as Search is to pick the cell whose domain is smallest — fewest legal digits right now. A cell with one legal digit is a forced write. A cell with four legal digits is a guess that may have to be undone. Trying the forced write first shrinks other domains before you guess.

On the campus board the first empty cell, row 0 column 1, has only one legal digit: 2. Row 0 already holds 1 and 4, its box already holds 1, and column 1 already holds 4 and 3 — the only survivor is 2. Scanning empties in reading order happens to find that cell first; on a 9×9 board, reading order is a worse heuristic than 'fewest candidates'.

3Write, recurse, clear

The loop is the colouring loop with a grid instead of a map. Find an empty cell. For each legal digit, write it, recurse, and if the recursive call fails, clear the cell and try the next digit. If no digit works, return failure so the caller can undo its own write. Depth-First Search and Iterative Deepening called this the current path as the current partial assignment. The board is that path.

Clearing the cell is the undo. A version that copies the whole grid on every try is correct and slower; a version that writes in place and clears on the way back is the one you implement. Do not skip the clear. A leftover digit from a dead branch is a false given, and every later legality check will treat it as a fact.

One cell

1. Find emptyScan for a zero, or pick the cell with the fewest legal digits.
2. Try a digitIf it is missing from the row, column and box, write it and recurse.
3. Clear on failPut a zero back. A leftover digit from a dead branch becomes a fake given.

4Filling the campus 4×4

Scan empties in reading order and write the first legal digit. Row 0 column 1 accepts only 2. Row 0 column 2 then accepts only 3, and the first row is 1, 2, 3, 4. Row 1 column 0 accepts only 3. Each of those writes is forced — the domain had one digit. The remaining empties fill the same way on this board: the puzzle was built to have one solution, so a legal walk never has to undo.

A harder 4×4, or any 9×9 that is not a 'gentle' puzzle, will guess and undo. The ledger below is the forced prefix, not a claim that Sudoku never backtracks.

Figure. The unique completion. Sage cells were empty on the start board and are now filled. Neutral cells are the original givens. Read rows 1 2 3 4, then 3 4 1 2, then 2 1 4 3, then 4 3 2 1.

5A solver that does not care about 4 or 9

The listing takes a square board of side n^2 with n \times n boxes. For the campus board n = 2. For a newspaper Sudoku n = 3. `find_empty` returns the first zero. `legal` checks the three uniqueness constraints. `solve` writes a candidate, recurses, and clears on failure. When `find_empty` returns None the board is full and the call returns True.

This is the Python-lab Sudoku experiment. It is not a dancing-links solver and it is not a SAT encoding. It is the colouring search pointed at a grid.

Figure. The listing takes a board of side n² with n × n boxes: n = 2 on the campus board, n = 3 on a newspaper Sudoku. A digit dies if it already sits in the row, the column, or the n×n box. solve writes a candidate, recurses, and clears the cell back to 0 on failure.

What the listing does

1. LegalA digit dies if it already sits in the row, the column, or the n×n box.
2. Write and recursefind_empty returns the first zero. solve writes a candidate and calls itself.
3. ClearOn failure the cell goes back to 0. A leftover digit is a fake given.

Sudoku, in-place backtracking

def legal(board, r, c, v, n=2):
    N = n * n
    if v in board[r] or v in (board[i][c] for i in range(N)):
        return False
    br, bc = n * (r // n), n * (c // n)
    for i in range(br, br + n):
        for j in range(bc, bc + n):
            if board[i][j] == v:
                return False
    return True

def find_empty(board):
    for i, row in enumerate(board):
        for j, v in enumerate(row):
            if v == 0:
                return i, j
    return None

def solve(board, n=2):
    spot = find_empty(board)
    if spot is None:
        return True
    r, c = spot
    for v in range(1, n * n + 1):
        if legal(board, r, c, v, n):
            board[r][c] = v
            if solve(board, n):
                return True
            board[r][c] = 0
    return False

Coding lab. Solve the campus 4×4 runs in the app, with checks on your output.

69×9 is n = 3

Change n from 2 to 3 and the same three functions solve a newspaper Sudoku. The domain becomes 1..9, the box is 3×3, the board is 9×9. The choose–try–undo loop does not grow a new case. What grows is the branching: a first empty with six candidates is six recursive calls, and a gentle 9×9 still finishes because most cells are forced after a few writes.

Reach for a fancier solver — dancing links, a SAT encoding, constraint-propagation queues beyond forward checking — when the puzzle is designed to defeat naked backtracking, or when you need every solution counted. For the lab experiment, n = 2 on the campus board and n = 3 on a published easy 9×9 are the same program.