Sudoku解算器：完成某些单元格的问题

Question

我的数独解算器有问题，它涉及算法的回溯机制。目前，我可以将数独板部分填满，但是我遇到了一个问题，即某个单元格中的所有猜测都是错误的，因此空格留空并继续到下一个单元格。

这里是起始板：

let sudoku = [[6, 0, 5, 7, 0, 0, 1, 3, 2],
              [7, 0, 0, 6, 0, 0, 5, 0, 8],
              [0, 1, 9, 3, 0, 0, 0, 0, 4],
              [0, 2, 0, 0, 0, 3, 0, 0, 0],
              [0, 7, 3, 9, 0, 0, 2, 5, 0],
              [0, 5, 1, 2, 0, 0, 0, 0, 9],
              [5, 0, 8, 0, 0, 0, 0, 2, 0],
              [0, 4, 0, 0, 7, 6, 9, 1, 5],
              [0, 9, 0, 0, 4, 0, 6, 8, 0]];

这里是结果

[[6, 8, 5, 7, 9, 4, 1, 3, 2],
 [7, 3, 2, 6, 1, 0, 5, 9, 8],
 [0, 1, 9, 3, 2, 5, 7, 6, 4],
 [4, 2, 6, 1, 5, 3, 8, 7, 0],
 [8, 7, 3, 9, 6, 0, 2, 5, 1],
 [0, 5, 1, 2, 8, 7, 3, 4, 9],
 [5, 6, 8, 0, 3, 1, 4, 2, 7],
 [2, 4, 0, 8, 7, 6, 9, 1, 5],
 [1, 9, 7, 5, 4, 2, 6, 8, 3]]

0是空格。如您所见，此结果不是解决的数独难题。

这是我当前的算法：

let sudoku = [[6, 0, 5, 7, 0, 0, 1, 3, 2],
              [7, 0, 0, 6, 0, 0, 5, 0, 8],
              [0, 1, 9, 3, 0, 0, 0, 0, 4],
              [0, 2, 0, 0, 0, 3, 0, 0, 0],
              [0, 7, 3, 9, 0, 0, 2, 5, 0],
              [0, 5, 1, 2, 0, 0, 0, 0, 9],
              [5, 0, 8, 0, 0, 0, 0, 2, 0],
              [0, 4, 0, 0, 7, 6, 9, 1, 5],
              [0, 9, 0, 0, 4, 0, 6, 8, 0]];

function possibleCandidate(x, y, n) {
  for(let i = 0; i < sudoku[y].length; i++) {
    if(sudoku[y][i] == n) {
      return false;
    }
  }

  for(let i = 0; i < sudoku.length; i++) {
    if(sudoku[i][x] == n) {
      return false;
    }
  }

    // For 3x3 squares
    let baseX = Math.floor(x / 3) * 3;
    let baseY = Math.floor(y / 3) * 3;

    for(let a = 0; a < 3; a++) {
      for(let b = 0; b < 3; b++) {
        // add incremented values until reaching 3 to check if the value we are checking for is in the square
        if(sudoku[baseY + a][baseX + b] == n) {
          return false;
        }
      }
    }

    return true;
}

function solve() {
  let prev = [];
  let tried;
  for(let i = 0; i < sudoku.length; i++) {
    for(let j = 0; j < sudoku[i].length; j++) {
      if(sudoku[i][j] == 0) {
        for(let l = 0; l < 10; l++) {

          if(possibleCandidate(j, i, l) && l !== tried) {
            if(j == 4 && i == 0) {
              console.log(l);
            }
            prev = [i, j];
            tried = l;
            sudoku[i][j] = l;
            break;
          }
        }
        // return;
      }
    }
  }
  return true;
}

possibleCandidate(1, 0, 6);
solve();
console.log(sudoku);

编辑：

possibleCandidate()函数正常工作，我认为问题专门来自solve()函数。

Answer 1

问题是您的算法是“贪婪的”：您假设如果值是可能，则它必须是正确。这是不正确的。

对于示例数独，到达第1行第2列时出错。算法确定可以将2放置在此处。但是它忽略了也可以在其中放置4个字符。这是哪两个呢？好吧，不能将4放置在该3x3框中的另一个自由正方形中（在第3行第1行中），因此4只能放置在第1行第2列中，从而排除了应该在其中放置2的选择。

因此，您的算法过于乐观。它还应考虑其他替代方案。有很多求解器。即使在堆栈溢出时，您也应该能够找到一些。它们基于递归和回溯。