JavaScript递归回溯算法应用：从数独终盘挖空生成唯一解数独

阿华AIGC实验室

2026-5-26

生成唯一解数独：从终盘移除指定数量数字的实现方案

嘿，我刚好之前折腾过数独生成的问题，结合你已经搞定回溯求解器的基础，咱们一步步来解决这个“挖空保唯一解”的问题。

核心思路

要生成唯一解的有效数独，绝对不能随便挖空——随便删数字大概率会导致盘面有多个解。核心逻辑是：试探性挖空+验证解的唯一性，每挖掉一个数字后，立刻用你的回溯算法验证当前盘面是否只有一个解，只有满足条件才保留这个空，否则把数字填回去。

具体实现步骤

从终盘出发：基于你已有的solvedSudokuGrid，先做一个深拷贝，避免修改原终盘数据。
随机化挖空顺序：生成所有单元格的位置列表，用洗牌算法打乱顺序（避免每次生成的数独布局一模一样）。
逐个试探挖空：
- 记录当前单元格的原始数字
- 将该单元格设为空（比如用''或'.'表示）
- 用修改后的回溯求解器计算当前盘面的解的数量
- 如果解的数量为1，保留挖空；如果大于1，把数字填回，跳过这个位置
- 重复直到挖到指定数量的空，或者无法继续挖（说明目标数量超过当前终盘的最大可挖空数）

JavaScript 示例代码

首先，我们需要修改你的回溯求解器，让它能统计解的数量，且找到第二个解就停止计算（大幅提升效率）：

// 计算数独盘面的解的数量，找到第2个解就立刻终止
function countSolutions(grid) {
  let solutionCount = 0;

  function backtrack() {
    // 找到第一个空单元格
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (grid[row][col] === '') {
          // 尝试1-9的数字
          for (let num = 1; num <= 9; num++) {
            const numStr = num.toString();
            if (isValid(grid, row, col, numStr)) {
              grid[row][col] = numStr;
              backtrack();
              grid[row][col] = ''; // 回溯

              // 一旦找到2个解，直接返回，无需继续计算
              if (solutionCount >= 2) return;
            }
          }
          return; // 无可用数字，回溯
        }
      }
    }
    solutionCount++; // 找到一个完整解
  }

  backtrack();
  return solutionCount;
}

// 验证数字是否可填入当前单元格（行、列、3x3宫检查）
function isValid(grid, row, col, num) {
  // 检查行
  for (let c = 0; c < 9; c++) {
    if (grid[row][c] === num) return false;
  }
  // 检查列
  for (let r = 0; r < 9; r++) {
    if (grid[r][col] === num) return false;
  }
  // 检查3x3宫
  const boxStartRow = Math.floor(row / 3) * 3;
  const boxStartCol = Math.floor(col / 3) * 3;
  for (let r = boxStartRow; r < boxStartRow + 3; r++) {
    for (let c = boxStartCol; c < boxStartCol + 3; c++) {
      if (grid[r][c] === num) return false;
    }
  }
  return true;
}

然后是核心的挖空函数：

function generateUniqueSudoku(solvedGrid, targetEmptyCount) {
  // 深拷贝终盘，避免修改原数据
  const grid = solvedGrid.map(row => [...row]);
  // 生成所有单元格位置，并打乱顺序（Fisher-Yates洗牌）
  const positions = [];
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      positions.push([row, col]);
    }
  }
  // 洗牌算法
  for (let i = positions.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [positions[i], positions[j]] = [positions[j], positions[i]];
  }

  let currentEmptyCount = 0;

  for (const [row, col] of positions) {
    if (currentEmptyCount >= targetEmptyCount) break;

    const originalNum = grid[row][col];
    // 尝试挖空
    grid[row][col] = '';

    // 验证解的唯一性
    const solutions = countSolutions(grid);
    if (solutions === 1) {
      // 唯一解，保留挖空
      currentEmptyCount++;
    } else {
      // 多解或无解，填回原数字
      grid[row][col] = originalNum;
    }
  }

  return {
    puzzleGrid: grid,
    actualEmptyCells: currentEmptyCount
  };
}