数独求解
进阶数独把回溯从"枚举"推进到"带强约束的搜索"。
// 算法讲解
数独求解
用回溯法求解一个 4×4 数独。
待机
速度 中
待机 ⌨1bool solve(vector<vector<char>>& board) {
2 for (int r = 0; r < 9; r++) {
3 for (int c = 0; c < 9; c++) {
4 if (board[r][c] != '.') continue;
5 for (char ch = '1'; ch <= '9'; ch++) {
6 if (!valid(board, r, c, ch)) continue;
7 board[r][c] = ch;
8 if (solve(board)) return true;
9 board[r][c] = '.';
10 }
11 return false;
12 }
13 }
14 return true;
15}
复杂度分析
时间 最坏指数级
空间 O(空格数)
最优 剪枝充分时很快
最坏 指数级
算法讲解
数独求解的核心是找到一个空格，尝试填入 1 到 9 中所有合法数字。
如果某个数字能同时满足行、列和 3x3 宫约束，就继续递归处理下一个空格；否则立即剪枝。
这类问题特别能体现"约束越强，搜索树越瘦"，也是启发式搜索的常见起点。
高效实现通常会预维护行、列、宫的占用状态，而不是每次都整盘扫描。