Sudoku Solver

#How does it work?

Sudoku is one of the most familiar examples of backtracking. In an n × n grid every row, column and box must hold the digits 1 to n exactly once. This lesson uses a 4 × 4 puzzle with 2 × 2 boxes so the animation stays readable; the method is the same for 9 × 9.

The algorithm finds the first empty cell and tries the digits 1, 2, … in turn. A digit already in the same row, column or box is skipped. A digit that fits is written in and the search moves to the next empty cell.

If no digit fits a cell, an earlier choice was wrong: the last digit written is erased and the next digit is tried there. The example puzzle has exactly one solution and needs two backtracks on the way.

#Try it yourself

#Step by step

1. 01Find the first empty cell; if there is none, the puzzle is solved.
2. 02Try the digits 1 to n in that cell.
3. 03If a digit respects the row, column and box rules, write it and move to the next empty cell.
4. 04If no digit fits, go back: erase the previous cell's digit and try its next digit.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

N, BOX = 4, 2  # a 4 x 4 puzzle with 2 x 2 boxes; the same code solves 9 x 9 with N, BOX = 9, 3

grid = [
    [0, 0, 0, 0],
    [0, 0, 1, 2],
    [2, 0, 0, 4],
    [0, 4, 0, 0],
]


def fits(r: int, c: int, d: int) -> bool:
    if d in grid[r] or any(grid[k][c] == d for k in range(N)):
        return False
    br, bc = r - r % BOX, c - c % BOX
    return all(grid[br + i][bc + j] != d for i in range(BOX) for j in range(BOX))


def solve() -> bool:
    for r in range(N):
        for c in range(N):
            if grid[r][c] == 0:  # the first empty cell
                for d in range(1, N + 1):
                    if fits(r, c, d):
                        grid[r][c] = d
                        if solve():
                            return True
                        grid[r][c] = 0  # dead end: backtrack
                return False
    return True  # no empty cell left


solve()
for row in grid:
    print(" ".join(map(str, row)))

#Complexity

In theory it is exponential; in practice the rules prune branches so early that 9 × 9 puzzles are solved in milliseconds. Filling the cell with the fewest options first (the MRV heuristic) and keeping sets of used digits per row/column/box speed the search up a lot.

#When to use it?

Sudoku and similar puzzles (KenKen, Kakuro), constraint satisfaction problems, timetables and exam schedules, graph colouring and resource assignment are all solved with the same "try, check, undo if needed" pattern.

#Practice

Log in to answer questions and save your progress.