Javascript 的数独解算器

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 依次猜测的），则无法取得任何进展。

要回溯，您需要将无法扩展到已解决状态的单元格置零，并且当单元格的所有可能性都用尽时，return 将 false 设置为父状态。

此外，函数最好采用参数和 return 值，而不是改变全局状态。

应用这些最少的修改会产生以下结果。还有改进的余地；例如，solve 函数必须 "hunt" 重复下一个空方块。

function possible(board, y, x, n) {
  for (let i = 0; i < 9; i++) {
    if (board[y][i] === n || board[i][x] === n) {
      return false;
    }
  }

  const xSquare = Math.floor(x / 3) * 3;
  const ySquare = Math.floor(y / 3) * 3;

  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[ySquare+i][xSquare+j] === n) {
        return false;
      }
    }
  }

  return true;
}

function solve(board) {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (board[y][x] === 0) {
        for (let n = 1; n <= 9; n++) {
          if (possible(board, y, x, n)) {
            board[y][x] = n;
            
            if (solve(board)) return board;
          }
        }
        
        board[y][x] = 0;
        return false;
      }
    }
  }
  
  return board;
}

const puzzle = [
  [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(solve(puzzle).map(e => "" + e));

Javascript 的数独解算器

Sudoku solver with Javascript

javascript

recursion

sudoku

backtracking