资源描述：
《javascript遍历求解数独问题的主要思路小结_javascript技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、JavaScript遍历求解数独问题的主要思路小结数独规则数独游戏，经典的为9X9=81个单元格组成的九宫格，同时也形成了3X3=9个小九宫格，要求在81个小单元格中填入数字广9,并且数字在每行每列及每个小九宫格中都不能重复。数独技巧•直观法•候选数法•相关二十格：一个数字只•其所在行列及小九宫格的二十格相关我的思路•精心设计了有效性判定函数，最多一次遍历81个小单元格就能做出方案的冇效性判定。•同理设计了相关20格判定，一次0〜9的循环就完成有效性判定。•用数组模拟堆栈，为搜索提供回溯信息。•利用对象具有map性质，来辅助判断方案的
2、有效性，人人简化了算法。方案设计与实现只用了一个二维数组存储数独方案，一个一维数组作堆栈，一个布尔变量作回溯标识。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对彖的哈希特性，为了方便调试，判定有效时函数的返回值为0,无效吋分三种情况，行冲突、列冲突、小九宫格冲突，分别返回1,2,3o前期判定用了它，后來増加了相关二十格判定，在找答案时这个函数就用不上了。functioncheckValid(sudo){letsubSudo二{}//辅助变量，用来判定小九宫格是否冲突for(leti=0;i<9;i++){letrow={},col={}//辅助变量，用来判定彳亍、列是否冲突for(letj=0;
4、j<9;j++){letcurl=sudo[i][j],cur2=sudo[j][i]//一次内循环同时完成行列的判定if(row[curl])//当前元素已经在行中出现，优化掉零的判断,key为0时值为0,不需要额外判断return1;elserow[curl]=curlif(col[cur2])//返回错误代码〃当前元素未在行中岀现，存入辅助变量中//列的判定与行类似，优化掉零的判断，key为0时值为0,不需要额外判断return2;elsecol[cur2]二cur2;letkey=Math,floor(i/3)+，+Math.
5、floor(j/3)//为不同的小九宫格生成不同的keyif(subSudo[key]){//小九宫格小已经有元素，优化掉零的判断，key为0时值为0,不需要额外判断if(subSudo[key][curl])//对某一个小九宫格的判定与行类似return3elsesubSudo[key][curl]=curl}else{//这是某小九宫格中的第一个元索subSudo[key]二{}//为小九宫格新建一个辅助变量，并将第一个元素存入其中subSudo[key][curl]=curl}return0;〃程序能运行到这，说明方案有效3•相
6、关二十格判定原理同整体判定，亮点在小九宫格的定位上。functioncheck20Grid(sudo,i,j){letrow={},col={},subSudo={}//辅助变量for(letk=0;k<9;k++){letcurl二sudo[i][k],cur2二sudo[k][j]if(curl){〃当前元素已经在行中出现，优化掉零的判断，key为0时值为0,不需要额外判断if(row[curl])return1;//返回错误代码eiserow[curl]二curl//当而元素未在行中出现,存入辅助变量屮1Jif(cur2){//
7、列的判定与行类似，优化掉零的判断，key为0时值为0,不需要额外判断if(col[cur2])return2;elsecol[cur2]二cur2;}〃转化循环变量到小九宫格的坐标letkey=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,不需要额外判断return3elsesubSudo[key]=key}return0;}4.遍历求解利用元
8、素状态初值为零的元素即为待定的特性，并加上堆栈的辅助，没有再开辟额外的存储空间。functionfindAnswcr(){for(leti=0;i<9;i++){for(letj=0;j<9;){if(problem[i
