Sudoku Solver
Solve a Sudoku puzzle in place via backtracking with row/col/box bitmasks.
6 min read
backtracking bitmask
Problem#
Fill the empty cells (.) of a partial 9×9 Sudoku board to form a valid solution. Exactly one solution exists.
Approach#
Track row/col/box usage as 9-bit masks. DFS over cells left-to-right, top-to-bottom; for each empty cell, try every digit not in its row/col/box mask. Recurse; on failure, unset and try the next digit.
Solution#
class Solution {public: void solveSudoku(vector<vector<char>>& b) { int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0}; for (int r = 0; r < 9; ++r) for (int c = 0; c < 9; ++c) if (b[r][c] != '.') { int bit = 1 << (b[r][c] - '1'); rows[r] |= bit; cols[c] |= bit; boxes[(r/3)*3 + c/3] |= bit; } function<bool(int)> dfs = [&](int pos) { if (pos == 81) return true; int r = pos / 9, c = pos % 9, k = (r/3)*3 + c/3; if (b[r][c] != '.') return dfs(pos + 1); int used = rows[r] | cols[c] | boxes[k]; for (int d = 0; d < 9; ++d) { int bit = 1 << d; if (used & bit) continue; b[r][c] = '1' + d; rows[r] |= bit; cols[c] |= bit; boxes[k] |= bit; if (dfs(pos + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[k] ^= bit; b[r][c] = '.'; } return false; }; dfs(0); }};func solveSudoku(b [][]byte) { var rows, cols, boxes [9]int for r := 0; r < 9; r++ { for c := 0; c < 9; c++ { if b[r][c] != '.' { bit := 1 << (b[r][c] - '1') rows[r] |= bit cols[c] |= bit boxes[(r/3)*3+c/3] |= bit } } } var dfs func(pos int) bool dfs = func(pos int) bool { if pos == 81 { return true } r, c := pos/9, pos%9 k := (r/3)*3 + c/3 if b[r][c] != '.' { return dfs(pos + 1) } used := rows[r] | cols[c] | boxes[k] for d := 0; d < 9; d++ { bit := 1 << d if used&bit != 0 { continue } b[r][c] = byte('1' + d) rows[r] |= bit cols[c] |= bit boxes[k] |= bit if dfs(pos + 1) { return true } rows[r] ^= bit cols[c] ^= bit boxes[k] ^= bit b[r][c] = '.' } return false } dfs(0)}from typing import List
class Solution: def solveSudoku(self, b: List[List[str]]) -> None: rows = [0] * 9 cols = [0] * 9 boxes = [0] * 9 for r in range(9): for c in range(9): if b[r][c] != '.': bit = 1 << (int(b[r][c]) - 1) rows[r] |= bit cols[c] |= bit boxes[(r // 3) * 3 + c // 3] |= bit
def dfs(pos: int) -> bool: if pos == 81: return True r, c = divmod(pos, 9) k = (r // 3) * 3 + c // 3 if b[r][c] != '.': return dfs(pos + 1) used = rows[r] | cols[c] | boxes[k] for d in range(9): bit = 1 << d if used & bit: continue b[r][c] = str(d + 1) rows[r] |= bit cols[c] |= bit boxes[k] |= bit if dfs(pos + 1): return True rows[r] ^= bit cols[c] ^= bit boxes[k] ^= bit b[r][c] = '.' return False
dfs(0)function solveSudoku(b) { const rows = new Array(9).fill(0); const cols = new Array(9).fill(0); const boxes = new Array(9).fill(0); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (b[r][c] !== '.') { const bit = 1 << (b[r][c].charCodeAt(0) - 49); // '1' = 49 rows[r] |= bit; cols[c] |= bit; boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)] |= bit; } } } const dfs = (pos) => { if (pos === 81) return true; const r = Math.floor(pos / 9); const c = pos % 9; const k = Math.floor(r / 3) * 3 + Math.floor(c / 3); if (b[r][c] !== '.') return dfs(pos + 1); const used = rows[r] | cols[c] | boxes[k]; for (let d = 0; d < 9; d++) { const bit = 1 << d; if (used & bit) continue; b[r][c] = String(d + 1); rows[r] |= bit; cols[c] |= bit; boxes[k] |= bit; if (dfs(pos + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[k] ^= bit; b[r][c] = '.'; } return false; }; dfs(0);}class Solution { private int[] rows = new int[9]; private int[] cols = new int[9]; private int[] boxes = new int[9]; private char[][] board;
public void solveSudoku(char[][] b) { this.board = b; for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (b[r][c] != '.') { int bit = 1 << (b[r][c] - '1'); rows[r] |= bit; cols[c] |= bit; boxes[(r / 3) * 3 + c / 3] |= bit; } } } dfs(0); }
private boolean dfs(int pos) { if (pos == 81) return true; int r = pos / 9, c = pos % 9, k = (r / 3) * 3 + c / 3; if (board[r][c] != '.') return dfs(pos + 1); int used = rows[r] | cols[c] | boxes[k]; for (int d = 0; d < 9; d++) { int bit = 1 << d; if ((used & bit) != 0) continue; board[r][c] = (char) ('1' + d); rows[r] |= bit; cols[c] |= bit; boxes[k] |= bit; if (dfs(pos + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[k] ^= bit; board[r][c] = '.'; } return false; }}function solveSudoku(b: string[][]): void { const rows: number[] = new Array(9).fill(0); const cols: number[] = new Array(9).fill(0); const boxes: number[] = new Array(9).fill(0); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (b[r][c] !== '.') { const bit: number = 1 << (b[r][c].charCodeAt(0) - 49); rows[r] |= bit; cols[c] |= bit; boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)] |= bit; } } } const dfs = (pos: number): boolean => { if (pos === 81) return true; const r: number = Math.floor(pos / 9); const c: number = pos % 9; const k: number = Math.floor(r / 3) * 3 + Math.floor(c / 3); if (b[r][c] !== '.') return dfs(pos + 1); const used: number = rows[r] | cols[c] | boxes[k]; for (let d = 0; d < 9; d++) { const bit: number = 1 << d; if (used & bit) continue; b[r][c] = String(d + 1); rows[r] |= bit; cols[c] |= bit; boxes[k] |= bit; if (dfs(pos + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[k] ^= bit; b[r][c] = '.'; } return false; }; dfs(0);}Editorial#
Bitmasks per row/col/box make “is digit d available here?” a single bitwise-and. The DFS order (left-to-right, top-to-bottom) is sufficient; advanced heuristics (most-constrained-cell first) cut typical solve times but aren’t needed.
Complexity#
- Time: O(9^k) where k is the number of empty cells.
- Space: O(1) auxiliary.
Concept revision#
Related#