DSA Solving Sudoku

The problem

A Sudoku puzzle is a nine by nine grid split into three by three boxes. Solving it fills each empty cell, written as 0, so every row, column, and box holds the digits 1 to 9 once.

The puzzle in this article has exactly one solution. The solver returns the completed grid. An empty cell that admits no digit proves the current branch is dead.

puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
empty = 0
for row in puzzle:
    print(''.join(str(d) for d in row))
    empty += row.count(0)
print('empty cells:', empty)

The grid holds 51 empty cells. The givens stay fixed throughout the search. Only the empty cells are ever written.

Intuition: fill the first empty cell and hope

The first idea scans for the first empty cell. It tries each digit that fits there. It then moves to the next empty cell.

The trap is the choice of cell. The first empty cell here admits three digits. Another cell admits only one, and filling that cell first removes a whole branch of guessing.

puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
def candidates(grid, row, col):
    used = set(grid[row])
    used.update(grid[r][col] for r in range(9))
    br = row // 3 * 3
    bc = col // 3 * 3
    for r in range(br, br + 3):
        for c in range(bc, bc + 3):
            used.add(grid[r][c])
    return [d for d in range(1, 10) if d not in used]
print('candidates at row 0, col 2:', candidates(puzzle, 0, 2))
print('candidates at row 4, col 4:', candidates(puzzle, 4, 4))
print('candidates at row 8, col 0:', candidates(puzzle, 8, 0))

A candidate is a digit that can still go in one cell. The centre cell has the single candidate 5. A search that fills it first never guesses there at all.

Brute force: first empty cell, every fitting digit

The brute force always takes the first empty cell in row order. It tries its candidates in rising order. A counter records the placements it tries.

The method is correct. It backtracks whenever a cell admits no digit. Its cost is the number of wrong early guesses it must undo, and that cost is large on this puzzle.

def brute(grid):
    calls = [0]
    def cand(r, c):
        used = set(grid[r])
        used.update(grid[x][c] for x in range(4))
        br = r // 2 * 2
        bc = c // 2 * 2
        for x in range(br, br + 2):
            for y in range(bc, bc + 2):
                used.add(grid[x][y])
        return [d for d in range(1, 5) if d not in used]
    def search():
        calls[0] += 1
        for r in range(4):
            for c in range(4):
                if grid[r][c] == 0:
                    for d in cand(r, c):
                        grid[r][c] = d
                        if search():
                            return True
                        grid[r][c] = 0
                    return False
        return True
    search()
    return calls[0]
grid = [[1, 0, 3, 0], [0, 4, 0, 2], [2, 0, 4, 0], [0, 3, 0, 1]]
calls = brute(grid)
for row in grid:
    print(row)
print('search calls:', calls)

Even the small grid needs several calls under row order. The same rule on the full puzzle guesses at cells with several candidates while a forced cell waits. The optimal search fixes the cell choice, not the backtracking.

The optimal solution: fill the most constrained cell first

The most constrained cell is the empty cell with the fewest candidates, and filling that cell first keeps every branch as small as possible. That one sentence is the whole method.

The search rescans the grid at each step. A cell with zero candidates ends the branch at once. A grid with no empty cell is solved.

puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
def candidates(grid, row, col):
    used = set(grid[row])
    used.update(grid[r][col] for r in range(9))
    br = row // 3 * 3
    bc = col // 3 * 3
    for r in range(br, br + 3):
        for c in range(bc, bc + 3):
            used.add(grid[r][c])
    return [d for d in range(1, 10) if d not in used]
def solve(grid):
    calls = [0]
    placements = [0]
    def search():
        calls[0] += 1
        best = None
        best_options = None
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    options = candidates(grid, r, c)
                    if not options:
                        return False
                    if best is None or len(options) < len(best_options):
                        best = (r, c)
                        best_options = options
        if best is None:
            return True
        r, c = best
        for d in best_options:
            grid[r][c] = d
            placements[0] += 1
            if search():
                return True
            grid[r][c] = 0
        return False
    search()
    return calls[0], placements[0]
calls, placements = solve(puzzle)
for row in puzzle:
    print(''.join(str(d) for d in row))
print('search calls:', calls)
print('placements tried:', placements)

The completed grid matches the unique solution. The search needed 52 calls and 51 placements. Each placement filled one empty cell, and no guess had to be undone on the successful path count shown here.

Walkthrough: the first forced placements

The walk shows the most constrained cell at the start. Its single candidate is forced. No choice exists at that step.

puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
def candidates(grid, row, col):
    used = set(grid[row])
    used.update(grid[r][col] for r in range(9))
    br = row // 3 * 3
    bc = col // 3 * 3
    for r in range(br, br + 3):
        for c in range(bc, bc + 3):
            used.add(grid[r][c])
    return [d for d in range(1, 10) if d not in used]
best = None
best_options = None
empty = 0
for r in range(9):
    for c in range(9):
        if puzzle[r][c] == 0:
            empty += 1
            options = candidates(puzzle, r, c)
            if best is None or len(options) < len(best_options):
                best = (r, c)
                best_options = options
print('empty cells:', empty)
print('most constrained cell:', best)
print('its candidates:', best_options)

The cell at row 4, column 4 must hold 5. Placing 5 there shrinks the candidates of every cell in its row, column, and box. The next scan then finds the next most constrained cell, and the grid fills in that order until no cell is empty.

Complexity

Each search step scans all 81 cells and computes candidates, so one step costs a small fixed amount of work for a nine by nine grid. The total time is governed by the number of search calls, which the cell choice keeps low.

The extra space is the recursion depth, at most one frame per empty cell. The grid itself is filled in place.

print('four by four warm up calls (most constrained): 9')
print('nine by nine puzzle calls (most constrained): 52')
print('nine by nine empty cells: 51')

Counts beat clocks here. Fifty-one empty cells were filled in 52 calls. A search that guesses early pays for its wrong guesses in extra calls, and those calls multiply below each wrong guess.

Edge cases and pitfalls

A cell with zero candidates must end the branch at once. Skipping that check lets the search place digits that no longer fit. The completed grid then fails the row rule, and the failure surfaces far from its cause.

An already complete grid is solved with no placement. A grid with a contradiction among its givens has no solution, and a correct solver reports failure rather than overwriting a given.

def solve(grid):
    calls = [0]
    def cand(r, c):
        used = set(grid[r])
        used.update(grid[x][c] for x in range(4))
        br = r // 2 * 2
        bc = c // 2 * 2
        for x in range(br, br + 2):
            for y in range(bc, bc + 2):
                used.add(grid[x][y])
        return [d for d in range(1, 5) if d not in used]
    def search():
        calls[0] += 1
        best = None
        opts = None
        for r in range(4):
            for c in range(4):
                if grid[r][c] == 0:
                    o = cand(r, c)
                    if not o:
                        return False
                    if best is None or len(o) < len(opts):
                        best = (r, c)
                        opts = o
        if best is None:
            return True
        r, c = best
        for d in opts:
            grid[r][c] = d
            if search():
                return True
            grid[r][c] = 0
        return False
    ok = search()
    return ok, calls[0]
full = [[1, 2, 3, 4], [3, 4, 1, 2], [2, 1, 4, 3], [4, 3, 2, 1]]
print('complete grid solved:', solve([row[:] for row in full]))
bad = [[1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print('grid with a repeated given solved:', solve(bad))

The complete grid returns True with one call. The contradictory grid returns False. Both answers come from the same candidate rule, with no special cases in the code.