How to Solve: Sudoku Solver – Complete Guide for FAANG Interviews

How to Solve: Sudoku Solver – Complete Guide for FAANG Interviews

? Introduction

"Sudoku Solver is the ultimate test of backtracking mastery—it appears in 1 out of every 3 onsite interviews at top-tier companies like Google, Meta, and Amazon. Nail it, and you prove you can handle constraint propagation, recursion, and pruning—skills that separate L4 from L5 engineers."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Sudoku Solver, you must understand: 1. Backtracking (DFS with pruning) – Recursively explore possibilities, undoing invalid choices. 2. 2D Array Traversal – Efficiently check rows, columns, and 3x3 subgrids. 3. Hash Sets / Bitmasking – Track used numbers in O(1) time.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental checklist for every Sudoku problem:

1. Understand the Board
2. Input: 9x9 grid with '.' for empty cells, digits '1'-'9' for filled.

3. Output: Modify the board in-place (no return value).

4. Choose a Cell to Fill

5. Start with the cell with the fewest possibilities (optimization).

6. If no empty cells, the board is solved.

7. Generate Valid Candidates

8. For the chosen cell, check:

   • Row: No duplicate in the same row.
   • Column: No duplicate in the same column.
   • Subgrid: No duplicate in the 3x3 subgrid.

9. Recursive Backtracking

10. For each candidate:

    • Place the number.
    • Recurse to solve the next cell.
    • If recursion succeeds, return True.
    • If not, backtrack (undo the placement).

11. Base Case

12. If all cells are filled, return True.

13. If no candidates work, return False.

14. Optimizations (Optional but Recommended)

15. Bitmasking: Track used numbers in rows/columns/subgrids with integers.
16. Early Termination: Stop if a cell has no valid candidates.

? WORKED EXAMPLES

Example 1 – Basic Sudoku Solver (Backtracking Only)

Problem: Solve a 9x9 Sudoku board with backtracking.

Thought Process

1. Iterate through each cell.
2. If empty ('.'), try numbers 1-9.
3. Check if the number is valid in row/column/subgrid.
4. Recurse; if it leads to a solution, return True.
5. If no number works, backtrack.

Python Code

def solveSudoku(board):

    def is_valid(row, col, num):

        # Check row

        for i in range(9):

            if board[row][i] == num:

                return False


        # Check column

        for i in range(9):

            if board[i][col] == num:

                return False


        # Check 3x3 subgrid

        start_row, start_col = 3  (row // 3), 3  (col // 3)

        for i in range(3):

            for j in range(3):

                if board[start_row + i][start_col + j] == num:

                    return False

        return True


    def backtrack():

        for row in range(9):

            for col in range(9):

                if board[row][col] == '.':

                    for num in map(str, range(1, 10)):

                        if is_valid(row, col, num):

                            board[row][col] = num

                            if backtrack():

                                return True

                            board[row][col] = '.'  # Backtrack

                    return False  # No valid number found

        return True  # All cells filled


    backtrack()

Time & Space Complexity

• Time: O(9^(n)) where n is the number of empty cells (worst case).
• Space: O(n) (recursion stack depth).

Why This Works

• Backtracking explores all possibilities while pruning invalid paths early.
• Constraint checks ensure only valid numbers are placed.

Example 2 – Medium: Optimized with Bitmasking

Problem: Solve Sudoku faster by tracking used numbers with bitmasks.

Thought Process

1. Use three arrays (rows, cols, subgrids) to track used numbers.
2. Each array is a bitmask (e.g., rows[row] |= (1 << num)).
3. Before placing a number, check if it’s already used in row/column/subgrid.

Python Code

def solveSudoku(board):

    rows = [0]  9

    cols = [0]  9

    subgrids = [0]  9


    # Initialize bitmasks

    for i in range(9):

        for j in range(9):

            if board[i][j] != '.':

                num = int(board[i][j])

                mask = 1 << num

                rows[i] |= mask

                cols[j] |= mask

                subgrids[(i // 3)  3 + (j // 3)] |= mask


    def backtrack():

        for i in range(9):

            for j in range(9):

                if board[i][j] == '.':

                    for num in range(1, 10):

                        mask = 1 << num

                        subgrid_idx = (i // 3)  3 + (j // 3)

                        if not (rows[i] & mask) and not (cols[j] & mask) and not (subgrids[subgrid_idx] & mask):

                            board[i][j] = str(num)

                            rows[i] |= mask

                            cols[j] |= mask

                            subgrids[subgrid_idx] |= mask


                            if backtrack():

                                return True


                            # Backtrack

                            board[i][j] = '.'

                            rows[i] ^= mask

                            cols[j] ^= mask

                            subgrids[subgrid_idx] ^= mask

                    return False

        return True


    backtrack()

Time & Space Complexity

• Time: O(9^(n)) (same as before, but faster due to bitwise checks).
• Space: O(1) (fixed-size arrays for tracking).

Why This Works

• Bitmasking reduces constraint checks from O(9) to O(1).
• Early pruning avoids unnecessary recursion.

Example 3 – Hard: Count All Valid Sudoku Solutions

Problem: Count all possible solutions for a given Sudoku board (follow-up question).

Thought Process

1. Modify the backtracking function to count solutions instead of returning early.
2. If a cell has no valid moves, return 0.
3. If all cells are filled, return 1.

Python Code

def countSolutions(board):

    rows = [0]  9

    cols = [0]  9

    subgrids = [0]  9


    # Initialize bitmasks

    for i in range(9):

        for j in range(9):

            if board[i][j] != '.':

                num = int(board[i][j])

                mask = 1 << num

                rows[i] |= mask

                cols[j] |= mask

                subgrids[(i // 3)  3 + (j // 3)] |= mask


    def backtrack():

        for i in range(9):

            for j in range(9):

                if board[i][j] == '.':

                    count = 0

                    for num in range(1, 10):

                        mask = 1 << num

                        subgrid_idx = (i // 3)  3 + (j // 3)

                        if not (rows[i] & mask) and not (cols[j] & mask) and not (subgrids[subgrid_idx] & mask):

                            board[i][j] = str(num)

                            rows[i] |= mask

                            cols[j] |= mask

                            subgrids[subgrid_idx] |= mask


                            count += backtrack()


                            # Backtrack

                            board[i][j] = '.'

                            rows[i] ^= mask

                            cols[j] ^= mask

                            subgrids[subgrid_idx] ^= mask

                    return count

        return 1  # All cells filled


    return backtrack()

Time & Space Complexity

• Time: O(9^(n)) (worst case, but pruning helps).
• Space: O(n) (recursion stack).

Why This Works

• Backtracking with counting explores all valid paths.
• Bitmasking ensures efficient constraint checks.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Sudoku Solver is all about backtracking with pruning. Here’s the playbook:

1. Pick an empty cell (start with the one with the fewest options).
2. Try numbers 1-9, checking if they’re valid in the row, column, and subgrid.
3. Recurse—if it leads to a solution, great! If not, backtrack.
4. Optimize with bitmasking for O(1) constraint checks.
5. Watch out for traps—interviewers might ask for counting solutions or iterative approaches.

You’ve got this. Now go solve that Sudoku like a pro!

Final Notes

• Practice: Solve LeetCode 37. Sudoku Solver and 36. Valid Sudoku.
• Follow-ups: Be ready for "Count all solutions" or "Solve with constraints (e.g., no recursion)."
• Whiteboard Tip: Draw the board and walk through the first few steps manually.

Now go ace that interview! ?