京公网安备11010502063487号给定一个部分填好的 9×9 数独，把它填完。数独的规则是每行、每列、每个 3×3 宫里数字 1 到 9 各出现一次。做法是回溯：找一个空格，试填一个合法的数字，递归地去填后面的空格，走不通就撤销、换下一个数字。朴素的回溯按固定顺序填空格，能做但很慢；关键的加速是每一步先挑「候选数字最少」的空格：只有一个候选的空格是被"逼"出来的，没有候选的空格能让这条路立刻失败。本文用真实的填写次数展示这个加速的效果，给出五种语言的实现，并把求解过程做成分步演示。
完整题目见官方页面（链接在文末）。输入保证有解。基准解是最朴素的回溯：按行优先找第一个空格，依次试 1 到 9，逐个检查行、列、宫是否合法。数独题目的解不一定唯一，所以本题核对时不要求与基准解逐格相同，只检查：答案是一个完整合法的数独（每行每列每宫恰好是 1 到 9），并且保留了题目给出的所有数字。一共 8 组用例，覆盖：官方示例、已经填满的棋盘、只缺一个格子、缺四个格子、每隔几格挖一个、另外两道已知数字分别是 27 个和 23 个的题、一道只有 21 个已知数字的题：
输入 [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] 输出 ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] 输入 [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] 输出 ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] 输入 [["534678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","345286179"]] 输出 ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] 输入 [["..4678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","34528617."]] 输出 ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] 输入 [[".34.78.12","67.19.34.","1.83.25.7",".59.61.23","42.85.79.","7.39.48.6",".61.37.84","28.41.63.","3.52.61.9"]] 输出 ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] 输入 [["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]] 输出 ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
下面统计的是"往一个空格里放一个数字"的总次数（包括后来被撤销的），以及耗时，比较朴素回溯（按顺序填空格）和候选最少优先（用位掩码维护每行每列每宫已用的数字）：
填写次数（每次尝试往一个空格里放一个数字，含之后被撤销的）与耗时：朴素回溯 vs 候选最少优先 + 位掩码 官方示例（51 个空格）: 朴素回溯 4208 次 / 17.2 ms 候选最少优先 51 次 / 0.1 ms 只有 21 个已知数字的题目（60 个空格）: 朴素回溯 49558 次 / 205.3 ms 候选最少优先 14344 次 / 31.6 ms 只挖掉 4 个格子: 朴素回溯 4 次 / 0.0 ms 候选最少优先 4 次 / 0.0 ms
官方示例有 51 个空格：朴素回溯放了 4208 次，其中 4157 次是走错路之后又被撤销的；候选最少优先只放了 51 次，也就是没有任何一次撤销，每一步都只有一个候选。耗时是 14.0ms 对 0.1ms。只有 21 个已知数字的那道题，两种做法都需要大量回溯，朴素回溯放了 49558 次（168.2ms），候选最少优先放了 14344 次（32.7ms）：次数少了约 3.5 倍，耗时少了约 5 倍。耗时比次数的差距更大，一个可能的原因是每次填写的开销不同：朴素回溯每次都要扫描整行整列整宫检查合法性，位掩码只需要按位运算；我没有单独测量这两部分的开销。这些数字只在这三道题上测得，不同题目的差距可能很不一样。
用三个长度为 9 的整数数组 rows、cols、boxes，每个整数的第 d 位表示数字 d 是否已经在这行、这列、这宫里出现。把所有空格放在一个列表里，empties[0..k) 是已经填好的，empties[k..) 是还没填的。每次递归，扫描剩下的空格，算出每个空格的候选掩码（三个掩码取并再取反，只保留第 1 到 9 位），数出候选个数，挑最少的那个换到位置 k；如果有个空格候选数是 0，这条路走不通，直接返回；否则依次尝试这个空格的每个候选：填入、更新三个掩码、递归、撤销。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(board): g = [list(r) for r in board] rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9 # 每行、每列、每个宫已经用过的数字（位掩码，第 d 位表示数字 d） empties = [] for r in range(9): for c in range(9): if g[r][c] == ".": empties.append((r, c)) else: bit = 1 << int(g[r][c]) rows[r] |= bit cols[c] |= bit boxes[r // 3 * 3 + c // 3] |= bit def dfs(k): # empties[0:k] 已经填好，empties[k:] 还是空格 if k == len(empties): return True best, best_mask, best_cnt = k, 0, 10 for i in range(k, len(empties)): # 挑「候选数字最少」的空格先填：失败得早，分支少 r, c = empties[i] mask = ~(rows[r] | cols[c] | boxes[r // 3 * 3 + c // 3]) & 0x3FE cnt = bin(mask).count("1") if cnt < best_cnt: best, best_mask, best_cnt = i, mask, cnt if cnt <= 1: break if best_cnt == 0: # 有个空格一个候选都没有：这条路走不通 return False empties[k], empties[best] = empties[best], empties[k] r, c = empties[k] b = r // 3 * 3 + c // 3 m = best_mask while m: bit = m & -m m ^= bit g[r][c] = str(bit.bit_length() - 1) rows[r] |= bit cols[c] |= bit boxes[b] |= bit if dfs(k + 1): return True rows[r] ^= bit # 回溯：撤销这次填写 cols[c] ^= bit boxes[b] ^= bit g[r][c] = "." return False dfs(0) return ["".join(r) for r in g]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..4678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","34528617."]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [[".34.78.12","67.19.34.","1.83.25.7",".59.61.23","42.85.79.","7.39.48.6",".61.37.84","28.41.63.","3.52.61.9"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]] → ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
Java · 解法代码class Solution { private int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // 已经用过的数字（位掩码，第 d 位表示数字 d） private int[][] empties; private int n; public void solveSudoku(char[][] board) { List<int[]> list = new ArrayList<>(); for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r][c] == '.') { list.add(new int[]{r, c}); } else { int bit = 1 << (board[r][c] - '0'); rows[r] |= bit; cols[c] |= bit; boxes[r / 3 * 3 + c / 3] |= bit; } } } empties = list.toArray(new int[0][]); n = empties.length; dfs(board, 0); } private boolean dfs(char[][] board, int k) { // empties[0..k) 已经填好，empties[k..) 还是空格 if (k == n) return true; int best = k, bestMask = 0, bestCnt = 10; for (int i = k; i < n; i++) { // 挑「候选数字最少」的空格先填：失败得早，分支少 int r = empties[i][0], c = empties[i][1]; int mask = ~(rows[r] | cols[c] | boxes[r / 3 * 3 + c / 3]) & 0x3FE; int cnt = Integer.bitCount(mask); if (cnt < bestCnt) { best = i; bestMask = mask; bestCnt = cnt; if (cnt <= 1) break; } } if (bestCnt == 0) return false; // 有个空格一个候选都没有：这条路走不通 int[] tmp = empties[k]; empties[k] = empties[best]; empties[best] = tmp; int r = empties[k][0], c = empties[k][1], b = r / 3 * 3 + c / 3; for (int m = bestMask; m != 0; m &= m - 1) { int bit = m & -m; board[r][c] = (char) ('0' + Integer.numberOfTrailingZeros(bit)); rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; if (dfs(board, k + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit; // 回溯：撤销这次填写 } board[r][c] = '.'; return false; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..4678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","34528617."]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [[".34.78.12","67.19.34.","1.83.25.7",".59.61.23","42.85.79.","7.39.48.6",".61.37.84","28.41.63.","3.52.61.9"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]] → ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
Go · 解法代码import "math/bits" type solver struct { rows, cols, boxes [9]int // 已经用过的数字（位掩码，第 d 位表示数字 d） empties [][2]int board [][]byte } func (s *solver) dfs(k int) bool { // empties[0:k] 已经填好，empties[k:] 还是空格 if k == len(s.empties) { return true } best, bestMask, bestCnt := k, 0, 10 for i := k; i < len(s.empties); i++ { // 挑「候选数字最少」的空格先填：失败得早，分支少 r, c := s.empties[i][0], s.empties[i][1] mask := ^(s.rows[r] | s.cols[c] | s.boxes[r/3*3+c/3]) & 0x3FE if cnt := bits.OnesCount(uint(mask)); cnt < bestCnt { best, bestMask, bestCnt = i, mask, cnt if cnt <= 1 { break } } } if bestCnt == 0 { // 有个空格一个候选都没有：这条路走不通 return false } s.empties[k], s.empties[best] = s.empties[best], s.empties[k] r, c := s.empties[k][0], s.empties[k][1] b := r/3*3 + c/3 for m := bestMask; m != 0; m &= m - 1 { bit := m & -m s.board[r][c] = byte('0' + bits.TrailingZeros(uint(bit))) s.rows[r] |= bit s.cols[c] |= bit s.boxes[b] |= bit if s.dfs(k + 1) { return true } s.rows[r] ^= bit // 回溯：撤销这次填写 s.cols[c] ^= bit s.boxes[b] ^= bit } s.board[r][c] = '.' return false } func solveSudoku(board [][]byte) { s := &solver{board: board} for r := 0; r < 9; r++ { for c := 0; c < 9; c++ { if board[r][c] == '.' { s.empties = append(s.empties, [2]int{r, c}) } else { bit := 1 << (board[r][c] - '0') s.rows[r] |= bit s.cols[c] |= bit s.boxes[r/3*3+c/3] |= bit } } } s.dfs(0) }
$ go build -o bin . && ./bin < cases.jsonl [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..4678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","34528617."]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [[".34.78.12","67.19.34.","1.83.25.7",".59.61.23","42.85.79.","7.39.48.6",".61.37.84","28.41.63.","3.52.61.9"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]] → ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
JavaScript · 解法代码function solveSudoku(board) { // board 是 9×9 的字符数组，原地修改 const rows = new Array(9).fill(0), cols = new Array(9).fill(0), boxes = new Array(9).fill(0); // 已用数字的位掩码 const empties = []; const popcount = (x) => { let n = 0; while (x) { x &= x - 1; n++; } return n; }; for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] === ".") { empties.push([r, c]); } else { const bit = 1 << Number(board[r][c]); rows[r] |= bit; cols[c] |= bit; boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)] |= bit; } } } const dfs = (k) => { // empties[0..k) 已经填好，empties[k..) 还是空格 if (k === empties.length) return true; let best = k, bestMask = 0, bestCnt = 10; for (let i = k; i < empties.length; i++) { // 挑「候选数字最少」的空格先填：失败得早，分支少 const [r, c] = empties[i]; const mask = ~(rows[r] | cols[c] | boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)]) & 0x3FE; const cnt = popcount(mask); if (cnt < bestCnt) { best = i; bestMask = mask; bestCnt = cnt; if (cnt <= 1) break; } } if (bestCnt === 0) return false; // 有个空格一个候选都没有：这条路走不通 [empties[k], empties[best]] = [empties[best], empties[k]]; const [r, c] = empties[k]; const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); for (let m = bestMask; m; m &= m - 1) { const bit = m & -m; board[r][c] = String(31 - Math.clz32(bit)); rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; if (dfs(k + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit; // 回溯：撤销这次填写 } board[r][c] = "."; return false; }; dfs(0); }
$ node run.js < cases.jsonl [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..4678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","34528617."]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [[".34.78.12","67.19.34.","1.83.25.7",".59.61.23","42.85.79.","7.39.48.6",".61.37.84","28.41.63.","3.52.61.9"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]] → ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
C++ · 解法代码#include <utility> #include <vector> using namespace std; class Solution { int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0}; // 已经用过的数字（位掩码，第 d 位表示数字 d） vector<pair<int, int>> empties; bool dfs(vector<vector<char>>& board, int k) { // empties[0..k) 已经填好，empties[k..) 还是空格 if (k == (int)empties.size()) return true; int best = k, bestMask = 0, bestCnt = 10; for (int i = k; i < (int)empties.size(); i++) { // 挑「候选数字最少」的空格先填：失败得早，分支少 int r = empties[i].first, c = empties[i].second; int mask = ~(rows[r] | cols[c] | boxes[r / 3 * 3 + c / 3]) & 0x3FE; int cnt = __builtin_popcount(mask); if (cnt < bestCnt) { best = i; bestMask = mask; bestCnt = cnt; if (cnt <= 1) break; } } if (bestCnt == 0) return false; // 有个空格一个候选都没有：这条路走不通 swap(empties[k], empties[best]); int r = empties[k].first, c = empties[k].second, b = r / 3 * 3 + c / 3; for (int m = bestMask; m; m &= m - 1) { int bit = m & -m; board[r][c] = '0' + __builtin_ctz(bit); rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; if (dfs(board, k + 1)) return true; rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit; // 回溯：撤销这次填写 } board[r][c] = '.'; return false; } public: void solveSudoku(vector<vector<char>>& board) { for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r][c] == '.') { empties.push_back({r, c}); } else { int bit = 1 << (board[r][c] - '0'); rows[r] |= bit; cols[c] |= bit; boxes[r / 3 * 3 + c / 3] |= bit; } } } dfs(board, 0); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["534678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","345286179"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..4678912","672195348","198342567","859761423","4268.3791","713924856","961537284","287419635","34528617."]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [[".34.78.12","67.19.34.","1.83.25.7",".59.61.23","42.85.79.","7.39.48.6",".61.37.84","28.41.63.","3.52.61.9"]] → ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"] [["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]] → ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
共 8 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 8/8 Java 通过 8/8 Go 通过 8/8 JavaScript 通过 8/8 C++ 通过 8/8
这里的"通过"就是上面说的检验：答案是完整合法的数独并保留了给出的数字。
Python 版本另外做了 60 组随机对拍：从随机置换过数字的完整数独里，随机挖掉 20 到 50 个格子，每道题至少有一个解，用同样的检验标准核对答案（因为随机挖出来的题不一定有唯一解，所以不能与基准解逐格比较）。下面的报告里"solve 与 brute 的结果全部一致"在这一题的含义是：每一组的答案都通过了上面的检验。
随机对拍 60 组（从随机置换过数字的完整数独里随机挖掉 20 到 50 个格子（每题至少有一个解，但不一定唯一，所以只要求答案是完整合法的数独并保留题目给出的数字）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 8 组固定用例上验证过，没有做大规模随机对拍。这一题的耗时取决于题目本身的难度，没有做规模对比实验，上一节的填写次数对比就是主要的实测。
下面的演示用官方示例。运行器每一步都只挑候选最少的空格，这道题里每一步都只有一个候选，所以没有任何回溯，51 个空格逐个被"逼"出来，从第 (4,4) 格（行、列都从 0 开始计数）开始。琥珀色是刚填入的数字，绿色是本次求解已经填入的数字。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。想看到回溯，需要更难的题目，但那样的演示会有上万帧，这里没有做。