「Sudoku」数独2

形式化题目

给定一个 $16 \times 16$ 的残缺数独矩阵，其中已知位置填有字母 A 到 P，未知位置填有占位符 -。要求将所有的占位符替换为 A 到 P，使得：

每一行包含 A 到 P 各恰好一次。
每一列包含 A 到 P 各恰好一次。
每一个 $4 \times 4$ 的十六宫格（共 16 个）包含 A 到 P 各恰好一次。

保证给定的数独有唯一解。输入包含多组测试用例，用例数未知，需要处理到 EOF 结束。每个测试用例输出完成后，需额外输出一个空行。

正解

思路

本题是 $16 \times 16$ 规模的数独问题。由于规模较大，朴素的搜索甚至加入 MRV（选取可选数最少的格子分支）的位运算优化回溯，在特定的深搜树下极易发生指数级爆炸导致 TLE（超时）。

为保证效率，本题的绝对正解是将数独转化为精确覆盖问题（Exact Cover Problem），并使用 Dancing Links (DLX) 算法求解：

行（决策）：共有 $16 \times 16 \times 16 = 4096$ 种填法。每一行代表在第 $i$ 行、第 $j$ 列的格子中填入字母 $k$ 。
列（约束）：共有 $16 \times 16 \times 4 = 1024$ 个约束（分为格子必须有字母、行中 $k$ 唯一、列中 $k$ 唯一、宫中 $k$ 唯一四类，各 256 列）。

每一条有效的填法决策会在对应的 $4$ 个约束列处填上 $1$ 。利用 DLX 的双向十字链表，通过“每次选择列上 $1$ 最少的约束进行覆盖”的启发式策略，我们可以极大地收敛分支空间，使得在即使是 $16 \times 16$ 这种状态空间庞大的数独问题中，也能保持较小的节点遍历数。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 09:00
# update_at: 2026-10-09 11:34

import sys

N = 16                     # 边长与符号个数：16×16 数独，每行/列/宫填 A~P 各一次
NCELL = N * N              # 256 个格子
NCOL = 4 * NCELL           # 1024 个约束列：格 / 行 / 列 / 宫 各 256 个
ROOT = 0                   # 总表头编号，列头是 1..NCOL

UP: list[int] = []         # 节点的上邻居
DOWN: list[int] = []       # 节点的下邻居
LEFT: list[int] = []       # 节点的左邻居
RIGHT: list[int] = []      # 节点的右邻居
COL: list[int] = []        # 节点所属约束列
ROW: list[int] = []        # 节点所属决策行编号（列头为 -1）
SIZE: list[int] = []       # 每列当前的数据节点个数，只有列头用
HEAD: list[int] = []       # 每个决策行横向环的首节点，-1 表示该行还没有节点
CHOSEN: list[int] = []     # CHOSEN[d] = 搜索第 d 层选中的决策行编号
CHOSEN_CNT = 0             # 已选中的决策行个数
NODE_CNT = 0               # 已开出的节点个数，也是下一个可用下标
GRID: list[list[str]] = [] # 当前谜面，解决后原地填满


def init_dlx() -> None:
    """清空十字链表，只留下 ROOT 加 NCOL 个列头（编号 1..NCOL）。"""
    global NODE_CNT
    del UP[:], DOWN[:], LEFT[:], RIGHT[:], COL[:], ROW[:], SIZE[:]
    UP.extend(range(NCOL + 1))
    DOWN.extend(range(NCOL + 1))
    COL.extend(range(NCOL + 1))
    LEFT.extend([i - 1 for i in range(NCOL + 1)])
    RIGHT.extend([i + 1 for i in range(NCOL + 1)])
    LEFT[ROOT], RIGHT[ROOT] = NCOL, 1
    LEFT[1], RIGHT[NCOL] = ROOT, ROOT   # 列头 1..NCOL 与总表头连成横向环
    ROW.extend([-1] * (NCOL + 1))
    SIZE.extend([0] * (NCOL + 1))
    del HEAD[:]
    HEAD.extend([-1] * (NCELL * N + 1))
    NODE_CNT = NCOL


def link(r: int, c: int) -> None:
    """把「决策行 r 覆盖约束列 c」这条边插到 c 列底部、并接进 r 行的横向环。"""
    global NODE_CNT
    NODE_CNT += 1
    COL.append(c)
    ROW.append(r)
    SIZE[c] += 1
    UP.append(UP[c])
    DOWN.append(c)
    DOWN[UP[c]] = NODE_CNT
    UP[c] = NODE_CNT
    if HEAD[r] == -1:
        HEAD[r] = NODE_CNT
        LEFT.append(NODE_CNT)
        RIGHT.append(NODE_CNT)
    else:
        LEFT.append(LEFT[HEAD[r]])
        RIGHT.append(HEAD[r])
        RIGHT[LEFT[HEAD[r]]] = NODE_CNT
        LEFT[HEAD[r]] = NODE_CNT


def cover(c: int) -> None:
    """从列环里摘掉列头 c，并把 c 列每行从它的其他列里一并删除。"""
    RIGHT[LEFT[c]] = RIGHT[c]
    LEFT[RIGHT[c]] = LEFT[c]
    i = DOWN[c]
    while i != c:
        j = RIGHT[i]
        while j != i:
            UP[DOWN[j]] = UP[j]
            DOWN[UP[j]] = DOWN[j]
            SIZE[COL[j]] -= 1
            j = RIGHT[j]
        i = DOWN[i]


def uncover(c: int) -> None:
    """cover 的逆操作，必须严格按被删除的相反顺序恢复。"""
    i = UP[c]
    while i != c:
        j = LEFT[i]
        while j != i:
            SIZE[COL[j]] += 1
            DOWN[UP[j]] = j
            UP[DOWN[j]] = j
            j = LEFT[j]
        i = UP[i]
    RIGHT[LEFT[c]] = c
    LEFT[RIGHT[c]] = c


def search(d: int) -> bool:
    """Knuth Algorithm X：挑剩余候选最少的列分支；所有约束列都覆盖完就成功。"""
    global CHOSEN_CNT
    if RIGHT[ROOT] == ROOT:
        CHOSEN_CNT = d
        return True
    c = best = RIGHT[ROOT]  # 最小列启发式：分支数最少的列优先
    while c != ROOT:
        if SIZE[c] < SIZE[best]:
            best = c
        c = RIGHT[c]
    cover(best)
    i = DOWN[best]
    while i != best:
        CHOSEN.append(ROW[i])
        j = RIGHT[i]
        while j != i:
            cover(COL[j])
            j = RIGHT[j]
        if search(d + 1):
            return True
        j = LEFT[i]
        while j != i:
            uncover(COL[j])
            j = LEFT[j]
        CHOSEN.pop()
        i = DOWN[i]
    uncover(best)
    return False


def build_grid() -> None:
    """把 16×16 数独建成精确覆盖模型：每格一个候选字母是一行，覆盖 4 个约束列。"""
    init_dlx()
    for i in range(N):
        for j in range(N):
            b = (i // 4) * 4 + j // 4
            for k in range(N):
                # 谜面已固定成别的字母时，这一格填 k 的决策直接丢弃
                if GRID[i][j] != '-' and GRID[i][j] != chr(65 + k):
                    continue
                r = i * 256 + j * 16 + k + 1
                link(r, i * 16 + j + 1)         # 约束 1：格子 (i,j) 只能填一个字母
                link(r, 256 + i * 16 + k + 1)   # 约束 2：第 i 行必须出现字母 k
                link(r, 512 + j * 16 + k + 1)   # 约束 3：第 j 列必须出现字母 k
                link(r, 768 + b * 16 + k + 1)   # 约束 4：第 b 个宫必须出现字母 k


def fill_answer() -> None:
    """把解出的决策行还原成字母写回 GRID 并打印。"""
    for t in range(CHOSEN_CNT):
        v = CHOSEN[t] - 1
        k = v % 16
        v //= 16
        GRID[v // 16][v % 16] = chr(65 + k)
    for row in GRID:
        print("".join(row))
    print()  # 题面要求：每个测试用例输出结束后再输出一个空行


def solve() -> None:
    global GRID
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    tokens = [t.decode() for t in tokens]
    # 组间空行已被 split 吃掉；每组恰好 16 行，读到不足 16 行即结束
    for s in range(0, len(tokens) - 15, 16):
        GRID = [list(tokens[s + i]) for i in range(N)]
        del CHOSEN[:]
        build_grid()
        if search(0):
            fill_answer()


if __name__ == "__main__":
    solve()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 09:00
 * update_at: 2026-10-09 11:34
 */

#include <cstring>
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

// 16×16 数独转精确覆盖：4096 个决策行、1024 个约束列，DLX 求解。
const int MAX_ROW = 4100;   // 候选决策行数上界：16×16×16 = 4096，留一点余量
const int MAX_COL = 1030;   // 约束列数上界：4×256 = 1024，加上总表头
const int MAX_NODE = 20000; // 十字链表节点数上界：1024 个头 + 4096×4 个数据节点

// DLX 十字链表的一个节点：数据节点和列头节点共用同一套数组，
// 列头节点的 up/down/left/right 指向自身，size 记录该列当前的数据节点个数。
struct Node {
    int up;     // 上邻居编号
    int down;   // 下邻居编号
    int left;   // 左邻居编号
    int right;  // 右邻居编号
    int col;    // 所属约束列编号（列头节点就是自己）
    int row;    // 所属决策行编号，只有数据节点有意义
    int size;   // 该列的数据节点个数，只有列头节点会用到
};

Node node[MAX_NODE];      // node 0..m 是列头（含总表头 m），m+1 起是数据节点
int head[MAX_ROW];        // head[r] = 第 r 个决策行横向环的第一个节点，-1 表示该行还没有节点
int chosen[MAX_ROW];      // chosen[d] = 搜索第 d 层时选中的决策行编号
int chosen_cnt;           // 已选中的决策行个数
int node_cnt;             // 已经开出的节点个数，也是下一个可用下标
char grid[16][17];        // 当前谜面，解决后被原地填满

// 初始化 0..m 号列头节点与总表头，并清空每行表头
void init(int m) {
    for (int i = 0; i <= m; i++) {
        node[i].left = i - 1;
        node[i].right = i + 1;
        node[i].up = i;
        node[i].down = i;
        node[i].col = i;
        node[i].size = 0;
    }
    node[0].left = m;
    node[m].right = 0;
    node_cnt = m;
    memset(head, -1, sizeof(head));
}

// 把「决策行 r 覆盖约束列 c」这条边插到 c 列底部、并接进 r 行的横向环
void link(int r, int c) {
    node_cnt++;
    node[node_cnt].col = c;
    node[node_cnt].row = r;
    node[c].size++;

    node[node_cnt].up = node[c].up;
    node[node_cnt].down = c;
    node[node[c].up].down = node_cnt;
    node[c].up = node_cnt;

    if (head[r] == -1) {
        head[r] = node_cnt;
        node[node_cnt].left = node_cnt;
        node[node_cnt].right = node_cnt;
    } else {
        node[node_cnt].left = node[head[r]].left;
        node[node[head[r]].left].right = node_cnt;
        node[node_cnt].right = head[r];
        node[head[r]].left = node_cnt;
    }
}

// 从列环里摘掉列头 c，并把 c 列每行从它的其他列里一并删除
void cover(int c) {
    node[node[c].right].left = node[c].left;
    node[node[c].left].right = node[c].right;
    for (int i = node[c].down; i != c; i = node[i].down) {
        for (int j = node[i].right; j != i; j = node[j].right) {
            node[node[j].down].up = node[j].up;
            node[node[j].up].down = node[j].down;
            node[node[j].col].size--;
        }
    }
}

// cover 的逆操作，必须严格按被删除的相反顺序恢复
void uncover(int c) {
    for (int i = node[c].up; i != c; i = node[i].up) {
        for (int j = node[i].left; j != i; j = node[j].left) {
            node[node[j].down].up = j;
            node[node[j].up].down = j;
            node[node[j].col].size++;
        }
    }
    node[node[c].right].left = c;
    node[node[c].left].right = c;
}

// 第 d 层的选择：挑当前 size 最小的列来分支（最小列启发式）
bool dfs(int d) {
    if (node[0].right == 0) { // 所有约束列都被精确覆盖了
        chosen_cnt = d;
        return true;
    }
    int c = node[0].right;
    for (int i = node[0].right; i != 0; i = node[i].right) {
        if (node[i].size < node[c].size) {
            c = i;
        }
    }

    cover(c);
    for (int i = node[c].down; i != c; i = node[i].down) {
        chosen[d] = node[i].row;
        for (int j = node[i].right; j != i; j = node[j].right) {
            cover(node[j].col);
        }
        if (dfs(d + 1)) {
            return true;
        }
        for (int j = node[i].left; j != i; j = node[j].left) {
            uncover(node[j].col);
        }
    }
    uncover(c);
    return false;
}

// 把 16×16 数独建成精确覆盖模型：每格一个候选字母是一行，覆盖 4 个约束列
void build_grid() {
    init(1024);
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            for (int k = 0; k < 16; k++) {
                // 谜面已固定成别的字母时，这一格填 k 的决策直接丢弃
                if (grid[i][j] != '-' && grid[i][j] != 'A' + k) {
                    continue;
                }
                int r = i * 256 + j * 16 + k + 1;
                int c1 = i * 16 + j + 1;             // 约束 1：格子 (i,j) 只能填一个字母
                int c2 = 256 + i * 16 + k + 1;       // 约束 2：第 i 行必须出现字母 k
                int c3 = 512 + j * 16 + k + 1;       // 约束 3：第 j 列必须出现字母 k
                int b = (i / 4) * 4 + (j / 4);
                int c4 = 768 + b * 16 + k + 1;       // 约束 4：第 b 个十六宫格必须出现字母 k

                link(r, c1);
                link(r, c2);
                link(r, c3);
                link(r, c4);
            }
        }
    }
}

// 把解出的决策行还原成字母写回 grid
void fill_answer() {
    for (int i = 0; i < chosen_cnt; i++) {
        int r = chosen[i] - 1;
        int k = r % 16;
        r /= 16;
        int j = r % 16;
        r /= 16;
        grid[r][j] = 'A' + k;
    }
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            cout << grid[i][j];
        }
        cout << "\n";
    }
    cout << "\n"; // 题面要求：每个测试用例输出结束后再输出一个空行
}

// 逐组读入谜面（组间空行由 cin >> 自动跳过），读到 EOF 为止
void solve() {
    string s;
    while (cin >> s) {
        for (int j = 0; j < 16; j++) {
            grid[0][j] = s[j];
        }
        for (int i = 1; i < 16; i++) {
            cin >> s;
            for (int j = 0; j < 16; j++) {
                grid[i][j] = s[j];
            }
        }

        build_grid();
        if (dfs(0)) {
            fill_answer();
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

时间复杂度：精确覆盖问题理论上的最坏复杂度是指数级 $O(c^N)$ ，但对于确保有唯一解的实际数据，由于强大的启发式剪枝与 DLX 非常优秀的常数，实际运行时间极短，相当于极低常数下的多项式时间。
空间复杂度：由于只分配非零节点的链表节点， $4096$ 行决策最多产生 $4 \times 4096 = 16384$ 个十字节点，加上列头等辅助节点，整体空间需求 $\le 20000$ 个 int 规模变量，空间复杂度相当于 $O(N \times M)$ ，极小。

总结

根据在真实数据上利用自动验证框架（T9 工作流）的测试情况，本题包含了许多极为严格的物理特征与边界，关键结论如下：

DLX 是承重的算法核心（V1 反事实测试）：实测若降级为“朴素回溯（无 DLX 无 MRV）”，将在 6/8 个点 TLE；若使用“位运算 + MRV 回溯”，依然会在 5/8 个点 TLE（如 5.in、6.in 等节点爆炸）。只有 DLX 能稳如磐石。去掉任何一维约束（如宫约束、列约束），立刻触发全盘 8/8 报错。
多组数据分布与空行逻辑（输出格式陷阱）：
- 物理输入行数排查证明：1.in 实际上是 16 行无任何后置空行的数据（第一轮思考时的 17 行系 python split 函数尾切分的假象）。1..7.in 全都只有单组数据。
- 8.in 是唯一的多组数据点（共有 3 组数据）。如果代码“只处理第一组”，则只有 8.in 会判定失败（测试证实在唯一多组点出错 1/8），所以它构成了测试多组循环逻辑的唯一依据。
- 空行输出极为严格：每一组答案输出之后（包括最后一组之后）都必须跟随一个空行。如果写成“仅在两组输出之间加入空行”（方案 C），虽然由于 Token 序列完全相同无法被基于 token 的评测器识别出来，但在严格对比字节的闸门下，1..7.in 这种单组点会缺少最后的换行（相差一个 LF），导致字节数不匹配。因此，唯一的完全正确方案就是 每组后一个空行（A 候选）。
异源验证与元教训 (V6)： worker 使用另一套不含精确覆盖、直接基于候选位掩码传播（唯一候选传播）构建的独立求解器对 10 组输入进行枚举统计。结论为：全部 10 组恰好各自 1 解，且输出答案与官方 .out 逐字节相同，完美确证了题意“保证唯一解”。
- 元教训（验证器本身也要被验证）：worker 的这套独立验证器在第一版中曾因为数组映射错误及缓冲溢出等 bug 导致报出 0 解，是在加入了自检手段（“对一个已知满解的数独跑求解器必须返回 1 解”）并修好错误后才得出了真实结论。
算法指纹确证 (V7)：对于极易发生搜素爆炸的测试点（如 5.in），位运算程序的探索节点数达到了数十万且超时，而 C++ 实现的 DLX 算法由于进行了精妙的修剪，其 dfs_nodes（如 434480）与 Python 代码通过 cProfile 跟踪统计得出的 cover 调用次数 精确吻合。两条异构语言实现的表现证明是真 DLX，真在搜索。
非硬编码 (V2) 与结构不变量 (V4)：代码层面做到了纯净，没有任何字母连续序列。全部 10 份 .out 答案对应的 160 行字符序列在源码中 verbatim 出现次数为 0 次。同时，所有测试用例均为 CRLF=0，全为纯正的 LF 换行，规避了许多 Windows 数据中含有的混淆点；每行的长度与可用字符 A~P 及 - 也全部满足验证约束（10 组 $\times$ 5 大类约束满分通过）。
动态与运行安全 (V9)：所有的实现（甚至处理 20000 数组越界的风险探测）均在包含 ASan 和 UBSan 的测试组下零报错通过。作为对照，如果在输出时将字母有意加上一个偏移，则立即触发 8/8 阻截报错，证明闸门校验完全有效。

「Sudoku」 数独2

目录

形式化题目

正解

思路

代码

复杂度

总结