Sudoku Solver

▶

Steps

setup

Initialize constraint sets and empty cells list

Scan the board to fill sets for rows, columns, and boxes with existing digits, and collect coordinates of empty cells.

💡 This step sets up the data structures that track which digits are already used in each row, column, and box, enabling quick validity checks later.

Line:

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empties = []

💡 Tracking constraints upfront allows the solver to efficiently check candidate digits without scanning the board repeatedly.

choose

Identify first empty cell and compute candidates

Sort empty cells by number of valid candidates and select the most constrained cell to fill next.

💡 Choosing the cell with the fewest candidates reduces branching and speeds up solving by tackling the hardest spots first.

Line:

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
r, c = empties.pop(0)

💡 The heuristic prioritizes cells that limit choices most, pruning the search tree effectively.

insert

Try candidate '1' in cell (0,2)

Place digit '1' in cell (0,2), update constraint sets, and recurse deeper.

💡 Trying a candidate involves updating the board and constraints to reflect the choice before recursive exploration.

Line:

board[r][c] = ch
rows[r].add(ch)
cols[c].add(ch)
boxes[b].add(ch)

💡 This step shows how the algorithm tentatively commits to a choice and prepares to explore consequences.

choose

Recurse to next empty cell after placing '1'

After placing '1', sort remaining empties and pick the next most constrained cell to fill.

💡 Each recursive call repeats the heuristic to pick the next cell with fewest candidates, narrowing the search.

Line:

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
r, c = empties.pop(0)

💡 The recursion tree deepens by choosing the next cell to fill based on updated constraints.

compare

Try candidate '1' in cell (0,3) - conflict detected

Attempt to place '1' in cell (0,3), but '1' already exists in column 3, so this candidate is invalid.

💡 Constraint checks prevent invalid placements, pruning branches early to avoid wasted work.

Line:

for ch in get_candidates(r, c):

💡 This step demonstrates how the algorithm uses constraint sets to quickly detect invalid moves.

insert

Try candidate '2' in cell (0,3)

Place digit '2' in cell (0,3), update constraints, and recurse deeper.

💡 Valid candidate placement extends the partial solution and constraint sets accordingly.

Line:

board[r][c] = ch
rows[r].add(ch)
cols[c].add(ch)
boxes[b].add(ch)

💡 This step shows the algorithm continuing exploration with a valid candidate.

backtracking

Backtrack after no candidates fit further down

Deeper recursion fails to find valid candidates for next cells, so algorithm backtracks by removing '2' from (0,3).

💡 Backtracking reverts changes to try alternative candidates, enabling exhaustive search.

Line:

board[r][c] = '.'
rows[r].remove(ch)
cols[c].remove(ch)
boxes[b].remove(ch)

💡 Backtracking is essential to undo choices that lead to dead ends.

insert

Try candidate '4' in cell (0,3)

Place digit '4' in cell (0,3), update constraints, and recurse deeper.

💡 Trying next candidate after backtracking continues the search for a valid solution.

Line:

board[r][c] = ch
rows[r].add(ch)
cols[c].add(ch)
boxes[b].add(ch)

💡 The algorithm systematically explores all candidates for each cell.

traverse

Continue recursion until all empties filled

The algorithm continues recursively filling cells with valid candidates, backtracking as needed, progressing deeper.

💡 This phase shows the core recursive exploration of the solution space, building partial answers stepwise.

Line:

if backtrack():
    return True

💡 The recursion tree grows as the algorithm tries candidates and backtracks on failure.

reconstruct

All empty cells filled - solution found

No empty cells remain, so the algorithm returns True, signaling a complete valid solution has been found.

💡 Reaching this base case means the Sudoku board is fully and correctly filled.

Line:

if not empties:
    return True

💡 The recursion terminates successfully when all constraints are satisfied and the board is complete.

def solveSudoku(board):
    rows = [set() for _ in range(9)]  # STEP 1
    cols = [set() for _ in range(9)]  # STEP 1
    boxes = [set() for _ in range(9)]  # STEP 1
    empties = []  # STEP 1

    for i in range(9):  # STEP 1
        for j in range(9):  # STEP 1
            if board[i][j] == '.':
                empties.append((i,j))
            else:
                val = board[i][j]
                rows[i].add(val)
                cols[j].add(val)
                boxes[(i//3)*3 + j//3].add(val)

    def get_candidates(r, c):
        b = (r//3)*3 + c//3
        return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

    def backtrack():
        if not empties:  # STEP 10
            return True
        empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))  # STEP 2,4,9
        r, c = empties.pop(0)  # STEP 2,4,9
        b = (r//3)*3 + c//3
        for ch in get_candidates(r, c):  # STEP 3,5,6,8
            board[r][c] = ch
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
            if backtrack():  # STEP 9
                return True
            board[r][c] = '.'  # STEP 7
            rows[r].remove(ch)
            cols[c].remove(ch)
            boxes[b].remove(ch)
        empties.insert(0, (r, c))
        return False

    backtrack()  # STEP 1

📊

Sudoku Solver - Watch the Algorithm Execute, Step by Step

Watching each choice and backtrack visually reveals how the algorithm prunes invalid paths early and efficiently fills the Sudoku grid, which is hard to grasp from code alone.

entering

Call Path (current → root)

backtrack()

choosing

Call Path (current → root)

backtrack()

Remaining

124

entering

Call Path (current → root)

backtrack()

backtrack()

Partial: [(0,2)=1]

choosing

Call Path (current → root)

backtrack()

backtrack()

Remaining

124

Partial: [(0,2)=1]

pruning

Call Path (current → root)

backtrack()

backtrack()

Tried

1

Remaining

24

Partial: [(0,2)=1]

✂ Digit '1' conflicts with column 3

entering

Call Path (current → root)

backtrack()

backtrack()

backtrack()

Partial: [(0,2)=1, (0,3)=2]

backtracking

Call Path (current → root)

backtrack()

backtrack()

backtrack()

Tried

2

Partial: [(0,2)=1]

entering

Call Path (current → root)

backtrack()

backtrack()

backtrack()

Partial: [(0,2)=1, (0,3)=4]

choosing

Call Path (current → root)

...

backtrack()

backtrack()

backtrack()

Partial: [(0,2)=1, (0,3)=4, ...]

backtracking

Call Path (current → root)

backtrack()

...

backtrack()

backtrack()

backtrack()

Found 1: [5,3,4,6,7,8,9,1,2,6,7,2,1,9,5,3,4,8,1,9,8,3,4,2,5,6,7,8,5,9,7,6,1,4,2,3,4,2,6,8,5,3,7,9,1,7,1,3,9,2,4,8,5,6,9,6,1,5,3,7,2,8,4,2,8,7,4,1,9,6,3,5,3,4,5,2,8,6,1,7,9]

Key Takeaways

✓ The heuristic of choosing the most constrained empty cell first drastically reduces the search space.

This insight is difficult to see from code alone because the sorting and candidate counting happen implicitly and recursively.

✓ Backtracking systematically explores all candidate digits for each cell, undoing invalid choices to find the unique solution.

Watching the recursion tree reveals the depth-first search nature and how backtracking prunes invalid paths early.

✓ Constraint sets for rows, columns, and boxes enable quick validity checks, avoiding expensive board scans.

This optimization is subtle in code but critical for performance and is clearly visible in the visualization as pruning decisions.