京公网安备11010502063487号给定一个 9×9 的数独棋盘，只需要判断已经填入的数字是否有效：每一行、每一列、每一个 3×3 的宫里，数字 1 到 9 都不能重复。棋盘不一定能被解出来，只检查已填的部分有没有冲突。做法是扫描一遍，用三组位掩码分别记录每行、每列、每个宫里出现过的数字，遇到冲突就返回。本文用真实的随机棋盘展示"只检查行和列、漏掉宫"的错误有多常见，给出五种语言的实现，并把扫描和冲突检测做成分步演示。
完整题目见官方页面（链接在文末）。棋盘在测试里用 9 个长度为 9 的字符串表示，. 表示空格。基准解把 27 个组（9 行、9 列、9 宫）全部列出来，逐组检查是否有重复数字，与位掩码的一次扫描是两种独立的写法。一共 12 组用例，覆盖：官方的两个示例、空棋盘、完整合法的棋盘、只有一个数字、行重复、列重复、宫重复（行和列都不重复）、不同行不同列不同宫的合法情形：
输入 [["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] 输出 true 输入 [["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] 输出 false 输入 [[".........",".........",".........",".........",".........",".........",".........",".........","........."]] 输出 true 输入 [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] 输出 true 输入 [["5........",".........",".........",".........",".........",".........",".........",".........","........."]] 输出 true 输入 [["5.......5",".........",".........",".........",".........",".........",".........",".........","........."]] 输出 false
行和列的检查很自然，容易漏掉 3×3 的宫。我用与对拍相同的随机棋盘生成器（从合法的完整数独出发，随机保留部分格子，再随机改写一两个格子）生成了 20000 个棋盘，看看只检查行和列的写法会漏掉多少：
随机 20000 个棋盘，其中 7879 个不合法（违反行、列、宫三条规则之一）； 只检查行和列、不检查 3×3 宫的写法：其中 652 个不合法的棋盘被误判成合法（占不合法棋盘的 8.3%）。
20000 个棋盘里有 7879 个不合法，其中 652 个（8.3%）是只违反宫规则、行和列都没有冲突的，只查行列的写法把它们误判成了合法。用例里也专门放了一组这样的数据：同一个宫里的两个 5，行、列都不同。
用三个长度为 9 的整数数组 rows、cols、boxes，每个整数的第 d 位表示数字 d 是否在这一行、这一列、这一宫里出现过。宫的编号是 r / 3 * 3 + c / 3。逐格扫描，空格跳过；遇到数字 d，看它对应的行、列、宫的掩码里第 d 位是否已经是 1，是就冲突，返回失败；否则把三个掩码的第 d 位置为 1。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(board): rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9 # 每一行、每一列、每个 3×3 宫各用一个 9 位的位掩码记录出现过的数字 for r in range(9): for c in range(9): ch = board[r][c] if ch == ".": continue bit = 1 << int(ch) b = r // 3 * 3 + c // 3 # (r, c) 所在的宫编号 0..8 if rows[r] & bit or cols[c] & bit or boxes[b] & bit: return False rows[r] |= bit cols[c] |= bit boxes[b] |= bit return True
$ 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"]] → true [["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → false [[".........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → true [["5........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["5.......5",".........",".........",".........",".........",".........",".........",".........","........."]] → false
Java · 解法代码class Solution { public boolean isValidSudoku(char[][] board) { int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // 每行、每列、每个宫各用一个位掩码 for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { char ch = board[r][c]; if (ch == '.') continue; int bit = 1 << (ch - '0'); int b = r / 3 * 3 + c / 3; // (r, c) 所在的宫编号 0..8 if ((rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[b] & bit) != 0) return false; rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; } } return true; } }
$ 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"]] → true [["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → false [[".........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → true [["5........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["5.......5",".........",".........",".........",".........",".........",".........",".........","........."]] → false
Go · 解法代码func isValidSudoku(board [][]byte) bool { var rows, cols, boxes [9]int // 每行、每列、每个宫各用一个位掩码 for r := 0; r < 9; r++ { for c := 0; c < 9; c++ { ch := board[r][c] if ch == '.' { continue } bit := 1 << (ch - '0') b := r/3*3 + c/3 // (r, c) 所在的宫编号 0..8 if rows[r]&bit != 0 || cols[c]&bit != 0 || boxes[b]&bit != 0 { return false } rows[r] |= bit cols[c] |= bit boxes[b] |= bit } } return true }
$ 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"]] → true [["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → false [[".........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → true [["5........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["5.......5",".........",".........",".........",".........",".........",".........",".........","........."]] → false
JavaScript · 解法代码function isValidSudoku(board) { const rows = new Array(9).fill(0), cols = new Array(9).fill(0), boxes = new Array(9).fill(0); // 每行、每列、每个宫各用一个位掩码 for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const ch = board[r][c]; if (ch === ".") continue; const bit = 1 << Number(ch); const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); // (r, c) 所在的宫编号 0..8 if (rows[r] & bit || cols[c] & bit || boxes[b] & bit) return false; rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; } } return true; }
$ 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"]] → true [["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → false [[".........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → true [["5........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["5.......5",".........",".........",".........",".........",".........",".........",".........","........."]] → false
C++ · 解法代码#include <vector> using namespace std; class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0}; // 每行、每列、每个宫各用一个位掩码 for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { char ch = board[r][c]; if (ch == '.') continue; int bit = 1 << (ch - '0'); int b = r / 3 * 3 + c / 3; // (r, c) 所在的宫编号 0..8 if ((rows[r] & bit) || (cols[c] & bit) || (boxes[b] & bit)) return false; rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit; } } return true; } };
$ 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"]] → true [["83..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]] → false [[".........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]] → true [["5........",".........",".........",".........",".........",".........",".........",".........","........."]] → true [["5.......5",".........",".........",".........",".........",".........",".........",".........","........."]] → false
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和"27 个组逐组查重"做了随机对拍，棋盘由生成器随机产生，其中约 39% 不合法（7879 / 20000，见上）：
随机对拍 20000 组（从一个合法的完整数独出发（随机置换数字），随机保留 20%/35%/50% 的格子，再以 60% 的概率随机改写 1 到 2 个格子（这样一半左右的棋盘会出现冲突）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题只扫描 81 个格子一遍，规模固定，所以没有做规模对比实验。
下面的演示用官方的无效示例：把第一行第一个数字从 5 改成 8。按行从左到右扫描：(0,0) 的 8、(0,1) 的 3……逐格记录，扫到 (2,2) 时发现它是 8，而它所在的左上角宫里已经有一个 8（在 (0,0)），冲突，棋盘无效。注意这一组数据里第 0 列也有两个 8（(0,0) 和 (3,0)），但扫描到那里之前，宫的冲突已经被发现了。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。