DIV CSS 佈局教程網

用 JavaScript 寫數獨求解器:候選標記、分支回溯與唯一解檢查
編輯:關於JavaScript     

寫一個數獨求解器,是練習「約束滿足問題(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 都能達到同樣效果,也更容易看到堆疊與候選數的變化過程。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved