Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
A complete visual walkthrough of the backtracking algorithm — filling empty cells one by one, undoing choices when stuck.
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
1-9 must occur exactly once in each row.1-9 must occur exactly once in each column.1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.The '.' character indicates empty cells.
Example 1:
Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["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"]] Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9board[i].length == 9board[i][j] is a digit or '.'.Sudoku solving is a classic constraint satisfaction problem. The approach is elegant in its simplicity:
Why does backtracking work? The problem guarantees exactly one solution. Backtracking systematically explores all possibilities, but the Sudoku constraints prune most branches immediately. In practice, it solves most puzzles in milliseconds.
Here's the decision tree the algorithm builds. Each node is a choice for an empty cell:
The algorithm explores forward until stuck, then backtracks to try the next option. Think of it as navigating a maze — when you hit a dead end, you retrace your steps.
Consider a partially filled board. The algorithm finds the first empty cell and starts trying digits:
Before placing a digit, we must verify it doesn't violate any constraint. We check three things in a single loop:
private boolean isValid(char[][] board, int row, int col, char c) { for (int i = 0; i < 9; i++) { if (board[row][i] == c) return false; // check row if (board[i][col] == c) return false; // check column if (board[3*(row/3)+i/3][3*(col/3)+i%3] == c) // check 3x3 box return false; } return true; }
func isValid(board [][]byte, row, col int, c byte) bool { for i := 0; i < 9; i++ { if board[row][i] == c { return false // check row } if board[i][col] == c { return false // check column } br := 3*(row/3) + i/3 bc := 3*(col/3) + i%3 if board[br][bc] == c { return false // check 3x3 box } } return true }
def is_valid(board: list[list[str]], row: int, col: int, c: str) -> bool: for i in range(9): if board[row][i] == c: # check row return False if board[i][col] == c: # check column return False br = 3 * (row // 3) + i // 3 bc = 3 * (col // 3) + i % 3 if board[br][bc] == c: # check 3x3 box return False return True
fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, c: char) -> bool { for i in 0..9 { if board[row][i] == c { return false; // check row } if board[i][col] == c { return false; // check column } let br = 3 * (row / 3) + i / 3; let bc = 3 * (col / 3) + i % 3; if board[br][bc] == c { return false; // check 3x3 box } } true }
function isValid(board: string[][], row: number, col: number, c: string): boolean { for (let i = 0; i < 9; i++) { if (board[row][i] === c) return false; // check row if (board[i][col] === c) return false; // check column const br = 3 * Math.floor(row / 3) + Math.floor(i / 3); const bc = 3 * Math.floor(col / 3) + i % 3; if (board[br][bc] === c) return false; // check 3x3 box } return true; }
The box index formula: 3*(row/3)+i/3 and 3*(col/3)+i%3 iterate through all 9 cells of the 3x3 box containing (row, col). As i goes 0..8, i/3 gives 0,0,0,1,1,1,2,2,2 for row offsets and i%3 gives 0,1,2,0,1,2,0,1,2 for column offsets.
Only one digit fits without conflicting with its row, column, and 3×3 box. The solver places it immediately and returns — no backtracking needed.
Many placements look valid early on but lead to a dead end later. For example, placing 1 in cell (0,0) may force a conflict dozens of steps later, requiring the solver to unwind the entire chain.
A nearly blank board forces the algorithm to explore a huge search tree. Constraint bitmasks (row/col/block arrays) prune invalid branches fast, keeping this tractable within the 9×9 bounds.
When no cells contain '.', the list of empty positions is empty. The DFS base case fires immediately (k == t.size()) and the board is returned unchanged.
A cell where eight of nine digits are already used in its row, column, or box has exactly one candidate. The solver places it without branching, effectively performing unit propagation via the bitmask checks.
class Solution { public void solveSudoku(char[][] board) { solve(board); } private boolean solve(char[][] board) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != '.') continue; // skip filled cells for (char c = '1'; c <= '9'; c++) { if (isValid(board, i, j, c)) { board[i][j] = c; // place digit if (solve(board)) // recurse return true; // solved! board[i][j] = '.'; // backtrack } } return false; // no digit works → trigger backtracking } } return true; // no empty cells left → solved! } private boolean isValid(char[][] board, int row, int col, char c) { for (int i = 0; i < 9; i++) { if (board[row][i] == c) return false; if (board[i][col] == c) return false; if (board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false; } return true; } }
func solveSudoku(board [][]byte) { var solve func() bool solve = func() bool { for i := 0; i < 9; i++ { for j := 0; j < 9; j++ { if board[i][j] != '.' { continue // skip filled cells } for c := byte('1'); c <= '9'; c++ { if isValidSudoku(board, i, j, c) { board[i][j] = c // place digit if solve() { return true // solved! } board[i][j] = '.' // backtrack } } return false // no digit works → backtrack } } return true // no empty cells left → solved! } solve() } func isValidSudoku(board [][]byte, row, col int, c byte) bool { for i := 0; i < 9; i++ { if board[row][i] == c { return false } if board[i][col] == c { return false } if board[3*(row/3)+i/3][3*(col/3)+i%3] == c { return false } } return true }
class Solution: def solve_sudoku(self, board: list[list[str]]) -> None: self._solve(board) def _solve(self, board: list[list[str]]) -> bool: for i in range(9): for j in range(9): if board[i][j] != ".": continue # skip filled cells for d in range(1, 10): c = str(d) if self._is_valid(board, i, j, c): board[i][j] = c # place digit if self._solve(board): # recurse return True # solved! board[i][j] = "." # backtrack return False # no digit works → trigger backtracking return True # no empty cells left → solved! def _is_valid(self, board: list[list[str]], row: int, col: int, c: str) -> bool: for i in range(9): if board[row][i] == c: return False if board[i][col] == c: return False br = 3 * (row // 3) + i // 3 bc = 3 * (col // 3) + i % 3 if board[br][bc] == c: return False return True
impl Solution { pub fn solve_sudoku(board: &mut Vec<Vec<char>>) { Self::solve(board); } fn solve(board: &mut Vec<Vec<char>>) -> bool { for i in 0..9 { for j in 0..9 { if board[i][j] != '.' { continue; // skip filled cells } for c in '1'..='9' { if Self::is_valid(board, i, j, c) { board[i][j] = c; // place digit if Self::solve(board) { return true; // solved! } board[i][j] = '.'; // backtrack } } return false; // no digit works → backtrack } } true // no empty cells left → solved! } fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, c: char) -> bool { for i in 0..9 { if board[row][i] == c { return false; } if board[i][col] == c { return false; } let br = 3 * (row / 3) + i / 3; let bc = 3 * (col / 3) + i % 3; if board[br][bc] == c { return false; } } true } }
function solveSudoku(board: string[][]): void { solve(board); } function solve(board: string[][]): boolean { for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { if (board[i][j] !== ".") continue; // skip filled cells for (let d = 1; d <= 9; d++) { const c = String(d); if (isValid(board, i, j, c)) { board[i][j] = c; // place digit if (solve(board)) // recurse return true; // solved! board[i][j] = "."; // backtrack } } return false; // no digit works → trigger backtracking } } return true; // no empty cells left → solved! } function isValid(board: string[][], row: number, col: number, c: string): boolean { for (let i = 0; i < 9; i++) { if (board[row][i] === c) return false; if (board[i][col] === c) return false; const br = 3 * Math.floor(row / 3) + Math.floor(i / 3); const bc = 3 * Math.floor(col / 3) + i % 3; if (board[br][bc] === c) return false; } return true; }
Watch the solver fill in cells and backtrack when stuck. Each step shows one placement or one backtrack.
Where m is the number of empty cells. Backtracking fills each empty cell by trying up to 9 digits. In the absolute worst case (an empty board), m = 81 and we explore up to 981 branches. Space is O(m) for the recursion stack -- one frame per empty cell.
Try all 9 digits in every cell without checking constraints first. Each of the 81 cells branches 9 ways, giving 981 total paths. The recursion stack grows up to 81 frames deep for a fully empty board.
Only m empty cells are explored, and the isValid check prunes invalid digits before recursing. This eliminates most branches immediately -- a typical puzzle with ~25 givens solves in under a millisecond. Stack depth is at most m.
Constraint propagation is the key. Checking row/col/box validity before placing a digit prunes most branches immediately. A typical puzzle with ~25 givens is solved in under a millisecond -- the effective branching factor is far less than 9 despite the exponential worst case.
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.