利用JavaScript做数独的完整实现过程
作者:写文章的自然醒 发布时间:2024-02-24 02:10:47
前言
最近看到老婆天天在手机上玩数独,突然想起 N 年前刷 LeetCode 的时候,有个类似的算法题(37.解数独),是不是可以把这个算法进行可视化。
说干就干,经过一个小时的实践,最终效果如下:
怎么解数独
解数独之前,我们先了解一下数独的规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的九宫格( 3x3 )内只能出现一次。
接下来,我们要做的就是在每个格子里面填一个数字,然后判断这个数字是否违反规定。
填第一个格子
首先,在第一个格子填 1,发现在第一列里面已经存在一个 1,此时就需要擦掉前面填的数字 1,然后在格子里填上 2,发现数字在行、列、九宫格内均无重复。那么这个格子就填成功了。
填第二个格子
下面看第二个格子,和前面一样,先试试填 1,发现在行、列、九宫格内的数字均无重复,那这个格子也填成功了。
填第三个格子
下面看看第三个格子,由于前面两个格子,我们已经填过数字 1、2,所以,我们直接从数字 3 开始填。填 3 后,发现在第一行里面已经存在一个 3,然后在格子里填上 4,发现数字 4 在行和九宫格内均出现重复,依旧不成功,然后尝试填上数字 5,终于没有了重复数字,表示填充成功。
……
一直填……
填第九个格子
照这个思路,一直填到第九个格子,这个时候,会发现,最后一个数字 9 在九宫格内冲突了。而 9 已经是最后一个数字了,这里没办法填其他数字了,只能返回上一个格子,把第七个格子的数字从 8 换到 9,发现在九宫格内依然冲突。
此时需要替换上上个格子的数字(第六个格子)。直到没有冲突为止,所以在这个过程中,不仅要往后填数字,还要回过头看看前面的数字有没有问题,不停地尝试。
综上所述
解数独就是一个不断尝试的过程,每个格子把数字 1-9 都尝试一遍,如果出现冲突就擦掉这个数字,直到所有的格子都填完。
通过代码来实现
把上面的解法反映到代码上,就需要通过 递归 + 回溯 的思路来实现。
在写代码之前,先看看怎么把数独表示出来,这里参考 leetcode 上的题目:37. 解数独。
前面的这个题目,可以使用一个二维数组来表示。最外层数组内一共有 9 个数组,表示数独的 9 行,内部的每个数组内 9 字符分别对应数组的列,未填充的空格通过字符('.' )来表示。
const sudoku = [
['.', '.', '.', '4', '.', '.', '.', '3', '.'],
['7', '.', '4', '8', '.', '.', '1', '.', '2'],
['.', '.', '.', '2', '3', '.', '4', '.', '9'],
['.', '4', '.', '5', '.', '9', '.', '8', '.'],
['5', '.', '.', '.', '.', '.', '9', '1', '3'],
['1', '.', '.', '.', '8', '.', '2', '.', '4'],
['.', '.', '.', '.', '.', '.', '3', '4', '5'],
['.', '5', '1', '9', '4', '.', '7', '2', '.'],
['4', '7', '3', '.', '5', '.', '.', '9', '1'],
]
知道如何表示数组后,我们再来写代码。
const sudoku = [……]
// 方法接受行、列两个参数,用于定位数独的格子
function solve(row, col) {
if (col >= 9) {
// 超过第九列,表示这一行已经结束了,需要另起一行
col = 0
row += 1
if (row >= 9) {
// 另起一行后,超过第九行,则整个数独已经做完
return true
}
}
if (sudoku[row][col] !== '.') {
// 如果该格子已经填过了,填后面的格子
return solve(row, col + 1)
}
// 尝试在该格子中填入数字 1-9
for (let num = 1; num <= 9; num++) {
if (!isValid(row, col, num)) {
// 如果是无效数字,跳过该数字
continue
}
// 填入数字
sudoku[row][col] = num.toString()
// 继续填后面的格子
if (solve(row, col + 1)) {
// 如果一直到最后都没问题,则这个格子的数字没问题
return true
}
// 如果出现了问题,solve 返回了 false
// 说明这个地方要重填
sudoku[row][col] = '.' // 擦除数字
}
// 数字 1-9 都填失败了,说明前面的数字有问题
// 返回 FALSE,进行回溯,前面数字要进行重填
return false
}
上面的代码只是实现了递归、回溯的部分,还有一个 isValid 方法没有实现。该方法主要就是按照数独的规则进行一次校验。
const sudoku = [……]
function isValid(row, col, num) {
// 判断行里是否重复
for (let i = 0; i < 9; i++) {
if (sudoku[row][i] === num) {
return false
}
}
// 判断列里是否重复
for (let i = 0; i < 9; i++) {
if (sudoku[i][col] === num) {
return false
}
}
// 判断九宫格里是否重复
const startRow = parseInt(row / 3) * 3
const startCol = parseInt(col / 3) * 3
for (let i = startRow; i < startRow + 3; i++) {
for (let j = startCol; j < startCol + 3; j++) {
if (sudoku[i][j] === num) {
return false
}
}
}
return true
}
通过上面的代码,我们就能解出一个数独了。
const sudoku = [
['.', '.', '.', '4', '.', '.', '.', '3', '.'],
['7', '.', '4', '8', '.', '.', '1', '.', '2'],
['.', '.', '.', '2', '3', '.', '4', '.', '9'],
['.', '4', '.', '5', '.', '9', '.', '8', '.'],
['5', '.', '.', '.', '.', '.', '9', '1', '3'],
['1', '.', '.', '.', '8', '.', '2', '.', '4'],
['.', '.', '.', '.', '.', '.', '3', '4', '5'],
['.', '5', '1', '9', '4', '.', '7', '2', '.'],
['4', '7', '3', '.', '5', '.', '.', '9', '1']
]
function isValid(row, col, num) {……}
function solve(row, col) {……}
solve(0, 0) // 从第一个格子开始解
console.log(sudoku) // 输出结果
动态展示做题过程
有了上面的理论知识,我们就可以把这个做题的过程套到 react 中,动态的展示做题的过程,也就是文章最开始的 Gif 中的那个样子。
这里直接使用 create-react-app 脚手架快速启动一个项目
npx create-react-app sudoku
cd sudoku
打开 App.jsx ,开始写代码。
import React from 'react';
import './App.css';
class App extends React.Component {
state = {
// 在 state 中配置一个数独二维数组
sudoku: [
['.', '.', '.', '4', '.', '.', '.', '3', '.'],
['7', '.', '4', '8', '.', '.', '1', '.', '2'],
['.', '.', '.', '2', '3', '.', '4', '.', '9'],
['.', '4', '.', '5', '.', '9', '.', '8', '.'],
['5', '.', '.', '.', '.', '.', '9', '1', '3'],
['1', '.', '.', '.', '8', '.', '2', '.', '4'],
['.', '.', '.', '.', '.', '.', '3', '4', '5'],
['.', '5', '1', '9', '4', '.', '7', '2', '.'],
['4', '7', '3', '.', '5', '.', '.', '9', '1']
]
}
// TODO:解数独
solveSudoku = async () => {
const { sudoku } = this.state
}
render() {
const { sudoku } = this.state
return (
<div className="container">
<div className="wrapper">
{/* 遍历二维数组,生成九宫格 */}
{sudoku.map((list, row) => (
{/* div.row 对应数独的行 */}
<div className="row" key={`row-${row}`}>
{list.map((item, col) => (
{/* span 对应数独的每个格子 */}
<span key={`box-${col}`}>{ item !== '.' && item }</span>
))}
</div>
))}
<button onClick={this.solveSudoku}>开始做题</button>
</div>
</div>
);
}
}
九宫格样式
给每个格子加上一个虚线的边框,先让它有一点九宫格的样子。
.row {
display: flex;
direction: row;
/* 行内元素居中 */
justify-content: center;
align-content: center;
}
.row span {
/* 每个格子宽高一致 */
width: 30px;
min-height: 30px;
line-height: 30px;
text-align: center;
/* 设置虚线边框 */
border: 1px dashed #999;
}
可以得到一个这样的图形:
接下来,需要给外边框和每个九宫格加上实线的边框,具体代码如下:
/* 第 1 行顶部加上实现边框 */
.row:nth-child(1) span {
border-top: 3px solid #333;
}
/* 第 3、6、9 行底部加上实现边框 */
.row:nth-child(3n) span {
border-bottom: 3px solid #333;
}
/* 第 1 列左边加上实现边框 */
.row span:first-child {
border-left: 3px solid #333;
}
/* 第 3、6、9 列右边加上实现边框 */
.row span:nth-child(3n) {
border-right: 3px solid #333;
}
这里会发现第三、六列的右边边框和第四、七列的左边边框会有点重叠,第三、六行的底部边框和第四、七行的顶部边框也会有这个问题,所以,我们还需要将第四、七列的左边边框和第三、六行的底部边框进行隐藏。
.row:nth-child(3n + 1) span {
border-top: none;
}
.row span:nth-child(3n + 1) {
border-left: none;
}
做题逻辑
样式写好后,就可以继续完善做题的逻辑了。
class App extends React.Component {
state = {
// 在 state 中配置一个数独二维数组
sudoku: [……]
}
solveSudoku = async () => {
const { sudoku } = this.state
// 判断填入的数字是否有效,参考上面的代码,这里不再重复
const isValid = (row, col, num) => {
……
}
// 递归+回溯的方式进行解题
const solve = async (row, col) => {
if (col >= 9) {
col = 0
row += 1
if (row >= 9) return true
}
if (sudoku[row][col] !== '.') {
return solve(row, col + 1)
}
for (let num = 1; num <= 9; num++) {
if (!isValid(row, col, num)) {
continue
}
sudoku[row][col] = num.toString()
this.setState({ sudoku }) // 填了格子之后,需要同步到 state
if (solve(row, col + 1)) {
return true
}
sudoku[row][col] = '.'
this.setState({ sudoku }) // 填了格子之后,需要同步到 state
}
return false
}
// 进行解题
solve(0, 0)
}
render() {
const { sudoku } = this.state
return (……)
}
}
对比之前的逻辑,这里只是在对数独的二维数组填空后,调用了 this.setState 将 sudoku 同步到了 state 中。
function solve(row, col) {
……
sudoku[row][col] = num.toString()
+ this.setState({ sudoku })
……
sudoku[row][col] = '.'
+ this.setState({ sudoku }) // 填了格子之后,需要同步到 state
}
在调用 solveSudoku 后,发现并没有出现动态的效果,而是直接一步到位的将结果同步到了视图中。
这是因为 setState 是一个伪异步调用,在一个事件任务中,所以的 setState 都会被合并成一次,需要看到动态的做题过程,我们需要将每一次 setState 操作放到该事件流之外,也就是放到 setTimeout 中。更多关于 setState 异步的问题,可以参考我之前的文章:React 中 setState 是一个宏任务还是微任务?
solveSudoku = async () => {
const { sudoku } = this.state
// 判断填入的数字是否有效,参考上面的代码,这里不再重复
const isValid = (row, col, num) => {
……
}
// 脱离事件流,调用 setState
const setSudoku = async (row, col, value) => {
sudoku[row][col] = value
return new Promise(resolve => {
setTimeout(() => {
this.setState({
sudoku
}, () => resolve())
})
})
}
// 递归+回溯的方式进行解题
const solve = async (row, col) => {
……
for (let num = 1; num <= 9; num++) {
if (!isValid(row, col, num)) {
continue
}
await setSudoku(row, col, num.toString())
if (await solve(row, col + 1)) {
return true
}
await setSudoku(row, col, '.')
}
return false
}
// 进行解题
solve(0, 0)
}
最后效果如下:
来源:https://mp.weixin.qq.com/s/nbEb2RgTymCQiTTrq0PHfQ


猜你喜欢
- 1.获取所有数据库名: SELECT Name FROM Master..SysDatabases ORDER BY Name2.获取所有表
- 本文实例讲述了Python文件及目录操作的方法。分享给大家供大家参考。具体分析如下:在python中对文件及目录的操作一般涉及多os模块,o
- Varchar 对每个英文(ASCII)字符都占用2个字节,对一个汉字也只占用两个字节char 对英文(ASCII)字符占用1个字节,对一个
- Go语言内置int转string至少有3种方式:fmt.Sprintf("%d",n)strconv.Itoa(n)st
- 前言上一篇文章写了关于字典操作方法的增删改,这篇主要讲解如何查找字典数据。查找数据写法一共有两种,一种能够是key值查找,另外一种是按照函数
- Golang 复制文件夹,包括文件夹中的文件/** * 拷贝文件夹,同时拷贝文件夹中的文件 * @param srcPath 需要拷贝的文件
- 在python用import或者from...import来导入相应的模块。模块其实就是一些函数和类的集合文件,它能实现一些相应的功能,当我
- 众所周知,vue可以用来开发移动端app,可以使用hbuilder将build好的vue打包成一个移动端app,但是用过之后就会发现,使用c
- 本文实例讲述了PHP中PDO事务处理操作。分享给大家供大家参考,具体如下:概要:将多条sql操作(增删改)作为一个操作单元,要么都成功,要么
- 今天给大家分享一下最新版阿里大于的短信验证码在node koa2的实现,还是有很多坑需要注意。首先需要在阿里云注册账号,并获取阿里云访问秘钥
- rebase在git中是一个非常有魅力的命令,使用得当会极大提高自己的工作效率;相反,如果乱用,会给团队中其他人带来麻烦。它的作用简要概括为
- 如下所示:temp1 = [[] for i in range(10)]temp2 = [temp1 for i in range(20)]
- 本文实例讲述了python飞机大战pygame碰撞检测实现方法。分享给大家供大家参考,具体如下:目标了解碰撞检测方法碰撞实现01. 了解碰撞
- 一、内置函数下面简单介绍几个:1.abs() 求绝对值2.all() 如果 iterable 的所有元素都为真(或者如果可迭代为空),则返回
- 欣赏上一篇:用画为5.12地震受灾同胞们祈福 今年我们的祖国多灾多难 雪灾的阴影还没散去又发生了地震。中国插画 * 举办5.12地震祈幅绘画活
- 这里假设你已经申请完微信支付1. 微信后台配置 如图我们先进行测试,所以先把测试授权目录和 测试白名单添加上。测试授权目录是你要
- 1. 简述我们在用scrapy爬取数据时,首先就要明确我们要爬取什么数据。scrapy提供了Item对象这种简单的容器,我们可以通过Item
- 1.实现效果2.实现代码# 导入所需库from tkinter import *import randomclass main:  
- 1 关联查询的执行关联查询的执行过程是:先遍历关联表t1(驱动表,全表扫描),然后根据从表t1中取出的每行数据中的a值,去表t2(被关联表,
- Python continue语句:当执行到 continue 语句时,将不再执行本次循环中 continue 语句接下来的部分,而是继续下