乐趣区

关于javascript:用-JavaScript-做数独

jiezi

最近看到老婆天天在手机上玩数独，忽然想起 N 年前刷 LeetCode 的时候，有个相似的算法题（37. 解数独），是不是能够把这个算法进行可视化。

说干就干，通过一个小时的实际，最终成果如下：

怎么解数独

解数独之前，咱们先理解一下数独的规定：

  1. 数字 1-9 在每一行只能呈现一次。
  2. 数字 1-9 在每一列只能呈现一次。
  3. 数字 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)}

最初成果如下：

退出移动版