摘要：數(shù)獨技巧直觀法候選數(shù)法相關(guān)二十格一個數(shù)字只與其所在行列及小九宮格的二十格相關(guān)我的思路精心設計了有效性判定函數(shù)，最多一次遍歷個小單元格就能做出方案的有效性判定。

看《算法的樂趣》，試著用非遞歸窮舉來解數(shù)獨，看效率如何！

數(shù)獨游戲，經(jīng)典的為9×9=81個單元格組成的九宮格，同時也形成了3×3=9個小九宮格，要求在81個小單元格中填入數(shù)字1~9，并且數(shù)字在每行每列及每個小九宮格中都不能重復。

直觀法

候選數(shù)法

相關(guān)二十格：一個數(shù)字只與其所在行列及小九宮格的二十格相關(guān)

精心設計了有效性判定函數(shù)，最多一次遍歷81個小單元格就能做出方案的有效性判定。

同理設計了相關(guān)20格判定，一次0~9的循環(huán)就完成有效性判定。

用數(shù)組模擬堆棧，為搜索提供回溯信息。

利用對象具有map性質(zhì)，來輔助判斷方案的有效性，大大簡化了算法。

只用了一個二維數(shù)組存儲數(shù)獨方案，一個一維數(shù)組作堆棧，一個布爾變量作回溯標識。

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;

充分利用了javascript對象的哈希特性，為了方便調(diào)試，判定有效時函數(shù)的返回值為0，無效時分三種情況，行沖突、列沖突、小九宮格沖突，分別返回1，2，3。前期判定用了它，后來增加了相關(guān)二十格判定，在找答案時這個函數(shù)就用不上了。

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]            //一次內(nèi)循環(huán)同時完成行列的判定
            if(row[cur1])                    //當前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷，key為0時值為0，不需要額外判斷
                return 1;                    //返回錯誤代碼
            else
                row[cur1] = cur1            //當前元素未在行中出現(xiàn)，存入輔助變量中   
            if(col[cur2])                    //列的判定與行類似，優(yōu)化掉零的判斷，key為0時值為0，不需要額外判斷
                return 2;
            else
                col[cur2] = cur2;
            let key = Math.floor(i/3)+"-"+Math.floor(j/3)        //為不同的小九宮格生成不同的key
            if(subSudo[key]){                 //小九宮格中已經(jīng)有元素，優(yōu)化掉零的判斷，key為0時值為0，不需要額外判斷
                if(subSudo[key][cur1])        //對某一個小九宮格的判定與行類似
                    return 3
                else
                    subSudo[key][cur1] = cur1
            }else{                            //這是某小九宮格中的第一個元素
                subSudo[key] = {}             //為小九宮格新建一個輔助變量，并將第一個元素存入其中
                subSudo[key][cur1] = cur1
            }                  
        }
    }
    return 0;                                //程序能運行到這，說明方案有效
}

原理同整體判定，亮點在小九宮格的定位上。

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){                                        //當前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷，key為0時值為0，不需要額外判斷
            if(row[cur1])
                return 1;                                //返回錯誤代碼
            else
                row[cur1] = cur1                        //當前元素未在行中出現(xiàn)，存入輔助變量中
        }
        if(cur2){                                        //列的判定與行類似，優(yōu)化掉零的判斷，key為0時值為0，不需要額外判斷
            if(col[cur2])
                return 2;
            else
                col[cur2] = cur2;
        }
        //轉(zhuǎn)化循環(huán)變量到小九宮格的坐標
        let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)]
        if(subSudo[key])                                //九宮格判定與行類似，優(yōu)化掉零的判斷，key為0時值為0，不需要額外判斷
            return 3
        else
            subSudo[key] = key
    }
    return 0;
}

利用元素狀態(tài)初值為零的元素即為待定的特性，并加上堆棧的輔助，沒有再開辟額外的存儲空間。

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){                              //循環(huán)找到下一個合法值
                    problem[i][j] = k;                    //填值
                    if(check20Grid(problem,i,j) == 0){    //判定合法，相關(guān)二十格判定
                        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{                                        //當前位置數(shù)字為題目給定
                j++;
            }
        }
    }
    return 1;                                            //成功找到一組解
}

代碼托管在開源中國，其中的sudoku.js即數(shù)獨解法。

https://git.oschina.net/zhoutk/test.git

書上提到的難度為10.7的題目的答案，1秒內(nèi)解決，效率還行。

[ [ 8, 1, 2, 7, 5, 3, 6, 4, 9 ],
  [ 9, 4, 3, 6, 8, 2, 1, 7, 5 ],
  [ 6, 7, 5, 4, 9, 1, 2, 8, 3 ],
  [ 1, 5, 4, 2, 3, 7, 8, 9, 6 ],
  [ 3, 6, 9, 8, 4, 5, 7, 2, 1 ],
  [ 2, 8, 7, 1, 6, 9, 5, 3, 4 ],
  [ 5, 2, 1, 9, 7, 4, 3, 6, 8 ],
  [ 4, 3, 8, 5, 2, 6, 9, 1, 7 ],
  [ 7, 9, 6, 3, 1, 8, 4, 5, 2 ] ]