JavaScript遍歷求解數(shù)獨問題的主要思路小結(jié)_javascript技巧

1、javascript遍歷求解數(shù)獨問題的主要思 路小結(jié)數(shù)獨規(guī)則數(shù)獨游戲，經(jīng)典的為9x9=81個單元格組成的九宮格，同時也形成了 3x3=9個 小九宮格，要求在81個小單元格中填入數(shù)字廣9,并且數(shù)字在每行每列及每個 小九宮格中都不能重復(fù)。數(shù)獨技巧 直觀法候選數(shù)法相關(guān)二十格：一個數(shù)字只其所在行列及小九宮格的二十格相關(guān)我的思路精心設(shè)計了有效性判定函數(shù)，最多一次遍歷81個小單元格就能做出方案的冇效性判 定。同理設(shè)計了相關(guān)20格判定，一次09的循環(huán)就完成有效性判定。用數(shù)組模擬堆棧，為搜索提供回溯信息。利用對象具有map性質(zhì)，來輔助判斷方案的有效性，人人簡化了算法。方案設(shè)計與實現(xiàn)只用了一個二維數(shù)組存儲數(shù)獨方

2、案，一個一維數(shù)組作堆棧，一個布爾變量作回溯 標識。1 變量定義：var problem二/這是書上提到的難度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 var s

3、tack 二,flag 二 false;2.方案有效性判定：充分利用了 javascript對彖的哈希特性，為了方便調(diào)試，判定有效時函數(shù)的返 回值為0,無效吋分三種情況，行沖突、列沖突、小九宮格沖突，分別返回1, 2, 3o前期判定用了它，后來増加了相關(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 c

4、url = sudoi j, cur2 = sudoj i/一次內(nèi)循環(huán)同時完成行列的判定if(rowcurl)/當前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷,key為0時值為0,不需要額外判斷return 1;elserowcurl = curlif(colcur2)/返回錯誤代碼當前元素未在行中岀現(xiàn)，存入輔助變量中 /列的判定與行類似，優(yōu)化掉零的判斷，key為0時值為0,不需要額外判斷return 2;elsecolcur2二 cur2;let key = math, floor(i/3)+，+math. floor(j/3)/為不同的小九宮格生成不同的keyif (subsudo key) /小

5、九宮格小已經(jīng)有元素，優(yōu)化掉零的判斷，key為0時值為0,不需要額外判斷if (subsudokey curl)/對某一個小九宮格的判定與行類似return 3elsesubsudokeycurl = curlelse/這是某小九宮格中的第一個元索subsudo key二/為小九宮格新建一個輔助變量，并將第一個元素存入其中subsudokeycurl = curlreturn 0;程序能運行到這，說明方案有效3 相關(guān)二十格判定原理同整體判定，亮點在小九宮格的定位上。function check20grid(sudo, i, j)let row = , col = , subsudo = /輔助變

6、量for (let k = 0; k < 9; k+) let curl 二 sudoik, cur2 二 sudokjif (curl) 當前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷，key為0時值為0,不需要額外判斷if (rowcurl)return 1;/返回錯誤代碼e i serowcurl二 curl/當而元素未在行中出現(xiàn),存入輔助變量屮1jif (cur2) /列的判定與行類似，優(yōu)化掉零的判斷，key為0時值為0,不需要額外判斷if(colcur2)return 2;elsecolcur2二 cur2;轉(zhuǎn)化循環(huán)變量到小九宮格的坐標let key = sudomath. floor

7、(i/3)*3 +math.floor (k/3)math, floor(j/3)*3+math. floor(k%3)if (subsudokey)/九宮格判定與行類似，優(yōu)化掉零的判斷，key為0時值為0,不需要額外判斷return 3else subsudokey = keyreturn 0;4.遍歷求解利用元素狀態(tài)初值為零的元素即為待定的特性，并加上堆棧的輔助，沒有再開辟 額外的存儲空間。function findanswcr() for (let i = 0; i<9; i+)for (let j = 0; j<9; ) if (problemi j = 0 | | flag) /當前位置為待定元素的首次處理或回溯到當前位置，兩種情況看似不同，其實處理相同，自加1即可 flag = false;let k = problemi j + 1;/搜索向下一個合法值邁進whilc(k<10) /循環(huán)找到卜一個合法值problemi j = k;/填值if (check20grid (problem, i, j) = 0) /判定合法,相關(guān)二十格判stack. push(i, j+)/存儲回溯點，并步進break;k+;if(k>9) problcmi j =