JavaScript遍历求解数独问题的主要思路小结

数独规则
数独游戏，经典的为9×9=81个单元格组成的九宫格，同时也形成了3×3=9个小九宫格，要求在81个小单元格中填入数字1~9，并且数字在每行每列及每个小九宫格中都不能重复。
数独技巧

直观法
候选数法
相关二十格：一个数字只与其所在行列及小九宫格的二十格相关

我的思路

精心设计了有效性判定函数，最多一次遍历81个小单元格就能做出方案的有效性判定。
同理设计了相关20格判定，一次0~9的循环就完成有效性判定。
用数组模拟堆栈，为搜索提供回溯信息。
利用对象具有map性质，来辅助判断方案的有效性，大大简化了算法。

方案设计与实现
只用了一个二维数组存储数独方案，一个一维数组作堆栈，一个布尔变量作回溯标识。
1.变量定义：

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;

2.方案有效性判定：
充分利用了javascript对象的哈希特性，为了方便调试，判定有效时函数的返回值为0，无效时分三种情况，行冲突、列冲突、小九宫格冲突，分别返回1，2，3。前期判定用了它，后来增加了相关二十格判定，在找答案时这个函数就用不上了。

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]//一次内循环同时完成行列的判定if（row[cur1]）//当前元素已经在行中出现，优化掉零的判断，key为0时值为0，不需要额外判断return 1;//返回错误代码elserow[cur1] = cur1//当前元素未在行中出现，存入辅助变量中if（col[cur2]）//列的判定与行类似，优化掉零的判断，key为0时值为0，不需要额外判断return 2;elsecol[cur2] = cur2;let key = Math.floor（i/3）+"-"+Math.floor（j/3）//为不同的小九宫格生成不同的keyif（subSudo[key]）{ //小九宫格中已经有元素，优化掉零的判断，key为0时值为0，不需要额外判断if（subSudo[key][cur1]）//对某一个小九宫格的判定与行类似return 3elsesubSudo[key][cur1] = cur1}else{//这是某小九宫格中的第一个元素subSudo[key] = {} //为小九宫格新建一个辅助变量，并将第一个元素存入其中subSudo[key][cur1] = cur1} }}return 0;//程序能运行到这，说明方案有效}

3.相关二十格判定
原理同整体判定，亮点在小九宫格的定位上。

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）{//当前元素已经在行中出现，优化掉零的判断，key为0时值为0，不需要额外判断if（row[cur1]）return 1;//返回错误代码elserow[cur1] = cur1//当前元素未在行中出现，存入辅助变量中}if（cur2）{//列的判定与行类似，优化掉零的判断，key为0时值为0，不需要额外判断if（col[cur2]）return 2;elsecol[cur2] = cur2;}//转化循环变量到小九宫格的坐标let key = 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，不需要额外判断return 3elsesubSudo[key] = key}return 0;}

4.遍历求解
利用元素状态初值为零的元素即为待定的特性，并加上堆栈的辅助，没有再开辟额外的存储空间。

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）{ //循环找到下一个合法值problem[i][j] = k;//填值if（check20Grid（problem,i,j） == 0）{//判定合法，相关二十格判定stack.push（[i,j++]）//存储回溯点，并步进break;}k++;}if（k>9）{ //当前位置找不到合法值，回溯problem[i][j] = 0;//回溯前归零let rt = stack.pop（）; //堆栈中取回溯信息if（！rt）//无解判断，返回0return 0;i=rt[0]//穿越j=rt[1]flag = true;}}else{//当前位置数字为题目给定j++;}}}return 1;//成功找到一组解}