数独求解器出现Maximum call stack size exceeded错误求助

你的数独求解器出现栈溢出错误，核心问题在于递归逻辑的三个缺陷：

• 未跳过已填充的非0位置，强行修改已有数字导致逻辑混乱，递归层数失控
• 缺少递归终止条件，无法判断棋盘是否已解，递归无限进行
• 回溯逻辑错误，不管递归是否成功都重置当前位置，无法保留正确解，也无法终止递归

修正后的代码 #

let board = [
  [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],
];

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

  const x0 = Math.floor(x / 3);
  const y0 = Math.floor(y / 3);

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

  return true;
};

const solve = function (board) {
  // 遍历所有位置，寻找空位（值为0）
  for (let x = 0; x < 9; x++) {
    for (let y = 0; y < 9; y++) {
      if (board[x][y] === 0) {
        // 尝试1-9的数字
        for (let n = 1; n < 10; n++) {
          if (possible(x, y, n, board)) {
            board[x][y] = n;
            // 递归求解，若返回true说明找到完整解，直接向上返回
            if (solve(board)) {
              return true;
            }
            // 递归失败，重置当前位置为0，继续尝试下一个数字
            board[x][y] = 0;
          }
        }
        // 所有数字都尝试失败，返回false触发回溯
        return false;
      }
    }
  }
  // 遍历完所有位置，没有空位，说明棋盘已解
  return true;
};

solve(board);
// 打印查看求解结果
console.log(board);

关键修改说明 #

1. 只处理空位：添加if (board[x][y] === 0)判断，跳过已有数字的位置，避免无效操作
2. 递归终止与返回值：当遍历完所有位置无空位时返回true，表示解已找到；递归调用后根据返回值判断是否成功，成功则直接返回，不再继续尝试
3. 正确回溯：仅当递归失败时才重置当前位置为0，尝试下一个数字；若所有数字都失败，返回false让上层递归继续回溯

内容的提问来源于stack exchange，提问作者Abdel Majid Kansoussi