37. 解数独
题目描述
输入一个 9 x 9 的数独盘面 board，部分格子已填了 '1' 到 '9'，空格用 '.' 表示。
把所有空格填上数字，使每一行、每一列、以及 9 个不重叠的 3 x 3 小宫格里，1 到 9 都恰好各出现一次。
直接修改 board，函数不返回值，判题检查填完后的盘面。
示例 1
输入：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"]] 输出：[["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"]]
解释：这个盘面只有一种填法，输出就是填完后的完整盘面。
数据范围
board.length == 9board[i].length == 9board[i][j]是一位数字或'.'。- 输入的数独一定有解，且解唯一。
解题思路：回溯 + 集合判重
先扫描一遍棋盘，用三组集合记录每行、每列、每宫已经用过的数字，并把空格按顺序收集起来。然后对第 k 个空格依次尝试 1–9：只要数字不在所在行、列、宫的集合里，就填进去并递归处理第 k+1 个空格。后面走不通时撤销这次填写，换下一个数字。所有空格都填好就说明找到了解，一路返回 True 停止搜索。
为什么正确
进入 dfs(k) 时，前 k 个空格都已填好且互不冲突；rows、cols、boxes 与棋盘上的数字始终一致。
复杂度分析
最坏时间 O(9^m)，m 是空格数；实际因剪枝很快。额外空间 O(m) 递归栈加 O(81) 集合。
易错点
递归成功后要立刻返回 True，不能继续循环；否则后面的撤销会把已经填好的答案擦掉。另外，失败回退时三个集合都要删掉这个数字。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empty = []
for i in range(9):
for j in range(9):
d = board[i][j]
if d == '.':
empty.append((i, j))
else:
rows[i].add(d)
cols[j].add(d)
boxes[i // 3 * 3 + j // 3].add(d)
def dfs(k):
if k == len(empty):
return True
i, j = empty[k]
b = i // 3 * 3 + j // 3
for d in '123456789':
if d in rows[i] or d in cols[j] or d in boxes[b]:
continue
board[i][j] = d
rows[i].add(d)
cols[j].add(d)
boxes[b].add(d)
if dfs(k + 1):
return True
rows[i].remove(d)
cols[j].remove(d)
boxes[b].remove(d)
board[i][j] = '.'
return False
dfs(0)class Solution {
boolean[][] rows, cols, boxes;
List<int[]> empty;
char[][] board;
public void solveSudoku(char[][] board) {
this.board = board;
rows = new boolean[9][10];
cols = new boolean[9][10];
boxes = new boolean[9][10];
empty = new ArrayList<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char d = board[i][j];
if (d == '.') {
empty.add(new int[]{i, j});
} else {
rows[i][d - '0'] = true;
cols[j][d - '0'] = true;
boxes[i / 3 * 3 + j / 3][d - '0'] = true;
}
}
}
dfs(0);
}
boolean dfs(int k) {
if (k == empty.size()) {
return true;
}
int i = empty.get(k)[0], j = empty.get(k)[1];
int b = i / 3 * 3 + j / 3;
for (char d = '1'; d <= '9'; d++) {
if (rows[i][d - '0'] || cols[j][d - '0'] || boxes[b][d - '0']) {
continue;
}
board[i][j] = d;
rows[i][d - '0'] = true;
cols[j][d - '0'] = true;
boxes[b][d - '0'] = true;
if (dfs(k + 1)) {
return true;
}
rows[i][d - '0'] = false;
cols[j][d - '0'] = false;
boxes[b][d - '0'] = false;
}
board[i][j] = '.';
return false;
}
}class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
vector<vector<bool>> rows(9, vector<bool>(10));
vector<vector<bool>> cols(9, vector<bool>(10));
vector<vector<bool>> boxes(9, vector<bool>(10));
vector<pair<int, int>> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char d = board[i][j];
if (d == '.') {
empty.push_back({i, j});
} else {
rows[i][d - '0'] = true;
cols[j][d - '0'] = true;
boxes[i / 3 * 3 + j / 3][d - '0'] = true;
}
}
}
function<bool(int)> dfs = [&](int k) -> bool {
if (k == (int)empty.size()) {
return true;
}
auto [i, j] = empty[k];
int b = i / 3 * 3 + j / 3;
for (char d = '1'; d <= '9'; d++) {
if (rows[i][d - '0'] || cols[j][d - '0'] || boxes[b][d - '0']) {
continue;
}
board[i][j] = d;
rows[i][d - '0'] = true;
cols[j][d - '0'] = true;
boxes[b][d - '0'] = true;
if (dfs(k + 1)) {
return true;
}
rows[i][d - '0'] = false;
cols[j][d - '0'] = false;
boxes[b][d - '0'] = false;
}
board[i][j] = '.';
return false;
};
dfs(0);
}
};func solveSudoku(board [][]byte) {
var rows [9][10]bool
var cols [9][10]bool
var boxes [9][10]bool
empty := [][2]int{}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
d := board[i][j]
if d == '.' {
empty = append(empty, [2]int{i, j})
} else {
rows[i][d-'0'] = true
cols[j][d-'0'] = true
boxes[i/3*3+j/3][d-'0'] = true
}
}
}
var dfs func(k int) bool
dfs = func(k int) bool {
if k == len(empty) {
return true
}
i, j := empty[k][0], empty[k][1]
b := i/3*3 + j/3
for d := byte('1'); d <= '9'; d++ {
if rows[i][d-'0'] || cols[j][d-'0'] || boxes[b][d-'0'] {
continue
}
board[i][j] = d
rows[i][d-'0'] = true
cols[j][d-'0'] = true
boxes[b][d-'0'] = true
if dfs(k + 1) {
return true
}
rows[i][d-'0'] = false
cols[j][d-'0'] = false
boxes[b][d-'0'] = false
}
board[i][j] = '.'
return false
}
dfs(0)
}var solveSudoku = function(board) {
const rows = Array.from({length: 9}, () => new Set());
const cols = Array.from({length: 9}, () => new Set());
const boxes = Array.from({length: 9}, () => new Set());
const empty = [];
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const d = board[i][j];
if (d === '.') {
empty.push([i, j]);
} else {
rows[i].add(d);
cols[j].add(d);
boxes[Math.floor(i / 3) * 3 + Math.floor(j / 3)].add(d);
}
}
}
const dfs = (k) => {
if (k === empty.length) {
return true;
}
const [i, j] = empty[k];
const b = Math.floor(i / 3) * 3 + Math.floor(j / 3);
for (const d of '123456789') {
if (rows[i].has(d) || cols[j].has(d) || boxes[b].has(d)) {
continue;
}
board[i][j] = d;
rows[i].add(d);
cols[j].add(d);
boxes[b].add(d);
if (dfs(k + 1)) {
return true;
}
rows[i].delete(d);
cols[j].delete(d);
boxes[b].delete(d);
}
board[i][j] = '.';
return false;
};
dfs(0);
};function solveSudoku(board: string[][]): void {
const rows = Array.from({length: 9}, () => new Set<string>());
const cols = Array.from({length: 9}, () => new Set<string>());
const boxes = Array.from({length: 9}, () => new Set<string>());
const empty: number[][] = [];
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const d = board[i][j];
if (d === '.') {
empty.push([i, j]);
} else {
rows[i].add(d);
cols[j].add(d);
boxes[Math.floor(i / 3) * 3 + Math.floor(j / 3)].add(d);
}
}
}
const dfs = (k: number): boolean => {
if (k === empty.length) {
return true;
}
const [i, j] = empty[k];
const b = Math.floor(i / 3) * 3 + Math.floor(j / 3);
for (const d of '123456789') {
if (rows[i].has(d) || cols[j].has(d) || boxes[b].has(d)) {
continue;
}
board[i][j] = d;
rows[i].add(d);
cols[j].add(d);
boxes[b].add(d);
if (dfs(k + 1)) {
return true;
}
rows[i].delete(d);
cols[j].delete(d);
boxes[b].delete(d);
}
board[i][j] = '.';
return false;
};
dfs(0);
}其他解法
主解法按固定顺序填空格，思路最直接；位运算 + 最少候选优先在每步选择最受约束的格子，剪枝更强，是解数独的常用加速手段。
解法 2：位运算 + 最少候选优先 时间 O(9^m)，空间 O(m)
用 9 位整数 row[i]、col[j]、box[b] 记录各行、列、宫已用数字，某格可填数字的掩码为 ~(row|col|box) & 0x1FF。每层递归先扫描所有空格，挑出候选数最少的格子再枚举，只有一个候选的格子会被优先确定。枚举时用 mask & -mask 取最低位，回溯时用异或撤销。
最坏复杂度相同（m 为空格数），但最少候选优先能极大减少分支，难题上通常快几个数量级。位运算判重比集合查询更快，代价是代码更难读。
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
row = [0] * 9
col = [0] * 9
box = [0] * 9
empty = []
for i in range(9):
for j in range(9):
c = board[i][j]
if c == '.':
empty.append((i, j))
else:
bit = 1 << (int(c) - 1)
row[i] |= bit
col[j] |= bit
box[i // 3 * 3 + j // 3] |= bit
def dfs(left):
if left == 0:
return True
best, best_mask, best_cnt = -1, 0, 10
for k, (i, j) in enumerate(empty):
if board[i][j] != '.':
continue
mask = ~(row[i] | col[j] | box[i // 3 * 3 + j // 3]) & 0x1FF
cnt = bin(mask).count('1')
if cnt < best_cnt:
best, best_mask, best_cnt = k, mask, cnt
if cnt <= 1:
break
if best_cnt == 0:
return False
i, j = empty[best]
b = i // 3 * 3 + j // 3
mask = best_mask
while mask:
bit = mask & -mask
mask ^= bit
board[i][j] = str(bit.bit_length())
row[i] |= bit
col[j] |= bit
box[b] |= bit
if dfs(left - 1):
return True
row[i] ^= bit
col[j] ^= bit
box[b] ^= bit
board[i][j] = '.'
return False
dfs(len(empty))class Solution {
int[] row = new int[9], col = new int[9], box = new int[9];
List<int[]> empty = new ArrayList<>();
char[][] board;
public void solveSudoku(char[][] board) {
this.board = board;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') {
empty.add(new int[]{i, j});
} else {
int bit = 1 << (c - '1');
row[i] |= bit; col[j] |= bit; box[i / 3 * 3 + j / 3] |= bit;
}
}
}
dfs(empty.size());
}
boolean dfs(int left) {
if (left == 0) return true;
int best = -1, bestMask = 0, bestCnt = 10;
for (int k = 0; k < empty.size(); k++) {
int i = empty.get(k)[0], j = empty.get(k)[1];
if (board[i][j] != '.') continue;
int mask = ~(row[i] | col[j] | box[i / 3 * 3 + j / 3]) & 0x1FF;
int cnt = Integer.bitCount(mask);
if (cnt < bestCnt) {
best = k; bestMask = mask; bestCnt = cnt;
if (cnt <= 1) break;
}
}
if (bestCnt == 0) return false;
int i = empty.get(best)[0], j = empty.get(best)[1];
int b = i / 3 * 3 + j / 3;
for (int mask = bestMask; mask != 0; mask &= mask - 1) {
int bit = mask & -mask;
board[i][j] = (char) ('1' + Integer.numberOfTrailingZeros(bit));
row[i] |= bit; col[j] |= bit; box[b] |= bit;
if (dfs(left - 1)) return true;
row[i] ^= bit; col[j] ^= bit; box[b] ^= bit;
}
board[i][j] = '.';
return false;
}
}class Solution {
public:
int row[9], col[9], box[9];
vector<pair<int, int>> empty;
bool dfs(vector<vector<char>>& board, int left) {
if (left == 0) return true;
int best = -1, bestMask = 0, bestCnt = 10;
for (int k = 0; k < (int)empty.size(); k++) {
auto [i, j] = empty[k];
if (board[i][j] != '.') continue;
int mask = ~(row[i] | col[j] | box[i / 3 * 3 + j / 3]) & 0x1FF;
int cnt = __builtin_popcount(mask);
if (cnt < bestCnt) {
best = k; bestMask = mask; bestCnt = cnt;
if (cnt <= 1) break;
}
}
if (bestCnt == 0) return false;
auto [i, j] = empty[best];
int b = i / 3 * 3 + j / 3;
for (int mask = bestMask; mask; mask &= mask - 1) {
int bit = mask & -mask;
board[i][j] = '1' + __builtin_ctz(bit);
row[i] |= bit; col[j] |= bit; box[b] |= bit;
if (dfs(board, left - 1)) return true;
row[i] ^= bit; col[j] ^= bit; box[b] ^= bit;
}
board[i][j] = '.';
return false;
}
void solveSudoku(vector<vector<char>>& board) {
for (int k = 0; k < 9; k++) row[k] = col[k] = box[k] = 0;
empty.clear();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') {
empty.push_back({i, j});
} else {
int bit = 1 << (c - '1');
row[i] |= bit; col[j] |= bit; box[i / 3 * 3 + j / 3] |= bit;
}
}
}
dfs(board, empty.size());
}
};func solveSudoku(board [][]byte) {
var row, col, box [9]int
empty := [][2]int{}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
c := board[i][j]
if c == '.' {
empty = append(empty, [2]int{i, j})
} else {
bit := 1 << (c - '1')
row[i] |= bit
col[j] |= bit
box[i/3*3+j/3] |= bit
}
}
}
var dfs func(left int) bool
dfs = func(left int) bool {
if left == 0 {
return true
}
best, bestMask, bestCnt := -1, 0, 10
for k, e := range empty {
i, j := e[0], e[1]
if board[i][j] != '.' {
continue
}
mask := ^(row[i] | col[j] | box[i/3*3+j/3]) & 0x1FF
cnt := bits.OnesCount(uint(mask))
if cnt < bestCnt {
best, bestMask, bestCnt = k, mask, cnt
if cnt <= 1 {
break
}
}
}
if bestCnt == 0 {
return false
}
i, j := empty[best][0], empty[best][1]
b := i/3*3 + j/3
for mask := bestMask; mask != 0; mask &= mask - 1 {
bit := mask & -mask
board[i][j] = byte('1' + bits.TrailingZeros(uint(bit)))
row[i] |= bit
col[j] |= bit
box[b] |= bit
if dfs(left - 1) {
return true
}
row[i] ^= bit
col[j] ^= bit
box[b] ^= bit
}
board[i][j] = '.'
return false
}
dfs(len(empty))
}var solveSudoku = function(board) {
const row = new Array(9).fill(0), col = new Array(9).fill(0), box = new Array(9).fill(0);
const empty = [];
const popcount = (m) => { let c = 0; while (m) { m &= m - 1; c++; } return c; };
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const c = board[i][j];
if (c === '.') {
empty.push([i, j]);
} else {
const bit = 1 << (Number(c) - 1);
row[i] |= bit; col[j] |= bit; box[Math.floor(i / 3) * 3 + Math.floor(j / 3)] |= bit;
}
}
}
const dfs = (left) => {
if (left === 0) return true;
let best = -1, bestMask = 0, bestCnt = 10;
for (let k = 0; k < empty.length; k++) {
const [i, j] = empty[k];
if (board[i][j] !== '.') continue;
const mask = ~(row[i] | col[j] | box[Math.floor(i / 3) * 3 + Math.floor(j / 3)]) & 0x1FF;
const cnt = popcount(mask);
if (cnt < bestCnt) {
best = k; bestMask = mask; bestCnt = cnt;
if (cnt <= 1) break;
}
}
if (bestCnt === 0) return false;
const [i, j] = empty[best];
const b = Math.floor(i / 3) * 3 + Math.floor(j / 3);
for (let mask = bestMask; mask; mask &= mask - 1) {
const bit = mask & -mask;
board[i][j] = String(31 - Math.clz32(bit) + 1);
row[i] |= bit; col[j] |= bit; box[b] |= bit;
if (dfs(left - 1)) return true;
row[i] ^= bit; col[j] ^= bit; box[b] ^= bit;
}
board[i][j] = '.';
return false;
};
dfs(empty.length);
};function solveSudoku(board: string[][]): void {
const row: number[] = new Array(9).fill(0), col: number[] = new Array(9).fill(0), box: number[] = new Array(9).fill(0);
const empty: number[][] = [];
const popcount = (m: number): number => { let c = 0; while (m) { m &= m - 1; c++; } return c; };
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const c = board[i][j];
if (c === '.') {
empty.push([i, j]);
} else {
const bit = 1 << (Number(c) - 1);
row[i] |= bit; col[j] |= bit; box[Math.floor(i / 3) * 3 + Math.floor(j / 3)] |= bit;
}
}
}
const dfs = (left: number): boolean => {
if (left === 0) return true;
let best = -1, bestMask = 0, bestCnt = 10;
for (let k = 0; k < empty.length; k++) {
const [i, j] = empty[k];
if (board[i][j] !== '.') continue;
const mask = ~(row[i] | col[j] | box[Math.floor(i / 3) * 3 + Math.floor(j / 3)]) & 0x1FF;
const cnt = popcount(mask);
if (cnt < bestCnt) {
best = k; bestMask = mask; bestCnt = cnt;
if (cnt <= 1) break;
}
}
if (bestCnt === 0) return false;
const [i, j] = empty[best];
const b = Math.floor(i / 3) * 3 + Math.floor(j / 3);
for (let mask = bestMask; mask; mask &= mask - 1) {
const bit = mask & -mask;
board[i][j] = String(31 - Math.clz32(bit) + 1);
row[i] |= bit; col[j] |= bit; box[b] |= bit;
if (dfs(left - 1)) return true;
row[i] ^= bit; col[j] ^= bit; box[b] ^= bit;
}
board[i][j] = '.';
return false;
};
dfs(empty.length);
}