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

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

数独技巧

我的思路

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

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