JS实现判断有效的数独算法示例

判断有效的数独是一道常见的编程面试题，本文将介绍如何使用JavaScript实现一个有效的数独判断算法。

如何表示数独？

数独可表示为一个9x9的二维数组，其中空白单元格表示为0，已填充数字的单元格则为1至9之间的数字。

示例：

const board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

算法流程

对于数独的有效性判断算法可以按照以下流程进行实现：

1. 验证每一行是否符合规则，即是否包含1到9的数字，而且不能有重复数字。
2. 验证每一列是否符合规则，即是否包含1到9的数字，而且不能有重复数字。
3. 验证每一宫是否符合规则，即是否包含1到9的数字，而且不能有重复数字。

代码实现

下面是使用JavaScript实现的代码：

function isValidSudoku(board) {
  const rows = [];
  const cols = [];
  const boxes = [];

  // 初始化rows、cols和boxes数组
  for (let i = 0; i < 9; i++) {
    rows[i] = new Set();
    cols[i] = new Set();
    boxes[i] = new Set();
  }

  // 遍历数独中的每一个元素
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const num = board[i][j];

      // 如果当前格是空白，直接跳过当前轮次
      if (num === 0) continue;

      // 计算该值所属的宫
      const boxIdx = Math.floor(i / 3) * 3 + Math.floor(j / 3);

      // 检测该值是否在当前的行、列或宫中已存在
      if (rows[i].has(num) || cols[j].has(num) || boxes[boxIdx].has(num)) {
        return false;
      } else {
        rows[i].add(num);
        cols[j].add(num);
        boxes[boxIdx].add(num);
      }
    }
  }

  return true;
}

示例一

假设我们有以下数独：

const board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

我们可以使用以下代码来判断该数独是否有效：

console.log(isValidSudoku(board)); // true

示例二

假设我们有以下数独：

const board = [
  [8, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 0, 0, 0, 7, 9]
];

我们可以使用以下代码来判断该数独是否有效：

console.log(isValidSudoku(board)); // false

在以上两个示例中，第一个数独是有效的，而第二个数独则无效，因为第一行和第一列都存在重复数字。

总结

以上是使用JavaScript实现判断有效的数独算法示例的完整攻略，通过将数独表示为二维数组，并使用一个Set数据结构来存储每行、每列和每宫中已存在的数字，最终得以实现有效的数独判断。