資源描述：
《javascript遍歷求解數(shù)獨(dú)問題的主要思路小結(jié)_javascript技巧》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、JavaScript遍歷求解數(shù)獨(dú)問題的主要思路小結(jié)數(shù)獨(dú)規(guī)則數(shù)獨(dú)游戲，經(jīng)典的為9X9=81個(gè)單元格組成的九宮格，同時(shí)也形成了3X3=9個(gè)小九宮格，要求在81個(gè)小單元格中填入數(shù)字廣9,并且數(shù)字在每行每列及每個(gè)小九宮格中都不能重復(fù)。數(shù)獨(dú)技巧?直觀法?候選數(shù)法?相關(guān)二十格：一個(gè)數(shù)字只?其所在行列及小九宮格的二十格相關(guān)我的思路?精心設(shè)計(jì)了有效性判定函數(shù)，最多一次遍歷81個(gè)小單元格就能做出方案的冇效性判定。?同理設(shè)計(jì)了相關(guān)20格判定，一次0?9的循環(huán)就完成有效性判定。?用數(shù)組模擬堆棧，為搜索提供回溯信息。?利用對(duì)象具有map性質(zhì)，來(lái)輔助判斷方案的
2、有效性，人人簡(jiǎn)化了算法。方案設(shè)計(jì)與實(shí)現(xiàn)只用了一個(gè)二維數(shù)組存儲(chǔ)數(shù)獨(dú)方案，一個(gè)一維數(shù)組作堆棧，一個(gè)布爾變量作回溯標(biāo)識(shí)。1?變量定義：varproblem二[//這是書上提到的難度10.7的題[&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,&5,0,0,0,1,0],[0,9,0,0,0,0,4,0,0]
3、varstack二[],flag二false;2.方案有效性判定：充分利用了javascript對(duì)彖的哈希特性，為了方便調(diào)試，判定有效時(shí)函數(shù)的返回值為0,無(wú)效吋分三種情況，行沖突、列沖突、小九宮格沖突，分別返回1,2,3o前期判定用了它，后來(lái)増加了相關(guān)二十格判定，在找答案時(shí)這個(gè)函數(shù)就用不上了。functioncheckValid(sudo){letsubSudo二{}//輔助變量，用來(lái)判定小九宮格是否沖突for(leti=0;i<9;i++){letrow={},col={}//輔助變量，用來(lái)判定彳亍、列是否沖突for(letj=0;
4、j<9;j++){letcurl=sudo[i][j],cur2=sudo[j][i]//一次內(nèi)循環(huán)同時(shí)完成行列的判定if(row[curl])//當(dāng)前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷,key為0時(shí)值為0,不需要額外判斷return1;elserow[curl]=curlif(col[cur2])//返回錯(cuò)誤代碼〃當(dāng)前元素未在行中岀現(xiàn)，存入輔助變量中//列的判定與行類似，優(yōu)化掉零的判斷，key為0時(shí)值為0,不需要額外判斷return2;elsecol[cur2]二cur2;letkey=Math,floor(i/3)+，+Math.
5、floor(j/3)//為不同的小九宮格生成不同的keyif(subSudo[key]){//小九宮格小已經(jīng)有元素，優(yōu)化掉零的判斷，key為0時(shí)值為0,不需要額外判斷if(subSudo[key][curl])//對(duì)某一個(gè)小九宮格的判定與行類似return3elsesubSudo[key][curl]=curl}else{//這是某小九宮格中的第一個(gè)元索subSudo[key]二{}//為小九宮格新建一個(gè)輔助變量，并將第一個(gè)元素存入其中subSudo[key][curl]=curl}return0;〃程序能運(yùn)行到這，說(shuō)明方案有效3?相
6、關(guān)二十格判定原理同整體判定，亮點(diǎn)在小九宮格的定位上。functioncheck20Grid(sudo,i,j){letrow={},col={},subSudo={}//輔助變量for(letk=0;k<9;k++){letcurl二sudo[i][k],cur2二sudo[k][j]if(curl){〃當(dāng)前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷，key為0時(shí)值為0,不需要額外判斷if(row[curl])return1;//返回錯(cuò)誤代碼eiserow[curl]二curl//當(dāng)而元素未在行中出現(xiàn),存入輔助變量屮1Jif(cur2){//
7、列的判定與行類似，優(yōu)化掉零的判斷，key為0時(shí)值為0,不需要額外判斷if(col[cur2])return2;elsecol[cur2]二cur2;}〃轉(zhuǎn)化循環(huán)變量到小九宮格的坐標(biāo)letkey=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時(shí)值為0,不需要額外判斷return3elsesubSudo[key]=key}return0;}4.遍歷求解利用元
8、素狀態(tài)初值為零的元素即為待定的特性，并加上堆棧的輔助，沒有再開辟額外的存儲(chǔ)空間。functionfindAnswcr(){for(leti=0;i<9;i++){for(letj=0;j<9;){if(problem[i
