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. You need to find the k-th lexicographically smallest permutation of numbers from 1 to n. Which approach guarantees an optimal solution without generating all permutations explicitly?

easy

A. Use a greedy algorithm that swaps elements to reach the k-th permutation directly.

B. Compute factorial values to determine each digit's position and build the permutation directly.

C. Use dynamic programming to count permutations and reconstruct the k-th sequence.

D. Generate all permutations using backtracking and return the k-th one.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the k-th permutation without enumerating all permutations, which is infeasible for large n.

2. Step 2: Identify the approach that uses factorial number system

   Using precomputed factorials, we can determine the index of each digit in the permutation directly, avoiding full enumeration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Factorial-based direct computation is optimal and avoids timeouts [OK]

Hint: Factorials let you jump directly to the k-th permutation [OK]

Common Mistakes:

• Thinking greedy swaps can find k-th permutation efficiently
• Assuming DP is needed here
• Trying to generate all permutations for large n

2. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

3. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?

def permuteUnique(nums):
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

medium

A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)

B. Line with 'nums.sort()' (sorting input before recursion)

C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)

D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

1. Step 1: Analyze duplicate skipping condition

   The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.

2. Step 2: Verify other lines

   Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect duplicate skipping causes duplicate permutations [OK]

Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]

Common Mistakes:

• Skipping duplicates by only comparing adjacent elements without usage tracking

4. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.

5. Suppose the Expression Add Operators problem is modified so that digits can be reused any number of times to form expressions (i.e., unlimited reuse of digits in order). Which of the following algorithmic changes correctly adapts the backtracking solution to handle this variant without infinite loops or incorrect results?

hard

A. Remove the index increment in recursive calls to allow reuse, but add a visited set to avoid infinite loops

B. Keep the index increment as is, but allow substring splits to wrap around to the start of the string

C. Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops

D. Allow index to reset to zero after reaching the end, but prune expressions longer than a fixed length to avoid infinite recursion

Solution

1. Step 1: Understand digit reuse impact

   Allowing reuse means the index does not always increment; digits can be chosen repeatedly, risking infinite recursion.

2. Step 2: Prevent infinite loops

   Not incrementing index requires limiting recursion depth (e.g., max length n) to avoid infinite loops while exploring repeated digits.

3. Step 3: Evaluate options

   Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops correctly limits recursion depth while allowing reuse; others either cause infinite loops or incorrect pruning.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Limiting recursion depth prevents infinite loops with reuse [OK]

Hint: Limit recursion depth when digits can be reused [OK]

Common Mistakes:

• Forgetting to limit recursion depth causes infinite loops