数独求解器

本章导读

数独是一个约束满足问题（CSP）：81 个格子，每个格子取值 1-9，受行、列、宫三重约束。回溯法是解决 CSP 的经典方法：选一个空格，尝试 1-9，检查约束，满足则递归填下一个，不满足则回退换数字。本章的代码不到 100 行，但涵盖了算法设计的核心思想。

49.1 问题建模

数独网格用 9×9 的二维数组表示，0 表示空格：

// 数独网格：0 = 空格，1-9 = 已填数字
// 用一维数组模拟二维：grid[row * 9 + col]
array<int> grid = [
    5,3,0, 0,7,0, 0,0,0,
    6,0,0, 1,9,5, 0,0,0,
    0,9,8, 0,0,0, 0,6,0,

    8,0,0, 0,6,0, 0,0,3,
    4,0,0, 8,0,3, 0,0,1,
    7,0,0, 0,2,0, 0,0,6,

    0,6,0, 0,0,0, 2,8,0,
    0,0,0, 4,1,9, 0,0,5,
    0,0,0, 0,8,0, 0,7,9
]

// 辅助函数：获取/设置格子
func getCell(array<int> g, int row, int col) as int
    return g[row * 9 + col]
end

func setCell(array<int> g, int row, int col, int val)
    g[row * 9 + col] = val
end

为什么用一维数组？xlang 的 array<int> 是静态泛型容器（第 16 章），性能优于嵌套 list。索引计算 row * 9 + col 简单高效。

49.2 约束检查

在格子 (row, col) 填入数字 val 前，必须检查三个约束：

func isValid(array<int> g, int row, int col, int val) as bool
    // 检查行：同一行不能有重复
    int c = 0
    while c < 9
        if g[row * 9 + c] == val then
            return false
        end
        c += 1
    end

    // 检查列：同一列不能有重复
    int r = 0
    while r < 9
        if g[r * 9 + col] == val then
            return false
        end
        r += 1
    end

    // 检查 3×3 宫：同一宫不能有重复
    int boxRow = (row / 3) * 3
    int boxCol = (col / 3) * 3
    int dr = 0
    while dr < 3
        int dc = 0
        while dc < 3
            if g[(boxRow + dr) * 9 + (boxCol + dc)] == val then
                return false
            end
            dc += 1
        end
        dr += 1
    end

    return true
end

宫的定位公式：boxRow = (row / 3) * 3，boxCol = (col / 3) * 3。整数除法自动向下取整，将 0-8 映射到 0、3、6。

49.3 回溯法核心

回溯法的四步模式：

1. 选择：找一个空格，尝试填入 1-9
2. 检查：isValid 验证约束
3. 递归：约束满足则递归填下一个空格
4. 撤销：递归失败则恢复为 0，尝试下一个数字

func solve(array<int> g) as bool
    // 找第一个空格
    int i = 0
    while i < 81
        if g[i] == 0 then
            int row = i / 9
            int col = i % 9

            // 尝试 1-9
            int val = 1
            while val <= 9
                if isValid(g, row, col, val) then
                    g[i] = val              // 选择

                    if solve(g) then        // 递归
                        return true
                    end

                    g[i] = 0               // 撤销（回溯）
                end
                val += 1
            end

            return false   // 1-9 都不行，此路不通
        end
        i += 1
    end

    return true   // 没有空格了，解题完成
end

递归终止条件：遍历完 81 个格子都没有空格（i == 81），说明所有格子都填好了，返回 true。

49.4 完整求解器

把各部分组合成完整程序：

// sudoku.xl — 数独求解器

func isValid(array<int> g, int row, int col, int val) as bool
    int c = 0
    while c < 9
        if g[row * 9 + c] == val then return false end
        c += 1
    end
    int r = 0
    while r < 9
        if g[r * 9 + col] == val then return false end
        r += 1
    end
    int boxRow = (row / 3) * 3
    int boxCol = (col / 3) * 3
    int dr = 0
    while dr < 3
        int dc = 0
        while dc < 3
            if g[(boxRow + dr) * 9 + (boxCol + dc)] == val then return false end
            dc += 1
        end
        dr += 1
    end
    return true
end

func solve(array<int> g) as bool
    int i = 0
    while i < 81
        if g[i] == 0 then
            int row = i / 9
            int col = i % 9
            int val = 1
            while val <= 9
                if isValid(g, row, col, val) then
                    g[i] = val
                    if solve(g) then return true end
                    g[i] = 0
                end
                val += 1
            end
            return false
        end
        i += 1
    end
    return true
end

func printGrid(array<int> g)
    int r = 0
    while r < 9
        string line = ""
        int c = 0
        while c < 9
            if c > 0 and c % 3 == 0 then line += " | " end
            line += g[r * 9 + c].toString()
            c += 1
        end
        println(line)
        if r == 2 or r == 5 then println("------+-------+------") end
        r += 1
    end
end

// 主程序
array<int> puzzle = [
    5,3,0, 0,7,0, 0,0,0,
    6,0,0, 1,9,5, 0,0,0,
    0,9,8, 0,0,0, 0,6,0,
    8,0,0, 0,6,0, 0,0,3,
    4,0,0, 8,0,3, 0,0,1,
    7,0,0, 0,2,0, 0,0,6,
    0,6,0, 0,0,0, 2,8,0,
    0,0,0, 4,1,9, 0,0,5,
    0,0,0, 0,8,0, 0,7,9
]

println("=== 谜题 ===")
printGrid(puzzle)

if solve(puzzle) then
    println("\n=== 解答 ===")
    printGrid(puzzle)
else
    println("无解！")
end

49.5 格式化输出

好的输出让结果一目了然。printGrid 用分隔线区分 3×3 宫：

// 输出效果：
// 5 3 4 | 6 7 8 | 9 1 2
// 6 7 2 | 1 9 5 | 3 4 8
// 1 9 8 | 3 4 2 | 5 6 7
// ------+-------+------
// 8 5 9 | 7 6 1 | 4 2 3
// ...

格式化技巧：每 3 列插入 " | "，第 2、5 行后插入分隔线。用 c % 3 == 0 判断列边界，r == 2 or r == 5 判断行边界。

49.6 多解检测

一个合格的数独谜题应该有且仅有一个解。检测多解：找到第一个解后继续搜索：

func countSolutions(array<int> g, int limit) as int
    int count = 0
    int i = 0
    while i < 81
        if g[i] == 0 then
            int row = i / 9
            int col = i % 9
            int val = 1
            while val <= 9
                if isValid(g, row, col, val) then
                    g[i] = val
                    count += countSolutions(g, limit - count)
                    g[i] = 0
                    if count >= limit then return count end
                end
                val += 1
            end
            return count
        end
        i += 1
    end
    return count + 1   // 找到一个完整解
end

// 使用：检查是否唯一解
array<int> copy = puzzle   // 复制一份
int solutions = countSolutions(copy, 2)
if solutions == 1 then
    println("唯一解")
elif solutions >= 2 then
    println("多解（至少 2 个）")
else
    println("无解")
end

limit 参数是性能关键——找到 2 个解就停止，不需要枚举所有解（可能有数百万个）。

49.7 候选数剪枝

基础版按顺序找第一个空格。优化：优先填候选数最少的空格（MRV 启发式）：

func countCandidates(array<int> g, int row, int col) as int
    int count = 0
    int val = 1
    while val <= 9
        if isValid(g, row, col, val) then
            count += 1
        end
        val += 1
    end
    return count
end

func findBestCell(array<int> g) as int
    int bestIdx = -1
    int bestCount = 10   // 最大候选数为 9
    int i = 0
    while i < 81
        if g[i] == 0 then
            int cnt = countCandidates(g, i / 9, i % 9)
            if cnt < bestCount then
                bestCount = cnt
                bestIdx = i
                if cnt == 1 then return bestIdx end  // 只有一个选择，最优
            end
        end
        i += 1
    end
    return bestIdx
end

// 改进版 solve：每次选候选数最少的格子
func solveOptimized(array<int> g) as bool
    int idx = findBestCell(g)
    if idx == -1 then return true end   // 无空格，完成

    int row = idx / 9
    int col = idx % 9
    int val = 1
    while val <= 9
        if isValid(g, row, col, val) then
            g[idx] = val
            if solveOptimized(g) then return true end
            g[idx] = 0
        end
        val += 1
    end
    return false
end

MRV（Minimum Remaining Values）启发式：候选数越少，分支越少，搜索树越小。对于"难"谜题，这个优化可以将求解时间从秒级降到毫秒级。

49.8 谜题生成

生成一个有唯一解的谜题：

// 策略：从完整解开始，随机挖空，每次挖空后验证唯一解
func generatePuzzle(array<int> g, int blanks)
    // 先求解得到完整网格
    solve(g)

    // 随机挖空
    int removed = 0
    while removed < blanks
        int idx = math.random(0, 80)
        if g[idx] != 0 then
            int backup = g[idx]
            g[idx] = 0

            // 验证唯一解
            array<int> copy = g
            if countSolutions(copy, 2) != 1 then
                g[idx] = backup   // 恢复——挖这个会导致多解
            else
                removed += 1
            end
        end
    end
end

blanks 控制难度：30 个空格是简单，50 个是困难，60+ 是专家级。

49.9 测试与验证

// 验证解答是否正确
func verifySolution(array<int> g) as bool
    int r = 0
    while r < 9
        // 检查每行包含 1-9
        set<int> rowSet = set<int>()
        int c = 0
        while c < 9
            int v = g[r * 9 + c]
            if v < 1 or v > 9 then return false end
            rowSet.add(v)
            c += 1
        end
        if rowSet.len() != 9 then return false end
        r += 1
    end
    // 类似检查每列和每宫...
    return true
end

// 测试用例
array<int> easy = [
    0,0,0, 2,6,0, 7,0,1,
    6,8,0, 0,7,0, 0,9,0,
    1,9,0, 0,0,4, 5,0,0,
    8,2,0, 1,0,0, 0,4,0,
    0,0,4, 6,0,2, 9,0,0,
    0,5,0, 0,0,3, 0,2,8,
    0,0,9, 3,0,0, 0,7,4,
    0,4,0, 0,5,0, 0,3,6,
    7,0,3, 0,1,8, 0,0,0
]
assert solve(easy), "easy puzzle should have solution"
assert verifySolution(easy), "solution should be valid"

49.10 扩展方向

数独求解器可以向多个方向扩展：

• 位运算加速：用 9 位整数表示候选集合，交集/并集用 &/| 运算，比循环快 10 倍
• 精确覆盖：将数独转化为精确覆盖问题，用 Algorithm X（Dancing Links）求解
• 16×16 变体：扩展为 16 宫数独，约束检查逻辑相同
• 对角线数独：额外约束两条对角线也不重复
• HTTP API：结合第 44 章，把求解器包装为 Web 服务

深入细节

⚠️ 常见错误

本章小结

复习题

1. 回溯法的四步模式是什么？"撤销"步骤为什么不可省略？
2. 数独的搜索空间有多大？为什么暴力穷举不可行？
3. 宫定位公式 (row/3)*3 的数学原理是什么？
4. MRV 启发式为什么能加速搜索？什么情况下效果最明显？
5. countSolutions 的 limit 参数解决什么问题？
6. 生成谜题时为什么每次挖空后要验证唯一解？
7. 如果用位运算表示候选集合，如何快速求交集？
8. array<int> copy = g 是什么语义？如果换成 list 需要注意什么？

编程练习