使用递归回溯算法实现的前端解数独游戏

我心飞翔 分类:javascript

前言

最近一个多月来,我一直全身心投入于数据结构和算法的学习,一边学习各种典型的算法类型,一边疯狂刷题,从一个对算法一无所知的小白,到现在leetcode破百的解题数,还是很有成就感的。逻辑思维能力也是明显的有所提高,很多算法当中的思想其实也是可以应用到实际的开发当中的。

因为算法学习总体来说,还是比较枯燥的,就是不断的刷题,前几天,在刷递归回溯算法相关题型的时候,做到了一道解数独的题目,感觉很有意思,花了一点时间做了一个纯前端实现的解数独游戏,在这里分享一下递归回溯法用来解数独的具体实现。

介绍

解数独游戏地址,大家可以点进去试玩一下,就是一个html文件,样式上做的比较简陋,没做兼容性,一般低版本的浏览器可能打开会有问题。想看源码的就直接右键查看源码。

微信截图_20210414232459.png

功能很简单,生成一套数独题目,可以手动填入1-9的数据,需要使每一行,每一列,每一个3X3的框中都存在1-9这9个数字。然后可以提交验证看是否答对。

PS:生成一套只有唯一解的数独这块的算法有点难搞,我尝试了很多思路都失败了,所以这里的数独题目目前都是我直接从题库中随机获取的。

解数独

按上图所示的数据,解数独可以抽象成

const board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]

给你一个二维数组,假设给定的数独只有唯一解,你需要编写一个程序,填充空格这些空格,并且需要满足以下三个条件。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

每一个空白格都要选一个数字去填,有多少个空白格,做多少次选择。我们可以想到递归,每次递归填当前的格子。不过我们需要思考一下两个点

1.每次递归的约束条件要怎么去处理?

2.这是个二维数组,怎么使用一个递归方法去处理每一层的数组?

每次递归的约束条件要怎么去处理?

数独的约束条件要求我们每一行,每一列,每一个3X3的宫内,1-9都只能使用一次。

如果按照暴力解法来考虑,每次填入一个值的时候,循环遍历当前节点的行,列,宫,如果不存在重复的值,才能填入值,然后继续递归。

不过我们可以做一些优化,因为每次都循环行列和宫,花费的性能比较大,我们可以定义三个变量用来记录每一行,每一列,每一个宫中使用过的数字,从循环变成查找表的形式,提高性能。

这是个二维数组,怎么使用一个递归方法去处理每一层的数组?

很多递归回溯的题其实只是对于一个一维数组或者字符串的递归,但是这里是二维数组。所以我们需要变通,递归时候定义x,y两个值代表当前节点的x轴和y轴。先从第一行第一位开始递归,x轴不变,每次递归只让y轴加1,当y轴等于9时,说明当前序号为x的数组已经递归完成。我们把x加1,y归0。继续递归下一行的数组。

具体实现

var solveSudoku = function(board) {
// 定义三个数组来记录,每一行,每一行,每一个3X3里已经被使用过的参数
let lineX = [];
let lineY = [];
let area3x3 = [];
for (let n = 0; n < 9; n ++) {
lineX[n] = {};
lineY[n] = {};
if (((n + 1) % 3) === 0) {
const curIndex = (n + 1) / 3;
area3x3[curIndex - 1] = [{}, {}, {}];
} 
}
// 用来增加(删除)记录,如果已经被使用过,将当前位置置为true
const toggleCache = (i, j, val, type) => {
const flag = (type === 'add' ? true : false);
lineX[i][val] = flag;
lineY[j][val] = flag;
area3x3[Math.floor(i / 3)][Math.floor(j / 3)][val] = flag;
};
// 判断当前数据是否在当前行,列,3x3中存在
const hasCache = (i, j, val) => {
if(lineX[i][val]) return true;
if(lineY[j][val]) return true;
if(area3x3[Math.floor(i / 3)][Math.floor(j / 3)][val]) return true;
return false;
};
// 初始化,将初始数据传入记录中
for (let i = 0; i < 9; i ++) {
for (let j = 0; j < 9; j ++) {
const val = board[i][j];
if (val !== '.') toggleCache(i, j, val, 'add');
}
}
// 递归方法
const dfs = (xIndex, yIndex) => {
// 当x轴递归到9时,结束递归。
// 因为本题都只有唯一解,所以需要return一个true,用来计算出值之后,提前退出
if (xIndex === 9) return true;
// 当y轴递归到9时,将x加1,继续下一行的递归
if (yIndex === 9) return dfs(xIndex + 1, 0);
if (board[xIndex][yIndex] === '.') {
// 如果当前没有值,遍历1-9
for (let v = 1; v <= 9; v ++) {
// 判断遍历的v是否满足同一行,同一列,3x3都没有被使用过
if (!hasCache(xIndex, yIndex, String(v))) {
// 递归
board[xIndex][yIndex] = String(v);
toggleCache(xIndex, yIndex, v, 'add');
// 如果得到的返回值是true,说明已经得到值了,不需要再计算后面的值了,直接退出
if (dfs(xIndex, yIndex + 1)) return true;
// 回溯
board[xIndex][yIndex] = '.';
toggleCache(xIndex, yIndex, v, 'remove');
}
}
} else {
// 如果当有初始值,跳到下一个节点
return dfs(xIndex, yIndex + 1);
}
};
dfs(0, 0);
return board;
};

总结

没啥说的,就是介绍了递归回溯算法在解数独上的具体实现。

感谢

感谢您的阅读,如果本文对你有帮助,就点个赞支持下吧。

回复

我来回复
  • 暂无回复内容