寫一個數獨求解器,是練習「約束滿足問題(CSP)」最經典的題目。它的解法其實完全模仿人類的思考過程:先把能確定的格子填掉,遇到多個候選時就試一個、記下備案,錯了就退回上一個決策點。
本文拆解一個完整的瀏覽器版數獨求解器,重點在三件事:如何標記候選數、如何用位元運算加速衝突檢查、如何驗證答案唯一。
階段一:初步整理。 拿到題目後,先根據已知條件整理出所有「確定項」,並為每一格標記「可能選項」。對應程式中的 refreshStat()。
階段二:猜測/驗證循環。 對「可能選項」逐一嘗試,驗證是否違背現有條件。每個新分支的最終結果只有兩種:得出答案,或判定出錯。對應 setOne() 與 choose()。
階段三:唯一性檢查。 若所有路徑搜完發現答案不止一個,這道題目其實是不合格的——標準數獨必須有唯一解。這段驗證邏輯是很多求解器會省略、但實際上很重要的一步。
主循環寫得極簡潔:
while(true){
var a = setOne(); // 嘗試填入確定的格子
var b = refreshStat(); // 重新統計候選
if(!a || b){ // 若 a==false 或 b==true,則跳出循環
break;
}
}
實際人腦思考時,也是先遍歷選項較少的分支。所以程式的分支順序是:確定的點 → 2 叉分支 → 3 叉分支 → ……,選項越少的分支優先驗證,能最快排除錯誤。
棋盤用 81 個 <input> 組成,每格給一個 tabindex,並攔截方向鍵讓焦點在九宮格中移動——上鍵跳 -9、下鍵跳 +9、左右鍵跳 ±1:
function keygo(evt, obj){
key = window.event ? evt.keyCode : evt.which;
var next = obj.tabIndex;
var inputs = document.getElementsByTagName("input");
if (key == 38){ // ↑
if (next - 9 >= 0) inputs[next - 9].select()
}
if (key == 40){ // ↓
if (next + 9 < 81) inputs[next + 9].select()
}
if (key == 37){ // ←
if (next - 1 >= 0) inputs[next - 1].select()
}
if (key == 39){ // →
if (next + 1 < 81) inputs[next + 1].select();
}
}
棋盤本身用迴圈動態產生,並用 i % 3 / j % 3 判斷邊框粗細,把九宮格的三三分隔線畫出來:
var maxRow = 9, maxCol = 9;
var strTbody = ["<table id='sodukuTable' border='0'><tbody>"];
for(var i = 0; i < maxRow; i++){
strTbody.push("<tr>");
for(var j = 0; j < maxCol; j++){
strTbody.push("<td style='border-left:" + (j % 3 == 0 ? 1 : 0)
+ "px solid black ;border-right:" + (j % 3 == 2 ? 1 : 0)
+ "px solid black;border-top:" + (i % 3 == 0 ? 1 : 0)
+ "px solid black;border-bottom:" + (i % 3 == 2 ? 1 : 0) + "px solid black;' >"
+ "<input style='width:20px;' tabindex='" + (i * 9 + j)
+ "' onclick='check(this);' onKeyUp='return keygo(event,this)' type='text'
id='input" + (i * 9 + j) + "' name='n" + (i * 9 + j) + "' value='" + i + j + "' ></td>");
}
strTbody.push("</tr>");
}
strTbody.push("</tbody></table>");
這是整份程式碼最聰明的地方。判斷某格能不能填 num,直觀做法是三個迴圈分別掃所屬列、行、宮。這裡改用位元遮罩:rows[x]、columns[y]、blook[] 三個陣列各存一個整數,第 n 個 bit 為 1 代表該數字已被使用。
function CheckNumInput(array, num, x, y) {
// 目標: 沖突檢查 參數 array:矩陣 num:檢測值 x/y:檢測位置
// 行列宮均無沖突, return true;
// 發現沖突, return false;
if (((rows[x] & (1 << num)) == 0)
&& (columns[y] & (1 << num)) == 0
&& (blook[parseInt(x / 3) * 3 + parseInt(y / 3)] & (1 << num)) == 0) {
return true;
}
return false;
}
1 << num 把第 num 位設為 1,用 & 做 AND 就能 O(1) 判斷該數字是否已出現。填入時用 |= 更新:
function refreshStat3(num, x, y) { // 更新行列宮
rows[x] |= 1 << num;
columns[y] |= 1 << num;
blook[parseInt(x / 3) * 3 + parseInt(y / 3)] |= 1 << num;
}
宮的索引 parseInt(x/3) * 3 + parseInt(y/3) 把 (row, col) 座標映射成 0–8 的宮編號,這個換算式在任何九宮格問題裡都用得上。
refreshStat() 負責掃過整個盤面,為每個空格統計剩餘可選數字,寫進 candidatNum[i][j][0](數量)與 candidatNum[i][j][1](位元遮罩):
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
if (grid[i][j] != 0) {
candidatNum[i][j][0] = 0;
continue;
}
var size = 0;
over = false;
for (var k = 1; k < 10; k++) {
if (CheckNumInput(grid, k, i, j)) {
candidatNum[i][j][1] |= 1 << k;
candidatNum[i][j][10] = k;
size++;
} else {
candidatNum[i][j][1] &= ~(1 << k);
}
}
candidatNum[i][j][0] = size; //標記剩余選項數目
}
}
回溯用「紙」與「廢紙」兩個計數器(papers / discards)追蹤,並用一個 Step 物件把決策前的盤面快照存進堆疊:
function Step(current1, arrys){
this.temp1 = new Array();
this.step = [arrys[0], arrys[1], arrys[2]];
for (var i = 0; i < 9; i++) {
this.temp1[i] = new Array();
for (var j = 0; j < 9; j++) {
this.temp1[i][j] = current1[i][j];
}
}
}
function push(current1, i, j, n) {
var s = new Step(current1, [ i, j, n ]);
steps.push(s);
}
function pop(){
var step = steps.pop();
discards++;
grid = step.temp1;
grid[step.step[0]][step.step[1]] = step.step[2];
return step;
}
setOne() 則是求解主軸:先找出「唯一候選」的格子直接填入;若發現某格候選為 0,代表走錯路,就 pop() 回退:
if (grid[i][j] == 0 && candidatNum[i][j][0] == 0 ||
(candidatNum[i][j][0] == 1 && !CheckNumInput(grid, candidatNum[i][j][10], i, j))) {
if (grid[i][j] == 0) result = false;
if (steps.length > 0) { // 回退
pop(); // 當前標簽已經被證明邏輯錯誤,廢棄
return true;
} else {
if (!success) alert("棧為空 結束!"); //題目出錯,結束
return false;
}
}
if (candidatNum[i][j][0] == 1) { //唯一選擇
grid[i][j] = candidatNum[i][j][10]; // 更新矩陣
refreshStat3(candidatNum[i][j][10], i, j); // 更新行列宮
candidatNum[i][j][0] = 0; // 標記已選
result = true;
continue;
}
當沒有唯一候選時,choose() 接手建立分支。它優先找「只有 2 種選擇」的格子(2 叉分支),把其中一個選項推入堆疊備查,另一個當場假設並驗算。若全盤找不到 2 叉分支,才退而尋找 3 叉分支:
if (candidatNum[i][j][0] == 2) { // 有2種選擇
binarynode = true;
var found = -1;
for (var k = 1; k < 10; k++) {
if ((candidatNum[i][j][1] & (1 << k)) > 0) {
if (found > 0) {
papers++;
push(grid, i, j, k); // 把備用選項存進堆疊
} else {
found = k; // 第一個選項當場採用
}
}
}
grid[i][j] = found;
candidatNum[i][j][0] = 0; // 在當前標簽上標記已選
return true;
}
算出答案後,程式會比較 papers(產生過幾個分支)與 discards(丟棄過幾個分支)。若兩者不等,代表還有未驗證的分支,於是再 pop() 回去把另一條路走一遍,看是否會得到不同答案:
if (papers != discards){
if (steps.length > 0) { // 回退
pop(); // 當前標簽廢棄
while(true){
var a = setOne();
var b = refreshStat();
if(!a || b) break;
}
if (b) {
alert("答案不唯一!記錄!");
out(grid);
} else {
alert("答案唯一!!");
}
}
}
另外還有一個實用功能:paste() 允許把 81 位數字的題目字串直接貼進來,程式會用 replace(/[^0-9]/g, '') 濾掉換行與空白,再依序填入棋盤。
位元遮罩取代多重迴圈。 用整數的 bit 表示「哪些數字已用過」,把每次衝突檢查從 O(27) 降到 O(1)。這是在 9×9 這種小型盤面上仍然能有感提速的經典技巧。
「快照 + 堆疊」實作回溯。 每個決策點存一份完整盤面副本,回退時直接還原,不必反向撤銷每一步操作。實作簡單、不易出錯,代價是記憶體——對 81 格而言完全划算。
唯一性驗證是品質指標。 能解出來只是及格,能判斷「這題出得好不好」才是進階。這一步把求解器從「工具」提升為「驗題工具」。
原文建議使用 IE 瀏覽器並按 F12 開啟除錯模式觀察;今天用任何現代瀏覽器的 DevTools 都能達到同樣效果,也更容易看到堆疊與候選數的變化過程。