时间戳

首页 > 解决方案 > 确定数独在 JavaScript 中是否可解

javascript - 确定数独在 JavaScript 中是否可解

问题描述

这是Pramp的一个问题。我需要确定数独是否可以解决（不像 LEETcode 问题，我只需要查看板是否有效）。

下面是我在 JavaScript 中使用递归的代码。我正在遵循 Pramp 上建议的逻辑，即创建一个辅助函数 getCandidates() 来查找所有可以进入空白空间的候选数字。然后在实际的 sudokuSolve() 函数中，找到具有最小候选集的空白空间，将这些候选输入到空白空间中，然后尝试使用递归求解棋盘。如果它有效，则该板是可以解决的。

我的代码每次都产生真，我找不到问题。我研究了互联网上提出的其他类似问题，但大多数都是为了找到数独板的确切解决方案或生成数独板。我只需要看看一个板是否可以解决。如果你能告诉我我的代码哪里错了，我真的很感激。

无论测试用例如何，我现在每次都得到“真实”......对于提供的这个测试用例，答案应该是错误的。

const test02 = [
  ['.', '8', '9', '.', '4', '.', '6', '.', '5'],
  ['.', '7', '.', '.', '.', '8', '.', '4', '1'],
  ['5', '6', '.', '9', '.', '.', '.', '.', '8'],
  ['.', '.', '.', '7', '.', '5', '.', '9', '.'],
  ['.', '9', '.', '4', '.', '1', '.', '5', '.'],
  ['.', '3', '.', '9', '.', '6', '.', '1', '.'],
  ['8', '.', '.', '.', '.', '.', '.', '.', '7'],
  ['.', '2', '.', '8', '.', '.', '.', '6', '.'],
  ['.', '.', '6', '.', '7', '.', '.', '8', '.']
];

function getCandidates(board, row, col) {
  const candidates = [];

  for (let chr = 1; chr <= 9; chr++) {
    let collision = false;
    for (let i = 0; i < 9; i++) {
      if (
        board[row][i] == chr ||
        board[i][col] == chr ||
        board[row - (row % 3) + Math.floor(i / 3)][
          col - (col % 3) + Math.floor(i / 3)
        ] == chr
      ) {
        collision = true;
        break;
      }
    }

    if (!collision) {
      candidates.push(chr);
    }
  }
  return candidates;
}

function sudokuSolve(board) {
  let row = -1;
  let col = -1;
  let candidates = [];

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] === '.') {
        newCandidates = getCandidates(board, r, c);
        if (
          candidates.length === 0 ||
          newCandidates.length < candidates.length
        ) {
          candidates = newCandidates;
          row = r;
          col = c;
        }
      }
    }
  }
  if (candidates.length === 0) {
    return true;
  } else {
    let solvable = false;
    candidates.forEach(val => {
      board[row][col] = val;
      if (sudokuSolve(board)) {
        solvable = true;
      } else {
        board[row][col] = '.';
      }
    });
    return solvable;
  }
}
console.log(
  sudokuSolve(test02)
);

标签： javascriptsudoku

解决方案

问题出在您的行：

if (candidates.length === 0) {
    return true;

您没有区分候选人为空的两种情况 - 它可能是：

a) 谜题已经完全解决，没有未知的“。” 剩余的方块（在这种情况下，是的，返回真）

b) 谜题已经无法解决，剩下的“。” 方块没有任何有效值

由于您对这两个都返回“true”，因此似乎一切都已解决。

尝试添加一个布尔值来检测是否有“。” 正方形仍然存在，并在您的“if”条件下使用它：

let allSquaresFilled = true;
for (let r = 0; r < 9; r++) {
  for (let c = 0; c < 9; c++) {
    if (board[r][c] === '.') {
        allSquaresFilled = false;


if (allSquaresFilled) {
    return true;

推荐阅读