Node.js递归生成数独数组时偶发无有效解问题如何解决？

核心问题分析 #

你当前的代码逻辑存在的核心缺陷是无回溯机制：遇到第一个符合规则的数字就直接填入单元格，不会验证后续填充是否能走通，一旦后续出现某个单元格无合法数字可填的情况，没有回退修改前面已填数字的逻辑，自然会频繁出现无有效解的问题。

改造思路 #

回溯算法的核心逻辑是「试错+回退」：

1. 每次优先找到第一个未填充（值为0）的单元格
2. 生成该单元格所有合法的可填数字，可随机打乱顺序保证每次生成的数独不同
3. 依次填入合法数字后递归调用填充函数验证后续路径是否能走通
4. 如果递归返回成功说明当前数字选择正确，直接结束逻辑
5. 如果递归返回失败说明当前数字选择错误，将单元格重置为0后尝试下一个数字
6. 所有数字都尝试失败则返回失败，触发上层逻辑回退
7. 所有单元格都填充完成则返回成功，结束递归

改造后代码 #

1. 洗牌函数（可选，用于生成不同的数独） #

// Fisher-Yates 数组洗牌算法
const shuffle = (arr) => {
  for (let i = arr.length - 1; i > 0; i--) {
    const randomIndex = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]];
  }
  return arr;
}

2. 改造后的solveGrid函数 #

sudokuArr = new Array(81).fill(0);
fillGrid(); // 填充初始的三个九宫格

const solveGrid = () => {
  // 遍历找到第一个未填充的单元格
  for (let i = 0; i < sudokuArr.length; i++) {
    if (sudokuArr[i] !== 0) continue;

    const { block, row, col } = getSudokuVars(i);
    // 合并当前单元格所有已使用的数字
    const usedNums = new Set([
      ...getNumbersInBlock(block),
      ...getNumbersInRow(row),
      ...getNumbersInCol(col)
    ]);
    // 生成待尝试的数字列表，打乱顺序避免每次生成相同数独
    const numsToTry = shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9]);

    // 遍历所有待尝试的数字
    for (const num of numsToTry) {
      if (!usedNums.has(num)) {
        // 填入当前数字
        sudokuArr[i] = num;
        // 递归填充后续单元格
        if (solveGrid()) {
          // 后续填充成功，直接返回
          return true;
        }
        // 后续填充失败，回溯重置当前单元格
        sudokuArr[i] = 0;
      }
    }
    // 所有数字都尝试失败，返回失败触发上层回溯
    return false;
  }
  // 所有单元格填充完成，返回成功
  return true;
}

// 调用方法
solveGrid();
// 调用完成后 sudokuArr 就是完整的数独解

逻辑说明 #

• 用Set存储已使用的数字，判断效率比数组includes更高
• 每次递归只处理第一个空单元格，避免重复遍历浪费性能
• 所有路径都会被遍历到，只要初始填充的三个九宫格没有逻辑冲突，就一定能找到有效解

内容的提问来源于stack exchange，提问作者Nate Simonsen