带有爪哇脚本的数独求解器

Question

我尝试用Javascript构建数独求解器。代码确实解决了它，但还有一些空白点。我使用 Javascript、回溯和递归。

在第一个函数中，我检查一个空白点（0）上的数字是可能的，在第二个函数中，我调用第一个函数来检查空点，并尝试在该点上放置一个介于1和9之间的数字

有人能看到我做错了什么吗？

const userInput = [

  [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],

];

function possible(y, x, n) {

  for (let i = 0; i <= 8; i++) {

    if (userInput[y][i] === n) {

      return false;

    }

  }

  for (let i = 0; i <= 8; i++) {

    if (userInput[i][x] === n) {

      return false;

    }

  }

  let xSquare = Math.floor(x / 3) * 3;

  let ySquare = Math.floor(y / 3) * 3;

  for (let i = 0; i <= 2; i++) {

    for (let j = 0; j <= 2; j++) {

      if (userInput[ySquare + i][xSquare + j] === n) {

        return false;

      }

    }

  }

  return true;

}

function solve() {

  for (let y = 0; y <= 8; y++) {

    for (let x = 0; x <= 8; x++) {

      if (userInput[y][x] === 0) {

        for (let n = 1; n <= 9; n++) {

          if (possible(y, x, n)) {

            userInput[y][x] = n;

            solve();

          }

        }

      }

    }

  }

}

Answer 1

您正在编写回溯算法，但这里没有回溯。当前的算法假设每个猜测的值都是完美的 - 如果有任何不完美（这是可以保证的，因为值是从1到9的顺序猜测的），则无法取得进展。要回溯，您需要将无法扩展为已解决状态的单元格清零，并在单元格的所有可能性耗尽时将 false 返回到父状态。此外，函数最好采用参数并返回值，而不是改变全局状态。应用这些最小的修改将产生以下结果。还有改进的余地。例如，该函数必须重复“搜索”下一个打开的正方形。solvefunction possible(board, y, x, n) {&nbsp; for (let i = 0; i < 9; i++) {&nbsp; &nbsp; if (board[y][i] === n || board[i][x] === n) {&nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }&nbsp; }&nbsp; const xSquare = Math.floor(x / 3) * 3;&nbsp; const ySquare = Math.floor(y / 3) * 3;&nbsp; for (let i = 0; i < 3; i++) {&nbsp; &nbsp; for (let j = 0; j < 3; j++) {&nbsp; &nbsp; &nbsp; if (board[ySquare+i][xSquare+j] === n) {&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; }&nbsp; return true;}function solve(board) {&nbsp; for (let y = 0; y < 9; y++) {&nbsp; &nbsp; for (let x = 0; x < 9; x++) {&nbsp; &nbsp; &nbsp; if (board[y][x] === 0) {&nbsp; &nbsp; &nbsp; &nbsp; for (let n = 1; n <= 9; n++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (possible(board, y, x, n)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; board[y][x] = n;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (solve(board)) return board;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; board[y][x] = 0;&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; }&nbsp;&nbsp;&nbsp; return board;}const puzzle = [&nbsp; [5, 3, 0, 0, 7, 0, 0, 0, 0],&nbsp; [6, 0, 0, 1, 9, 5, 0, 0, 0],&nbsp; [0, 9, 8, 0, 0, 0, 0, 6, 0],&nbsp; [8, 0, 0, 0, 6, 0, 0, 0, 3],&nbsp; [4, 0, 0, 8, 0, 3, 0, 0, 1],&nbsp; [7, 0, 0, 0, 2, 0, 0, 0, 6],&nbsp; [0, 6, 0, 0, 0, 0, 2, 8, 0],&nbsp; [0, 0, 0, 4, 1, 9, 0, 0, 5],&nbsp; [0, 0, 0, 0, 8, 0, 0, 7, 9],];console.log(solve(puzzle).map(e => "" + e));