數獨規則
數獨游戲，經典的為9×9=81個單元格組成的九宮格，同時也形成了3×3=9個小九宮格，要求在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.方案有效性判定：
充分利用了javascript對象的哈希特性，為了方便調試，判定有效時函數的返回值為0，無效時分三種情況，行沖突、列沖突、小九宮格沖突，分別返回1，2，3。前期判定用了它，后來增加了相關二十格判定，在找答案時這個函數就用不上了。
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]) //當前元素已經在行中出現，優化掉零的判斷，key為0時值為0，不需要額外判斷 return 1; //返回錯誤代碼 else row[cur1] = cur1 //當前元素未在行中出現，存入輔助變量中 if(col[cur2]) //列的判定與行類似，優化掉零的判斷，key為0時值為0，不需要額外判斷 return 2; else col[cur2] = cur2; let key = Math.floor(i/3)+'-'+Math.floor(j/3) //為不同的小九宮格生成不同的key if(subSudo[key]){ //小九宮格中已經有元素，優化掉零的判斷，key為0時值為0，不需要額外判斷 if(subSudo[key][cur1]) //對某一個小九宮格的判定與行類似 return 3 else subSudo[key][cur1] = cur1 }else{ //這是某小九宮格中的第一個元素 subSudo[key] = {} //為小九宮格新建一個輔助變量，并將第一個元素存入其中 subSudo[key][cur1] = cur1 } } } return 0; //程序能運行到這，說明方案有效}3.相關二十格判定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){ //當前元素已經在行中出現，優化掉零的判斷，key為0時值為0，不需要額外判斷 if(row[cur1]) return 1; //返回錯誤代碼 else row[cur1] = cur1 //當前元素未在行中出現，存入輔助變量中 } if(cur2){ //列的判定與行類似，優化掉零的判斷，key為0時值為0，不需要額外判斷 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]) //九宮格判定與行類似，優化掉零的判斷，key為0時值為0，不需要額外判斷 return 3 else subSudo[key] = key } return 0;}4.遍歷求解
利用元素狀態初值為零的元素即為待定的特性，并加上堆棧的輔助，沒有再開辟額外的存儲空間。
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) //無解判斷，返回0 return 0; i=rt[0] //穿越 j=rt[1] flag = true; } }else{ //當前位置數字為題目給定 j++; } } } return 1; //成功找到一組解}新聞熱點
疑難解答
