LeetCode 37: Sudoku Solver (Backtracking with Row/Col/Box Constraints)
LeetCode 37BacktrackingConstraint PropagationToday we solve LeetCode 37 - Sudoku Solver.
Source: https://leetcode.com/problems/sudoku-solver/
English
Problem Summary
Given a partially filled 9 x 9 Sudoku board, fill empty cells ('.') so that every row, every column, and every 3 x 3 box contains digits 1..9 exactly once. The puzzle is guaranteed to have one valid solution.
Key Insight
This is a classic constrained search problem. For each empty cell, only digits that are absent from its row, column, and box are legal. Backtracking tries legal choices and immediately prunes invalid branches.
Why Backtracking Works Here
At each step we preserve Sudoku invariants using three boolean structures: rows[9][10], cols[9][10], boxes[9][10]. A candidate digit is valid iff all three structures say "not used".
Algorithm Steps
1) Scan the board and preload used digits into row/col/box tables.
2) Collect coordinates of empty cells.
3) DFS on empties index k: try digits 1..9 that satisfy all constraints.
4) Place digit, mark row/col/box, recurse to k+1.
5) If deeper call fails, undo placement and marks (backtrack).
6) When k == empties.size(), board is solved.
Complexity Analysis
Worst-case time is exponential (roughly O(9^E), E = number of empty cells), but pruning is strong for valid Sudoku inputs.
Space: O(E) recursion depth plus fixed constraint tables.
Common Pitfalls
- Forgetting to undo row/col/box marks during backtracking.
- Wrong box index formula; must be (r / 3) * 3 + (c / 3).
- Mixing chars and ints incorrectly when writing digits back.
- Not preloading existing digits, causing illegal duplicates.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private final boolean[][] rows = new boolean[9][10];
private final boolean[][] cols = new boolean[9][10];
private final boolean[][] boxes = new boolean[9][10];
private final List<int[]> empties = new ArrayList<>();
public void solveSudoku(char[][] board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char ch = board[r][c];
if (ch == '.') {
empties.add(new int[]{r, c});
} else {
int d = ch - '0';
int b = (r / 3) * 3 + c / 3;
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
dfs(board, 0);
}
private boolean dfs(char[][] board, int k) {
if (k == empties.size()) return true;
int r = empties.get(k)[0], c = empties.get(k)[1];
int b = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
board[r][c] = (char) ('0' + d);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
if (dfs(board, k + 1)) return true;
rows[r][d] = cols[c][d] = boxes[b][d] = false;
board[r][c] = '.';
}
return false;
}
}func solveSudoku(board [][]byte) {
rows := [9][10]bool{}
cols := [9][10]bool{}
boxes := [9][10]bool{}
empties := [][2]int{}
for r := 0; r < 9; r++ {
for c := 0; c < 9; c++ {
ch := board[r][c]
if ch == '.' {
empties = append(empties, [2]int{r, c})
} else {
d := int(ch - '0')
b := (r/3)*3 + c/3
rows[r][d], cols[c][d], boxes[b][d] = true, true, true
}
}
}
var dfs func(int) bool
dfs = func(k int) bool {
if k == len(empties) {
return true
}
r, c := empties[k][0], empties[k][1]
b := (r/3)*3 + c/3
for d := 1; d <= 9; d++ {
if rows[r][d] || cols[c][d] || boxes[b][d] {
continue
}
board[r][c] = byte('0' + d)
rows[r][d], cols[c][d], boxes[b][d] = true, true, true
if dfs(k + 1) {
return true
}
rows[r][d], cols[c][d], boxes[b][d] = false, false, false
board[r][c] = '.'
}
return false
}
dfs(0)
}class Solution {
public:
bool rows[9][10] = {}, cols[9][10] = {}, boxes[9][10] = {};
vector<pair<int,int>> empties;
void solveSudoku(vector<vector<char>>& board) {
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
char ch = board[r][c];
if (ch == '.') {
empties.push_back({r, c});
} else {
int d = ch - '0';
int b = (r / 3) * 3 + c / 3;
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
dfs(board, 0);
}
bool dfs(vector<vector<char>>& board, int k) {
if (k == (int)empties.size()) return true;
auto [r, c] = empties[k];
int b = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; ++d) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
board[r][c] = char('0' + d);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
if (dfs(board, k + 1)) return true;
rows[r][d] = cols[c][d] = boxes[b][d] = false;
board[r][c] = '.';
}
return false;
}
};class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
rows = [[False] * 10 for _ in range(9)]
cols = [[False] * 10 for _ in range(9)]
boxes = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
empties.append((r, c))
else:
d = ord(ch) - ord('0')
b = (r // 3) * 3 + c // 3
rows[r][d] = cols[c][d] = boxes[b][d] = True
def dfs(k: int) -> bool:
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if rows[r][d] or cols[c][d] or boxes[b][d]:
continue
board[r][c] = str(d)
rows[r][d] = cols[c][d] = boxes[b][d] = True
if dfs(k + 1):
return True
rows[r][d] = cols[c][d] = boxes[b][d] = False
board[r][c] = '.'
return False
dfs(0)/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
const rows = Array.from({ length: 9 }, () => Array(10).fill(false));
const cols = Array.from({ length: 9 }, () => Array(10).fill(false));
const boxes = Array.from({ length: 9 }, () => Array(10).fill(false));
const empties = [];
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const ch = board[r][c];
if (ch === '.') {
empties.push([r, c]);
} else {
const d = ch.charCodeAt(0) - 48;
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
const dfs = (k) => {
if (k === empties.length) return true;
const [r, c] = empties[k];
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
for (let d = 1; d <= 9; d++) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
board[r][c] = String(d);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
if (dfs(k + 1)) return true;
rows[r][d] = cols[c][d] = boxes[b][d] = false;
board[r][c] = '.';
}
return false;
};
dfs(0);
};中文
题目概述
给定一个部分填充的 9 x 9 数独棋盘，空位用 '.' 表示。你需要填满所有空位，使每一行、每一列、每个 3 x 3 宫都恰好包含数字 1..9，且题目保证解唯一。
核心思路
这是标准约束搜索。对每个空格，只能尝试当前行、列、宫都尚未使用的数字。使用回溯法：合法就继续，不合法立即剪枝回退。
为什么该方法高效
我们用三个布尔表维护已用数字：rows、cols、boxes。每次判定候选数字是否可放，仅需 O(1) 查询，剪枝效率很高。
算法步骤
1）先扫描棋盘，把已填数字写入行/列/宫标记。
2）记录所有空格坐标。
3）按空格顺序 DFS：尝试数字 1..9。
4）若数字在行、列、宫均未出现，则放入并标记后递归。
5）若递归失败，撤销填充与标记（回溯）。
6）当空格全部处理完毕，得到完整解。
复杂度分析
最坏时间复杂度呈指数级（约 O(9^E)，E 为空格数），但数独约束强，实际剪枝后通常远优于理论上界。
空间复杂度：O(E) 递归栈 + 固定大小标记表。
常见陷阱
- 回溯时忘记撤销行/列/宫标记。
- 宫编号公式写错，正确是 (r / 3) * 3 + (c / 3)。
- 字符与数字转换混乱，导致写入错误。
- 未预加载初始数字，回溯过程中出现重复冲突。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private final boolean[][] rows = new boolean[9][10];
private final boolean[][] cols = new boolean[9][10];
private final boolean[][] boxes = new boolean[9][10];
private final List<int[]> empties = new ArrayList<>();
public void solveSudoku(char[][] board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char ch = board[r][c];
if (ch == '.') {
empties.add(new int[]{r, c});
} else {
int d = ch - '0';
int b = (r / 3) * 3 + c / 3;
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
dfs(board, 0);
}
private boolean dfs(char[][] board, int k) {
if (k == empties.size()) return true;
int r = empties.get(k)[0], c = empties.get(k)[1];
int b = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
board[r][c] = (char) ('0' + d);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
if (dfs(board, k + 1)) return true;
rows[r][d] = cols[c][d] = boxes[b][d] = false;
board[r][c] = '.';
}
return false;
}
}func solveSudoku(board [][]byte) {
rows := [9][10]bool{}
cols := [9][10]bool{}
boxes := [9][10]bool{}
empties := [][2]int{}
for r := 0; r < 9; r++ {
for c := 0; c < 9; c++ {
ch := board[r][c]
if ch == '.' {
empties = append(empties, [2]int{r, c})
} else {
d := int(ch - '0')
b := (r/3)*3 + c/3
rows[r][d], cols[c][d], boxes[b][d] = true, true, true
}
}
}
var dfs func(int) bool
dfs = func(k int) bool {
if k == len(empties) {
return true
}
r, c := empties[k][0], empties[k][1]
b := (r/3)*3 + c/3
for d := 1; d <= 9; d++ {
if rows[r][d] || cols[c][d] || boxes[b][d] {
continue
}
board[r][c] = byte('0' + d)
rows[r][d], cols[c][d], boxes[b][d] = true, true, true
if dfs(k + 1) {
return true
}
rows[r][d], cols[c][d], boxes[b][d] = false, false, false
board[r][c] = '.'
}
return false
}
dfs(0)
}class Solution {
public:
bool rows[9][10] = {}, cols[9][10] = {}, boxes[9][10] = {};
vector<pair<int,int>> empties;
void solveSudoku(vector<vector<char>>& board) {
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
char ch = board[r][c];
if (ch == '.') {
empties.push_back({r, c});
} else {
int d = ch - '0';
int b = (r / 3) * 3 + c / 3;
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
dfs(board, 0);
}
bool dfs(vector<vector<char>>& board, int k) {
if (k == (int)empties.size()) return true;
auto [r, c] = empties[k];
int b = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; ++d) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
board[r][c] = char('0' + d);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
if (dfs(board, k + 1)) return true;
rows[r][d] = cols[c][d] = boxes[b][d] = false;
board[r][c] = '.';
}
return false;
}
};class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
rows = [[False] * 10 for _ in range(9)]
cols = [[False] * 10 for _ in range(9)]
boxes = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
empties.append((r, c))
else:
d = ord(ch) - ord('0')
b = (r // 3) * 3 + c // 3
rows[r][d] = cols[c][d] = boxes[b][d] = True
def dfs(k: int) -> bool:
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if rows[r][d] or cols[c][d] or boxes[b][d]:
continue
board[r][c] = str(d)
rows[r][d] = cols[c][d] = boxes[b][d] = True
if dfs(k + 1):
return True
rows[r][d] = cols[c][d] = boxes[b][d] = False
board[r][c] = '.'
return False
dfs(0)/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
const rows = Array.from({ length: 9 }, () => Array(10).fill(false));
const cols = Array.from({ length: 9 }, () => Array(10).fill(false));
const boxes = Array.from({ length: 9 }, () => Array(10).fill(false));
const empties = [];
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const ch = board[r][c];
if (ch === '.') {
empties.push([r, c]);
} else {
const d = ch.charCodeAt(0) - 48;
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
const dfs = (k) => {
if (k === empties.length) return true;
const [r, c] = empties[k];
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
for (let d = 1; d <= 9; d++) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
board[r][c] = String(d);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
if (dfs(k + 1)) return true;
rows[r][d] = cols[c][d] = boxes[b][d] = false;
board[r][c] = '.';
}
return false;
};
dfs(0);
};
Comments