数独
回溯与搜索 · 约束满足
填数游戏，也是约束回溯的名场面
数独要把每个空格填上数字，使每一行、每一列、每一宫（小方块）里的数字都不重复。它和 N 皇后同属「棋盘约束」回溯，但换了个玩法：N 皇后是放置型（每列放一个皇后、避开攻击），数独是填数型（每个空格从 1..n 里挑一个、满足行/列/宫三重约束）。
试填 → 冲突就换 → 死路就回退
做法是回溯：找到一个空格，从小到大试 1..n；如果某个数字和同行、同列、同宫已有的数字冲突，就换下一个；如果不冲突，就填进去、去填下一个空格。要是某个空格 1..n全都填不了，说明之前的某一步填错了——撤销刚才的填入、回退到上一个空格，换个数字重来。「撤销」正是回溯的关键：错了能退回去，而不是一条道走到黑。
下面是一张 4×4 迷你数独（2×2 宫，加粗为题目给定）。点「下一步」逐步看：当前格琥珀环，试填数字冲突时标红、合法时填绿。特别留意中间——某个空格先填了一个当下看着合法、其实全局错误的数，一路填到死路后，撤销、回退，改填另一个数才走通（本例有 2 次这样的回退）。走到底，整盘填满。右侧代码随每一步同步高亮。
2
3
4
3
4
1
2
2
4
2
3
初始盘：加粗为给定数字，共 5 个空格待填（每空格试填 1..4，行/列/宫不重复）
1function solveSudoku(grid: number[][], n: number, box: number): boolean {
2 const valid = (r: number, c: number, v: number): boolean => {
3 for (let i = 0; i < n; i++)
4 if (grid[r][i] === v || grid[i][c] === v) return false;
5 const br = Math.floor(r / box) * box, bc = Math.floor(c / box) * box;
6 for (let i = br; i < br + box; i++)
7 for (let j = bc; j < bc + box; j++)
8 if (grid[i][j] === v) return false;
9 return true;
10 };
11 for (let r = 0; r < n; r++)
12 for (let c = 0; c < n; c++)
13 if (grid[r][c] === 0) { // 找到一个空格
14 for (let v = 1; v <= n; v++) {
15 if (valid(r, c, v)) { // 合法 → 填；不合法 → 换下一个
16 grid[r][c] = v; // 填入
17 if (solveSudoku(grid, n, box)) return true;
18 grid[r][c] = 0; // 走不通 → 撤销、回退
19 }
20 }
21 return false; // 1..n 都填不了 → 死路
22 }
23 return true; // 无空格 → 完成
24}
盘4×4（2×2 宫）
当前格-
已填空格0 / 5
1 / 22
真实 9×9 数独空格更多、回溯更深，但骨架完全一样。想更快，可以用约束传播（优先填候选最少的格，即 MRV）、位运算记录每行列宫的可用数字，甚至 Dancing Links——但内核依然是「试探 → 冲突 → 回退」。
约束满足与回溯
约束满足问题（CSP）：数独、地图着色、排课、八皇后，本质都是「给变量赋值、满足一堆约束」，回溯是通用解法。
剪枝越早越好：一填入就检查冲突（本页做法），比填满再验快得多。
回溯的两种棋盘形态：N 皇后（放置）+ 数独（填数），加上决策树、网格，凑齐回溯的各种状态空间。
剪枝越早越好：一填入就检查冲突（本页做法），比填满再验快得多。
回溯的两种棋盘形态：N 皇后（放置）+ 数独（填数），加上决策树、网格，凑齐回溯的各种状态空间。