为何数独回溯算法随机位置排序比顺序排序慢？如何优化？

一、耗时差异的核心原因 #

1. 回溯分支的剪枝效率差异 #

从左到右的顺序填充是按行递进，早期填充的位置会快速对后续位置形成约束，减少无效分支的产生。比如先填[0,0]后，[0,1]的可选值会被[0,0]的数值限制，分支数逐步收敛。

而随机位置顺序可能优先选择约束极弱的位置（比如中间的[4,4]，初始状态下所在行、列、宫全空，可选值有9个），每个选择都会衍生出大量子分支，直到后续填充时才发现冲突，导致回溯的深度和次数暴增，整体时间复杂度大幅上升。

2. posOrder.find的重复遍历开销 #

原代码中每次回溯都调用posOrder.find(p => board[p[0]][p[1]] === 0)查找空白位置：

• 顺序posOrder中空白位置是按排列顺序存在的，find只需遍历少量元素就能找到目标；
• 随机posOrder中空白位置的分布是随机的，每次find可能需要遍历整个数组才能找到第一个空白位置，在递归的深层调用中，这种重复遍历的开销会被指数级放大。

二、高效随机位置顺序的实现方案 #

要实现每次运行随机化位置顺序，同时避免原代码的性能问题，需要解决重复遍历和分支无效扩张的问题，具体修改如下：

1. 预生成全局随机位置列表 #

提前生成所有数独位置的随机排列，确保每次运行顺序不同，替代固定的随机数组。

2. 回溯时跟踪当前处理索引 #

不再每次遍历整个数组找空白位置，而是通过索引记录当前处理到的位置，从索引开始往后查找未填充的位置，避免重复遍历已处理过的位置。

优化后的完整代码 #

// 生成随机位置顺序，每次运行都会生成新的随机序列
const generateRandomPosOrder = () => {
  const order = [];
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      order.push([row, col]);
    }
  }
  return shuffleArray(order);
};

// 预生成本次运行的随机位置顺序
let posOrder = generateRandomPosOrder();

const backtrack = (board, idx = 0) => {
  // 从当前索引开始，找到第一个未填充的位置
  let currentIdx = idx;
  while (currentIdx < posOrder.length && board[posOrder[currentIdx][0]][posOrder[currentIdx][1]] !== 0) {
    currentIdx++;
  }
  // 所有位置已填充，返回成功
  if (currentIdx >= posOrder.length) {
    return true;
  }

  const [row, col] = posOrder[currentIdx];
  // 随机尝试数字顺序
  return shuffleArray([1, 2, 3, 4, 5, 6, 7, 8, 9]).some(number => {
    if (!numberExists(board, number, row, col)) {
      board[row][col] = number;
      // 递归处理下一个位置（从currentIdx+1开始，避免重复遍历前面的位置）
      if (backtrack(board, currentIdx + 1)) {
        return true;
      }
      // 回溯
      board[row][col] = 0;
    }
    return false;
  });
};

const shuffleArray = (array) => {
  // 复制数组，避免修改原数组
  const arr = [...array];
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
};

const numberInRow = (board, number, row) => board[row].some(col => col === number);
const numberInCol = (board, number, col) => board.some(row => row[col] === number);
const numberInRegion = (board, number, row, col) => {
  const r = 3 * Math.floor(row / 3);
  const c = 3 * Math.floor(col / 3);
  return [board[r], board[r+1], board[r+2]].some(arr => 
    [arr[c], arr[c+1], arr[c+2]].some(nbr => nbr === number)
  );
};
const numberExists = (board, number, row, col) => (
  numberInRow(board, number, row) ||
  numberInCol(board, number, col) ||
  numberInRegion(board, number, row, col)
);

// 测试空数独板
const sudokuBoard = Array(9).fill().map(() => Array(9).fill(0));
backtrack(sudokuBoard);
console.log(sudokuBoard);

进阶优化（可选） #

如果希望在随机位置的同时进一步提升效率，可以结合最少剩余值（MRV）启发式：每次从空白位置中随机选择可选值最少的位置进行填充，这样能大幅减少无效分支的数量。示例代码如下：

const backtrackMRV = (board) => {
  // 收集所有空白位置，并计算每个位置的可选值数量
  const emptyPositions = [];
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        // 计算可选值数量
        let count = 0;
        for (let num = 1; num <=9; num++) {
          if (!numberExists(board, num, row, col)) count++;
        }
        emptyPositions.push({ pos: [row, col], options: count });
      }
    }
  }
  if (emptyPositions.length === 0) return true;

  // 按可选值数量排序，随机选择同数量级的位置
  emptyPositions.sort((a,b) => a.options - b.options);
  const minOptions = emptyPositions[0].options;
  const candidates = emptyPositions.filter(p => p.options === minOptions);
  const { pos: [row, col] } = candidates[Math.floor(Math.random() * candidates.length)];

  return shuffleArray([1,2,3,4,5,6,7,8,9]).some(number => {
    if (!numberExists(board, number, row, col)) {
      board[row][col] = number;
      if (backtrackMRV(board)) return true;
      board[row][col] = 0;
    }
    return false;
  });
};

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