本文介绍使用JavaScript通过遍历和回溯法求解9x9数独问题的思路。核心在于利用二维数组存储方案，结合一维数组模拟堆栈记录回溯路径。通过设计有效性判定函数和相关二十格判定，利用对象哈希特性优化冲突检测，最终实现无需额外空间开辟的高效求解逻辑。
数独规则与技巧概述
数独游戏规则要求在一个由81个单元格组成的9×9九宫格中填入数字1至9。该网格进一步划分为9个3×3的小九宫格。核心规则是确保每一行、每一列以及每一个小九宫格内的数字均不重复。
常见的数独解题技巧主要包括直观法和候选数法。
- 直观法
- 候选数法
- 在数独逻辑中，一个数字的有效性仅与其所在的行、列及小九宫格内的其余二十个格子相关。
求解思路设计
本文提出的求解思路主要包含以下四个关键点：
- 首先，精心设计了整体有效性判定函数。该函数最多只需遍历一次全部81个单元格，即可判断当前方案是否合法。
- 同理设计了相关20格判定，一次0~9的循环就完成有效性判定。
- 第三，使用数组模拟堆栈结构，用于在搜索过程中保存回溯所需的状态信息。
- 最后，利用JavaScript对象具备的Map（键值对）性质来辅助判断方案有效性，这一设计大大简化了算法逻辑。
方案设计与实现
在方案设计与实现层面，程序仅使用了一个二维数组来存储数独方案，一个一维数组作为堆栈，以及一个布尔变量作为回溯标识。
具体实现步骤如下：
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;
第一步是变量定义。第二步是方案有效性判定。该判定充分利用了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; //程序能运行到这，说明方案有效
}
第三步是相关二十格判定。其原理与整体判定类似，但亮点在于对小九宫格位置的精准定位。
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; //返回错误代码
else
row[cur1] = cur1 //当前元素未在行中出现，存入辅助变量中
}
if(cur2){ //列的判定与行类似，优化掉零的判断，key为0时值为0，不需要额外判断
if(col[cur2])
return 2;
else
col[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 3
else
subSudo[key] = key
}
return 0;
}
第四步是遍历求解。算法利用元素状态初值为零即代表待定的特性，并结合堆栈辅助，实现了在不开辟额外存储空间的情况下完成求解。
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) //无解判断，返回0
return 0;
i=rt[0] //穿越
j=rt[1]
flag = true;
}
}else{ //当前位置数字为题目给定
j++;
}
}
}
return 1; //成功找到一组解
}