做算独方格的题库时我给每道题存了一份答案。校验这份答案是否合法只能证明题目至少有一个解。比如下面这道 4×4 数独左边四个空格有两种合法填法。题面 解一 解二 . . 3 4 1 2 3 4 2 1 3 4 3 4 1 2 3 4 1 2 3 4 1 2 . . 4 3 2 1 4 3 1 2 4 3 4 3 2 1 4 3 2 1 4 3 2 1两种填法的每行、每列、每个 2×2 宫都满足规则。如果求解器填完第一份就返回成功这道多解题也会通过检查。找到第一个解之后回到分叉处回溯会在一个空格上尝试每个候选数字。填出完整盘面时先把解的数量加一再撤销最后的填写继续检查还没有走过的分支。每个分支对应这个格子的一个取值。一个完整解只能沿着其中一条路径被找到因此计数不会重复。行、列或宫出现冲突时当前分支也无法扩展成合法解可以直接剪掉。搜索结果题库校验搜完后找到 0 个解无解搜完后找到 1 个解唯一解找到第 2 个解多解可以提前停止搜索预算耗尽校验未完成当前计数只表示已找到多少个多解只需要两份解就能确认。唯一解则需要搜完其余可行分支排除第二份解的可能。用位掩码找候选先试选择最少的格子4×4 数独只用数字 1 到 4可以用四个二进制位记录占用。0b0101表示 1 和 3 已经出现。把一个格子所在行、列、宫的占用合并再从0b1111中去掉这些位就得到它的候选集合。每次递归先选候选最少的空格。比如一格只有两种填法另一格有四种先处理前者可以减少当前分叉更早发现冲突。候选顺序只影响搜索过程判定仍依赖完整枚举或找到第二个解。下面是用 JavaScript 写的 4×4 经典数独示例0表示空格。budget限制访问的搜索节点数count最多记到2。functioncountSolutions4x4(givens,budget100_000){if(!Array.isArray(givens)||givens.length!16){thrownewTypeError(需要 16 个格子);}constboard[...givens];if(board.some(n!Number.isInteger(n)||n0||n4)){thrownewTypeError(格子只能填 0 到 4 的整数);}if(!Number.isSafeInteger(budget)||budget1){thrownewRangeError(搜索预算须为正整数);}constrowsArray(4).fill(0);constcolsArray(4).fill(0);constboxesArray(4).fill(0);constcellsboard.map((_,i){constrowMath.floor(i/4);constcoli%4;constboxMath.floor(row/2)*2Math.floor(col/2);return{row,col,box};});for(leti0;iboard.length;i){if(board[i]0)continue;const{row,col,box}cells[i];constbit1(board[i]-1);if((rows[row]|cols[col]|boxes[box])bit){return{count:0,exhausted:false};}rows[row]|bit;cols[col]|bit;boxes[box]|bit;}letcount0;letvisited0;letexhaustedfalse;functionsearch(){if(visitedbudget){exhaustedtrue;return;}visited;letindex-1;letchoices0;letfewest5;for(leti0;iboard.length;i){if(board[i]!0)continue;const{row,col,box}cells[i];constusedrows[row]|cols[col]|boxes[box];constmask0b1111~used;if(mask0)return;letsize0;for(letbitsmask;bits!0;bitsbits-1)size;if(sizefewest){indexi;choicesmask;fewestsize;}}if(index-1){count;return;}const{row,col,box}cells[index];for(letbitschoices;bits!0;bitsbits-1){constbitbits-bits;board[index]32-Math.clz32(bit);rows[row]|bit;cols[col]|bit;boxes[box]|bit;search();board[index]0;rows[row]~bit;cols[col]~bit;boxes[box]~bit;if(count2||exhausted)return;}}search();return{count,exhausted};}撤销时要同时清掉格子的数字和三份占用记录。尝试一个候选之前这个数字在对应行、列、宫都未出现因此递归返回后可以安全地清掉刚设置的位。用三道小题检查边界constboardOf(...rows)[...rows.join()].map(Number);constnoSolutionboardOf(1230,0004,0000,0000);constuniqueboardOf(1034,3412,0043,4321);constmultipleboardOf(0034,3412,0043,4321);console.log(countSolutions4x4(noSolution));// { count: 0, exhausted: false }console.log(countSolutions4x4(unique));// { count: 1, exhausted: false }console.log(countSolutions4x4(multiple));// { count: 2, exhausted: false }console.log(countSolutions4x4(multiple,5));// { count: 1, exhausted: true }第一题的已知数字没有直接重复但第一行最后一格只能填 4那一列已经有 4所以无解。第二题在开头的多解题左上角补了一个1正好排除另一种填法。最后一行仍用多解题只给搜索五个节点的预算。程序刚好找到第一份解还没机会检查另一条分支。单看count: 1会放过这道题校验时要同时看exhausted。题库用独立求解器验一遍算独方格的题库测试会把题面和规则交给一个独立参考求解器。它自行构建行、列、宫等约束搜索时只读取题面和对应题型的规则。等搜索结束测试才拿求得的解和题库预存答案对照。这样做能减少校验和应用共用一套逻辑时的盲区。比如应用的候选计算漏掉了某个约束独立求解器还有机会发现差异。经典题只需检查行列宫温度计、箭头、求和笼等变形题还要验证各自的附加规则。项目的全量用例逐题检查了 1308 道固定题目。每道题都要求搜索未耗尽预算、解的数量恰好为 1并且解与预存答案一致。开发时如果改动了题面、题库生成脚本或变形规则这个用例可以直接指出哪一道题出了问题。我把这些题做进了算独方格网页版可以从 4×4 开始练习。 算独方格网页版