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.

Practice

1. Consider the following Python code implementing the bitmask backtracking solution for N-Queens II. What is the final return value of totalNQueens(4)?

easy

A. 2

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace initial call for n=4

   Start with row=0, no columns or diagonals occupied, all 4 columns available.

2. Step 2: Count valid placements recursively

   Backtracking explores all valid queen placements; for n=4, there are exactly 2 distinct solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known result for 4-queens is 2 solutions [OK]

Hint: 4-queens has 2 solutions; bitmask backtracking counts all [OK]

Common Mistakes:

• Off-by-one counting
• Confusing number of solutions with board size

2. Identify the bug in the following code snippet for counting beautiful arrangements:

medium

A. Line with 'bit = 1 << num' bit shift

B. Line with 'if (used & bit) == 0' check

C. Line with 'if pos > n:' condition

D. Line with recursive call 'backtrack(pos + 1, used | bit)'

Solution

1. Step 1: Analyze bit shift operation

   Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.

2. Step 2: Consequence of incorrect bit shift

   Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct bit shift is critical for accurate used-state tracking [OK]

Hint: Bit shifts must be zero-based for bitmask [OK]

Common Mistakes:

• Off-by-one bit shifts
• Forgetting to unmark used numbers

3. Consider the following buggy code for generating letter combinations. Which line contains the subtle bug that causes incorrect or incomplete results?

from collections import deque

def letterCombinations(digits):
    if digits == '':
        return ['']
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

medium

A. Line 7: letters = digit_map[digit]

B. Line 2: if digits == '': return ['']

C. Line 10: prev = queue.popleft()

D. Line 1: from collections import deque

Solution

1. Step 1: Analyze empty input handling

   Returning [''] for empty input is incorrect; the problem expects an empty list [] when input is empty.

2. Step 2: Check other lines

   Digit mapping, queue operations, and imports are correct and do not cause bugs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Empty input should return [] not [''] to match problem spec [OK]

Hint: Empty input must return empty list, not list with empty string [OK]

Common Mistakes:

• Returning [''] instead of [] for empty input
• Assuming digits '1' or '0' map to letters

4. What is the time complexity of the optimal backtracking algorithm that generates unique permutations of an array with duplicates by sorting and skipping duplicates during recursion?

medium

A. O(n! * log n) due to sorting and binary search for duplicates

B. O(n! * n^2) because each permutation requires copying the array and checking duplicates

C. O(n^n) because the recursion explores all possible swaps without pruning

D. O(n! * n) because pruning duplicates early reduces redundant branches but each permutation still requires O(n) copying

Solution

1. Step 1: Identify complexity of outer and inner loops

   Backtracking explores permutations, which is O(n!). Each permutation requires copying O(n) elements to result.

2. Step 2: Check if pruning duplicates reduces complexity

   Pruning duplicates early avoids redundant branches, so complexity is O(n! * n), not worse. Sorting is O(n log n) but done once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pruning reduces branches but copying each permutation costs O(n) [OK]

Hint: Pruning duplicates reduces branches but copying costs O(n) per permutation [OK]

Common Mistakes:

• Confusing pruning effect or ignoring copy cost

5. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column conflicts are ignored), but diagonal conflicts still apply. Which modification to the bitmask backtracking approach correctly counts all valid solutions under this relaxed constraint?

hard

A. Track only column bitmask and ignore diagonal bitmasks

B. Keep all bitmasks but allow queens to be placed in any column regardless of conflicts

C. Remove the column bitmask and only track diagonal bitmasks for conflicts

D. Use a greedy approach placing queens in the first available diagonal position per row

Solution

1. Step 1: Analyze relaxed constraints

   Column conflicts are ignored, so column bitmask is unnecessary; diagonal conflicts remain.

2. Step 2: Modify bitmask tracking accordingly

   Remove column bitmask from conflict checks and recursive calls; keep positive and negative diagonal bitmasks to prune invalid placements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Removing column mask matches relaxed rules and preserves diagonal conflict checks [OK]

Hint: Ignore column mask when column conflicts are allowed [OK]

Common Mistakes:

• Ignoring diagonals too
• Allowing all placements without pruning