JavaScript遍历求解数独问题的主要思路小结
数独规则
数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复。
数独技巧
- 直观法
- 候选数法
- 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关
我的思路
- 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定。
- 同理设计了相关20格判定,一次0~9的循环就完成有效性判定。
- 用数组模拟堆栈,为搜索提供回溯信息。
- 利用对象具有map性质,来辅助判断方案的有效性,大大简化了算法。
方案设计与实现
只用了一个二维数组存储数独方案,一个一维数组作堆栈,一个布尔变量作回溯标识。
1.变量定义:
varproblem=[//这是书上提到的难度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] ] varstack=[],flag=false;
2.方案有效性判定:
充分利用了javascript对象的哈希特性,为了方便调试,判定有效时函数的返回值为0,无效时分三种情况,行冲突、列冲突、小九宫格冲突,分别返回1,2,3。前期判定用了它,后来增加了相关二十格判定,在找答案时这个函数就用不上了。
functioncheckValid(sudo){ letsubSudo={}//辅助变量,用来判定小九宫格是否冲突 for(leti=0;i<9;i++){ letrow={},col={}//辅助变量,用来判定行、列是否冲突 for(letj=0;j<9;j++){ letcur1=sudo[i][j],cur2=sudo[j][i]//一次内循环同时完成行列的判定 if(row[cur1])//当前元素已经在行中出现,优化掉零的判断,key为0时值为0,不需要额外判断 return1;//返回错误代码 else row[cur1]=cur1//当前元素未在行中出现,存入辅助变量中 if(col[cur2])//列的判定与行类似,优化掉零的判断,key为0时值为0,不需要额外判断 return2; else col[cur2]=cur2; letkey=Math.floor(i/3)+'-'+Math.floor(j/3)//为不同的小九宫格生成不同的key if(subSudo[key]){//小九宫格中已经有元素,优化掉零的判断,key为0时值为0,不需要额外判断 if(subSudo[key][cur1])//对某一个小九宫格的判定与行类似 return3 else subSudo[key][cur1]=cur1 }else{//这是某小九宫格中的第一个元素 subSudo[key]={}//为小九宫格新建一个辅助变量,并将第一个元素存入其中 subSudo[key][cur1]=cur1 } } } return0;//程序能运行到这,说明方案有效 }3.相关二十格判定
原理同整体判定,亮点在小九宫格的定位上。
functioncheck20Grid(sudo,i,j){ letrow={},col={},subSudo={}//辅助变量 for(letk=0;k<9;k++){ letcur1=sudo[i][k],cur2=sudo[k][j] if(cur1){//当前元素已经在行中出现,优化掉零的判断,key为0时值为0,不需要额外判断 if(row[cur1]) return1;//返回错误代码 else row[cur1]=cur1//当前元素未在行中出现,存入辅助变量中 } if(cur2){//列的判定与行类似,优化掉零的判断,key为0时值为0,不需要额外判断 if(col[cur2]) return2; else col[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,不需要额外判断 return3 else subSudo[key]=key } return0; }
4.遍历求解
利用元素状态初值为零的元素即为待定的特性,并加上堆栈的辅助,没有再开辟额外的存储空间。
functionfindAnswer(){ for(leti=0;i<9;i++){ for(letj=0;j<9;){ if(problem[i][j]===0||flag){//当前位置为待定元素的首次处理或回溯到当前位置,两种情况看似不同,其实处理相同,自加1即可 flag=false; letk=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;//回溯前归零 letrt=stack.pop();//堆栈中取回溯信息 if(!rt)//无解判断,返回0 return0; i=rt[0]//穿越 j=rt[1] flag=true; } }else{//当前位置数字为题目给定 j++; } } } return1;//成功找到一组解 }