确定Sudoku在JavaScript中是否可解决

Question

这是Pramp的问题。我需要确定数独功能是否可解决（与LEETcode问题不同，我只需要查看电路板是否有效）。

下面是我使用递归的JavaScript代码。我遵循Pramp上建议的逻辑，即创建一个辅助函数getCandidates（）来查找可以进入空白空间的所有候选编号。然后，在实际的sudokuSolve（）函数中，找到候选集最小的空白空间，将这些候选内容输入空白空间，然后尝试使用递归求解电路板。如果可行，则该板是可解决的。

我的代码每次都是正确的，我找不到问题。我已经研究了互联网上提出的其他类似问题，但大多数问题都是为数独板找到确切的解决方案或生成数独板。我只需要查看一块木板是否可解决。如果可以的话，请告诉我我的代码哪里有错，我将非常感谢。

无论测试案例是什么，我现在每次都得到“ true” ...对于提供的这个测试案例，答案应该为false。

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)
);  

Answer 1

问题出在你的行上：

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

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

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

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;