JavaScript
发布时间:2022-04-16 发布网站:大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了JavaScript遍历求解数独问题的主要思路小结,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
数独规则
数独游戏,经典的为9×9=8
1个单元格组成的九宫格,
同时也形成了3×3=9个小九宫格,要求在8
1个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复。
数独技巧
- 直观法
- 候选数法
- 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关
我的思路
- 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定。
- 同理设计了相关20格判定,一次0~9的循环就完成有效性判定。
- 用数组模拟堆栈,为搜索提供回溯信息。
- 利用对象具有map性质,来辅助判断方案的有效性,大大简化了算法。
方案设计与实现
只用了一个二维数组存储数独方案,一个一维数组作堆栈,一个布尔变量作回溯标识。
1.变量定义:
false;
2.方案有效性判定:
充分利用了javascript对象的哈希特性,为了方
便调试,判定有效时函数的返回值为0,无效时分三种情况,行冲突、列冲突、小九宫格冲突,分别返回1,2,3。前期判定用了它,后来增加了相关二十格判定,在找答案时这个函数就用不上了。
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[ke
y]){ //小九宫格中已经有元素,优化掉零的判断,key为0时值为0,不需要额外判断
if(subSudo[key][cur1]) //对某一个小九宫格的判定与行类似
return 3
else
subSudo[key][cur1] = cur1
}else
{ //这是某小九宫格中的第一个元素
subSudo[key] =
{} //为小九宫格新建一个辅助变量,并将第一个元素存入其中
subSudo[key][cur1] = cur1
}
}
}
return 0; //程序能运行到这,说明方案有效
}
3.相关二十格判定
原理同整体判定,亮点在小九宫格的定位上。
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[ke
y]) //九宫格判定与行类似,优化掉零的判断,key为0时值为0,不需要额外判断
return 3
else
subSudo[key] = key
}
return 0;
}
4.遍历求解
利用元素状态初值为零的元素即为待定的特性,并加上堆栈的辅助,没有再开辟额外的存储空间。
{
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,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; //成功找到一组解
}
大佬总结
以上是大佬教程为你收集整理的JavaScript遍历求解数独问题的主要思路小结全部内容,希望文章能够帮你解决JavaScript遍历求解数独问题的主要思路小结所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。