Sudoku Solver

Sudoku Solver

What is this problem about?

The "Sudoku Solver" problem asks you to write a program that fills in the empty cells of a 9x9 Sudoku board. A valid Sudoku solution must satisfy three conditions: each of the digits 1-9 must occur exactly once in each row, exactly once in each column, and exactly once in each of the nine 3x3 sub-boxes of the grid. Empty cells are typically denoted by a character like '.'.

Why is this asked in interviews?

This is a quintessential Hard-level backtracking problem asked by nearly every major tech company (Apple, Uber, Google, etc.). It tests a candidate's ability to implement a recursive search with state management. It requires careful handling of constraints and efficient "is valid" checks. Solving Sudoku isn't just about the puzzle; it's about demonstrating that you can navigate a large search space and prune unnecessary paths efficiently.

Algorithmic pattern used

The pattern used is Backtracking. The algorithm tries to fill an empty cell with a digit from '1' to '9'. For each digit, it checks if the placement is valid (no conflicts in row, column, or 3x3 box). If it's valid, the algorithm moves to the next empty cell. If it reaches a point where no digit can be placed, it "backtracks" by clearing the current cell and trying the next digit in the previous cell. This depth-first search continues until the board is completely filled.

Example explanation

Imagine a board where the first empty cell is at (0, 2).

1. We try placing '1'. We check row 0, column 2, and the top-left 3x3 box.
2. If '1' is already in row 0, we skip it and try '2'.
3. If '2' is valid, we place it and call the solver recursively for the next cell.
4. If the rest of the board cannot be solved with '2' at (0, 2), the function returns false, and we try '3' at (0, 2). This process ensures we explore all possibilities until a solution is found.

Common mistakes candidates make

1. Inefficient Validation: Re-scanning the entire row, column, and box for every single check. A more efficient way is to use hash sets or bitmasks to keep track of used numbers.
2. Incorrect Recursion Base Case: Failing to identify when the board is fully solved or how to propagate the "solved" status back up the recursion stack.
3. Global Variable Misuse: Using global state that doesn't reset properly during backtracking, leading to "ghost" values on the board.

Interview preparation tip

Practice backtracking with smaller grids first (like a 4x4 Sudoku) to get the logic right. Focus on how to represent the constraints. Can you use a bitmask to check if a number is present in a row in O(1)? Small optimizations like these can turn a slow backtracking solution into a highly efficient one.