JS 数独算法详解：递归回溯与 React 动态展示实现

前言

近期观察到身边人常通过手机应用进行数独游戏，这引发了一个想法：多年前在 LeetCode 上遇到的类似算法题（第 37 题：解数独）是否可以进行可视化呈现？

经过约一小时的开发实践，最终实现了如下效果：

数独解题原理

在开始解题前，需明确数独的基本规则：

数字 1 至 9 在每一行中只能出现一次。
数字 1 至 9 在每一列中只能出现一次。
数字 1 至 9 在每一个由粗实线分隔的 3x3 九宫格内只能出现一次。

解题的核心任务即是在每个空格中填入数字，并实时校验该数字是否违反上述规则。

首个格子填充逻辑

以第一个格子为例，若尝试填入数字 1，发现该列已存在 1，则需撤销该操作并尝试填入 2。若 2 在行、列及九宫格内均无重复，则填充成功。

第二个格子填充逻辑

对于第二个格子，若尝试填入 1 后发现行、列及九宫格内均无重复，则该格子填充成功。

第三个格子填充逻辑

鉴于前两个格子已填入 1 和 2，第三个格子可从数字 3 开始尝试。若填入 3 发现第一行已有 3，则尝试 4；若 4 在行或九宫格内重复，则继续尝试 5。直到找到无冲突的数字，填充才算成功。

……

持续填充过程

第九个格子填充逻辑

依此逻辑推进至第九个格子时，若发现最后一个数字 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;
}

最终可得到如下图形效果：

接下来，需为外边框及每个 3x3 九宫格添加实线边框，具体实现代码如下：


/* 第 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 状态同步至 React 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)
}

最终实现效果如下：

总结

至此，关于利用 JavaScript 实现数独求解及动态展示的文章介绍完毕。如需了解更多相关 JavaScript 数独内容，请搜索本站往期文章或继续阅读后续文章，感谢支持！

JavaScript 实现数独求解与 React 动态可视化教程

前言