Sudoku Solver
A hard Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 2
- Core for
- 0 roles
The problem
Write an algorithm to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. Each row, column, and 3×3 box must contain the digits 1 through 9 without repetition. The input board has exactly one solution.
Example 1
- Input
- board = [[".",".","3",".",".","1","5","6","."],["1",".",".","9",".","4","3",".","."],["7","6",".",".",".",".",".",".","8"],[".",".","5",".",".","6",".",".","."],["3","7","2",".",".","5",".","9","."],[".","1",".",".","2",".","8","7","."],["8",".",".",".",".","7",".",".","3"],["5",".","6",".",".",".",".",".","1"],["2","3",".","5",".",".",".",".","6"]]
- Output
- [["4","2","3","8","7","1","5","6","9"],["1","5","8","9","6","4","3","2","7"],["7","6","9","2","5","3","4","1","8"],["9","8","5","7","4","6","1","3","2"],["3","7","2","1","8","5","6","9","4"],["6","1","4","3","2","9","8","7","5"],["8","4","1","6","9","7","2","5","3"],["5","9","6","4","3","2","7","8","1"],["2","3","7","5","1","8","9","4","6"]]
- Why
- Each row, column and 3x3 box ends up with the digits 1-9 exactly once; this board has a single valid completion.
Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or '.'
- The input board has exactly one solution
How to think about it
Updated 2026-09-29Sudoku is an exact constraint satisfaction problem where choices must immediately stop the moment any sub-grid, row, or column is violated. Returning a boolean from the recursive step allows the search to halt instantly upon discovering the single valid completed board, avoiding unwinding or exploring dead branches.
Approaches, worst first
Linear scanning with board checks
time O(9^m) · space O(m)
Iterate through the board to find the next empty cell. For digits '1' through '9', scan the full 9 cells of the row, column, and 3x3 block to verify safety before placing. Correct and fast enough for a 9x9 board, but repeats 27 cell comparisons on every placement.
Bitmask constraint arraysWrite this one
time O(9^m) · space O(m)
Precompute occupied digits using bitmasks: rows[9], cols[9], and boxes[9]. Validating a candidate digit d is a single bitwise AND against (rows[r] | cols[c] | boxes[b]). Once placed, set the d-th bit and recurse, clearing it if child calls fail.
Where people lose marks · 3
- Incorrect 3x3 box indexing. The formula is 3 * Math.floor(row / 3) + Math.floor(col / 3); using row % 3 or col % 3 conflates different sub-boxes.
- Continuing recursion after a valid solution has been found. If the solver does not return true up the call stack, backtracking clears the solved digits back to '.' characters.
- Failing to reset board[r][c] = '.' on branch failure before returning false, which leaves invalid digits on the board.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .