數獨規則
經典數獨由 9×9=81 個格子組成,同時形成 9 個 3×3 的小九宮格。要求在 81 格中填入 1~9,且每行、每列與每個小九宮格內數字都不能重複。
解題技巧
我的思路
方案設計
只用了三個資料結構:一個二維陣列存盤面、一個一維陣列當堆疊、一個布林變數當回溯標記。
1. 變數定義
var problem = [ //書上難度 10.7 的題目 [8,0,0,0,0,0,0,0,0], [0,0,3,6,0,0,0,0,0], [0,7,0,0,9,0,2,0,0], [0,5,0,0,0,7,0,0,0], [0,0,0,0,4,5,7,0,0], [0,0,0,1,0,0,0,3,0], [0,0,1,0,0,0,0,6,8], [0,0,8,5,0,0,0,1,0], [0,9,0,0,0,0,4,0,0] ] var stack = [],flag = false;
2. 整體有效性判定
這裡充分利用 JS 物件的雜湊特性。為了方便除錯,有效時回傳 0,無效時分三種情況:行衝突回 1、列衝突回 2、小九宮格衝突回 3。由於 key 為 0 時值為 0(falsy),天然就不必另外判斷空格。
function checkValid(sudo){ let subSudo = {} //輔助變量,判定小九宮格是否衝突 for(let i = 0; i<9; i++){ let row = {}, col = {} //輔助變量,判定行、列是否衝突 for(let j = 0; j<9; j++){ let cur1 = sudo[i][j], cur2 = sudo[j][i] //一次內循環同時完成行列判定 if(row[cur1]) return 1; else row[cur1] = cur1 if(col[cur2]) return 2; else col[cur2] = cur2; let key = Math.floor(i/3)+'-'+Math.floor(j/3) //為不同小九宮格生成不同 key if(subSudo[key]){ if(subSudo[key][cur1]) return 3 else subSudo[key][cur1] = cur1 }else{ subSudo[key] = {} subSudo[key][cur1] = cur1 } } } return 0; //能跑到這裡說明方案有效 }
3. 相關二十格判定
原理與整體判定相同,關鍵在於小九宮格的座標換算——把單一迴圈變數 k 映射成九宮格內的實際座標。
function check20Grid(sudo,i,j){ let row = {}, col = {}, subSudo = {} for(let k = 0; k < 9; k++){ let cur1 = sudo[i][k], cur2 = sudo[k][j] if(cur1){ if(row[cur1]) return 1; else row[cur1] = cur1 } if(cur2){ if(col[cur2]) return 2; else col[cur2] = cur2; } //轉化循環變量到小九宮格的坐標 let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)] if(subSudo[key]) return 3 else subSudo[key] = key } return 0; }
4. 遍歷求解
利用「值為 0 即待填」的特性搭配堆疊,不必額外開空間記錄狀態。遇到無解可走時就歸零並回溯到上一個決策點。
function findAnswer(){ for(let i = 0; i<9; i++){ for(let j = 0; j<9; ){ if(problem[i][j] === 0 || flag){ //首次處理或回溯到當前位置,兩者處理方式相同:值加 1 flag = false; let k = problem[i][j] + 1; while(k<10){ problem[i][j] = k; if(check20Grid(problem,i,j) == 0){ stack.push([i,j++]) break; } k++; } if(k>9){ problem[i][j] = 0; let rt = stack.pop(); if(!rt) return 0; //無解 i=rt[0] j=rt[1] flag = true; } }else{ j++; //題目已給定數字 } } } return 1; //成功找到一組解 }
整體來說,這份實作的取捨很清楚:以「相關二十格判定」取代全盤掃描,把每次嘗試的檢查成本壓到極低;再用堆疊取代遞迴,避免深層呼叫。若你只是要快速求解,也可以直接用啟發式候選數法,但作為演算法練習,這種回溯框架值得自己寫一遍。