数独

回溯与搜索 · 约束满足

填数游戏，也是约束回溯的名场面

数独要把每个空格填上数字，使每一行、每一列、每一宫（小方块）里的数字都不重复。它和 N 皇后同属「棋盘约束」回溯，但换了个玩法：N 皇后是放置型（每列放一个皇后、避开攻击），数独是填数型（每个空格从 1..n 里挑一个、满足行/列/宫三重约束）。

试填 → 冲突就换 → 死路就回退

做法是回溯：找到一个空格，从小到大试 1..n；如果某个数字和同行、同列、同宫已有的数字冲突，就换下一个；如果不冲突，就填进去、去填下一个空格。要是某个空格 1..n全都填不了，说明之前的某一步填错了——撤销刚才的填入、回退到上一个空格，换个数字重来。「撤销」正是回溯的关键：错了能退回去，而不是一条道走到黑。

下面是一张 4×4 迷你数独（2×2 宫，加粗为题目给定）。点「下一步」逐步看：当前格琥珀环，试填数字冲突时标红、合法时填绿。特别留意中间——某个空格先填了一个当下看着合法、其实全局错误的数，一路填到死路后，撤销、回退，改填另一个数才走通（本例有 2 次这样的回退）。走到底，整盘填满。右侧代码随每一步同步高亮。

初始盘：加粗为给定数字，共 5 个空格待填（每空格试填 1..4，行/列/宫不重复）

1function solveSudoku(grid: number[][], n: number, box: number): boolean {
const valid = (r: number, c: number, v: number): boolean => {
  for (let i = 0; i < n; i++)
    if (grid[r][i] === v || grid[i][c] === v) return false;
  const br = Math.floor(r / box) * box, bc = Math.floor(c / box) * box;
  for (let i = br; i < br + box; i++)
    for (let j = bc; j < bc + box; j++)
      if (grid[i][j] === v) return false;
  return true;
};
for (let r = 0; r < n; r++)
  for (let c = 0; c < n; c++)
    if (grid[r][c] === 0) {              // 找到一个空格
      for (let v = 1; v <= n; v++) {
        if (valid(r, c, v)) {            // 合法 → 填；不合法 → 换下一个
          grid[r][c] = v;                // 填入
          if (solveSudoku(grid, n, box)) return true;
          grid[r][c] = 0;                // 走不通 → 撤销、回退
        }
      }
      return false;                      // 1..n 都填不了 → 死路
    }
return true;                             // 无空格 → 完成
24}

盘: 4×4（2×2 宫）
当前格: -
已填空格: 0 / 5

真实 9×9 数独空格更多、回溯更深，但骨架完全一样。想更快，可以用约束传播（优先填候选最少的格，即 MRV）、位运算记录每行列宫的可用数字，甚至 Dancing Links——但内核依然是「试探 → 冲突 → 回退」。

约束满足与回溯

约束满足问题（CSP）：数独、地图着色、排课、八皇后，本质都是「给变量赋值、满足一堆约束」，回溯是通用解法。
剪枝越早越好：一填入就检查冲突（本页做法），比填满再验快得多。
回溯的两种棋盘形态：N 皇后（放置）+ 数独（填数），加上决策树、网格，凑齐回溯的各种状态空间。