「Sudoku」数独

形式化题目

给定一个 $16\times16$ 的矩阵，符号集为 $\{\texttt{A},\dots,\texttt{P}\}$ ，部分格子已填，其余为空。要求给所有空格填上符号，使得：

每一行 16 个符号各恰好出现一次；
每一列 16 个符号各恰好出现一次；
每个 $4\times4$ 宫（把矩阵切成 $4\times4$ 块）16 个符号各恰好出现一次。

题目保证每个谜面恰有一组解。输入含多组谜面，以单独一行 end 结束。

数据说明：本 OJ 的测试数据把 16 个符号按每行 16 个字符逐行给出（谜面之间隔一个空行），空格用 - 表示，与原题面（一行 81/256 个字符、. 表示空格、以 end 结尾）在格式上略有出入。下面的代码对两种写法都做了兼容：读入时把 end 丢弃，其余 token 拼接后按每 256 个字符切谜面；空格同时接受 - 和 .。

正解

思路

朴素做法：最直接的想法是 DFS——逐个处理空格，对每个空格枚举行、列、宫都没出现过的符号，全部填完就得到解。用 3 张位图表（行/列/宫 → 已出现符号集合）可以 $O(1)$ 判断与更新。但在 $16\times16$ 的棋盘上，中间过程大量空格仍有五六个候选符号，搜索树接近"每层叉积"的规模，这个写法在本题数据上跑不出结果。

瓶颈在哪：纯 DFS 的分支发生在"格子"，而约束被孤立地看——一个格子有 6 个候选就产生 6 个分支，哪怕其中 5 个会让某个符号在它所在的行/列/宫里"无家可归"。要让搜索有效，必须让每一步分支都尽量少的浪费，即：

分支前先做约束传播：候选唯一就填，某符号只剩一格可放也直接填；
分支时选候选最少的约束来分裂。

精确覆盖建模：这两点恰好是 Dancing Links（Algorithm X）的拿手好戏。把数独写成精确覆盖问题——设计 4 类"列"（约束），每个候选填法 $(格\ p, 值\ v)$ 是一个恰好覆盖 4 个约束的"行"：

约束列	个数	含义
`cell(p)`	256	格 $p$ 恰好填一个符号
`row(r,v)`	256	第 $r$ 行恰好有一个 $v$
`col(c,v)`	256	第 $c$ 列恰好有一个 $v$
`box(b,v)`	256	第 $b$ 宫恰好有一个 $v$

于是"填完整个数独" = “选出一批候选行，使 1024 个约束列各被覆盖恰好一次”。给定符号就是把对应行从矩阵中永久选中（删掉它覆盖的 4 列及所有冲突行）。

Algorithm X 如何消掉朴素 DFS 的浪费：

min 取候选最少的列分支——若某列只剩 1 行，这一步是必然（等价于唯一候选/隐藏唯一传播），分支数不增加；若某列为空则立刻回溯（等价于"符号无处可放"的矛盾检测）。整个搜索树被剪得只剩必要的分叉。
删除/恢复只沿 4 条双向环链进行，每次分支的代价与受影响的约束数成正比，而不是整个棋盘。

以样例第一问（第一个谜面）为例，选列的顺序大致是：

flowchart TD
    A["初始：给定格锁定约 60 个候选行"] --> B["选中某列 (候选 2 行)"]
    B --> C["传播：一串列只剩 1 行，连锁选中"]
    C --> D{"还有约束列未覆盖？"}
    D -- "某列为空 → 矛盾" --> E["回溯到上一个分支，换下一行"]
    E --> C
    D -- "全部覆盖" --> F["得到唯一解"]

由于题目保证解唯一，Algorithm X 找到的第一个完整覆盖就是答案，不需要枚举全部解。

代码

Python 版：

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#!/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-01 12:55
# update_at: 2026-10-01 12:55

import sys

N = 16  # 边长与符号个数：16×16 数独，每行/列/宫填 A~P 各一次
NCELL = N * N                    # 256 个格子
NCOL = 4 * NCELL                 # 1024 个约束列：格 / 行 / 列 / 宫 各 256 个
ROOT = NCOL                      # 总表头，0..NCOL-1 是列头
ROWCOLS = [None] * (NCELL * N)   # 每个候选行 (p, v) 覆盖的 4 个约束列

for p in range(NCELL):
    r, c = p >> 4, p & 15
    b = r // 4 * 4 + c // 4
    for v in range(N):
        ROWCOLS[p << 4 | v] = (p, (256 | r) << 8 | v if False else 256 + r * N + v,
                              512 + c * N + v, 768 + b * N + v)

# Dancing Links 的环形十字链表：0..NCOL-1 列头 + NCOL 根 + 每候选行 4 个节点
L: list[int] = []
R: list[int] = []
U: list[int] = []
D: list[int] = []
C: list[int] = []
S: list[int] = []
ROW: list[int] = []  # 节点 -> 候选行编号 p<<4|v，列头为 -1


def build() -> None:
    """把 4096 个候选行 × 4 约束列建成 DLX 矩阵，只建一次。"""
    del L[:], R[:], U[:], D[:], C[:], S[:], ROW[:]
    for i in range(NCOL + 1):  # 列头横向环 + 根
        L.append(i - 1)
        R.append(i + 1)
    L[0], R[ROOT] = ROOT, 0
    U.extend(range(NCOL + 1))
    D.extend(range(NCOL + 1))
    C.extend(range(NCOL + 1))
    S.extend([0] * (NCOL + 1))
    ROW.extend([-1] * (NCOL + 1))
    for row_id, cols in enumerate(ROWCOLS):
        first = len(C)
        for cid in cols:  # 竖向插到列底
            U.append(U[cid])
            D.append(cid)
            D[U[cid]] = len(C)
            U[cid] = len(C)
            C.append(cid)
            S[cid] += 1
            ROW.append(row_id)
        for k in range(4):  # 同一行的 4 个节点横向成环
            i = first + k
            L.append(first + (k - 1) % 4)
            R.append(first + (k + 1) % 4)


def cover(cid: int) -> None:
    """从列环中摘掉列头，并把该列每行从各自的其他列里删除。"""
    L[R[cid]] = L[cid]
    R[L[cid]] = R[cid]
    i = D[cid]
    while i != cid:
        j = R[i]
        while j != i:
            D[U[j]] = D[j]
            U[D[j]] = U[j]
            S[C[j]] -= 1
            j = R[j]
        i = D[i]


def uncover(cid: int) -> None:
    """cover 的逆操作，严格按相反顺序恢复链表。"""
    i = U[cid]
    while i != cid:
        j = L[i]
        while j != i:
            S[C[j]] += 1
            D[U[j]] = j
            U[D[j]] = j
            j = L[j]
        i = U[i]
    L[R[cid]] = cid
    R[L[cid]] = cid


def search(sol: list[int]) -> bool:
    """Knuth Algorithm X：挑剩余候选最少的列分支；列环空即完全覆盖。"""
    if R[ROOT] == ROOT:
        return True
    c, best = R[ROOT], R[ROOT]  # 最小列启发式：分支数最少
    s = S[c]
    while c != ROOT:
        if S[c] < s:
            s, best = S[c], c
        c = R[c]
    cover(best)
    i = D[best]
    while i != best:
        sol.append(ROW[i])
        j = R[i]
        while j != i:
            cover(C[j])
            j = R[j]
        if search(sol):
            return True
        j = L[i]
        while j != i:
            uncover(C[j])
            j = L[j]
        sol.pop()
        i = D[i]
    uncover(best)
    return False


def solve_puzzle(puzzle: str) -> str:
    """从建好的矩阵出发解一个谜面，返回 16 行文本。"""
    U[:] = base_U
    D[:] = base_D
    L[:] = base_L
    R[:] = base_R
    S[:] = base_S
    givens: list[tuple[int, int]] = []
    board = ["-"] * NCELL
    for p, ch in enumerate(puzzle):
        if ch not in "-.":  # 数据用 '-' 表示空格（题面写作 '.'）
            v = ord(ch) - 65
            givens.append((p, v))
            board[p] = ch
            for cid in ROWCOLS[p << 4 | v]:  # 给定行永久选中，不再恢复
                cover(cid)
    sol: list[int] = list(givens and [])
    sol = [p << 4 | v for p, v in givens]
    search(sol)
    for row_id in sol:
        p, v = row_id >> 4, row_id & 15
        board[p] = chr(65 + v)
    return "\n".join("".join(board[i:i + N]) for i in range(0, NCELL, N))


build()
base_U, base_D, base_L, base_R, base_S = U[:], D[:], L[:], R[:], S[:]


def solve() -> None:
    # 兼容两种写法：整行一个谜面、或每行 16 个字符逐行给出；end 终止符直接丢弃
    # 整篇输入要保留空格/换行并做整行/整 token 拼接，比 next() 顺序消费更自然
    raw = sys.stdin.read().split()
    body = "".join(t for t in raw if t != "end")
    out = [solve_puzzle(body[i:i + NCELL]) for i in range(0, len(body), NCELL)]
    print("\n\n".join(out))  # 谜面之间用空行分隔，与数据一致


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268/**
 * 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-06 17:02
 * update_at: 2026-10-06 17:02
 */

#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 16;          // 16×16 数独
const int NCELL = N * N;   // 256 个格子
const int NCOL = 4 * NCELL; // 1024 个约束列
const int ROOT = NCOL;     // 总表头
const int MAXNODE = NCOL + 1 + NCELL * N * 5; // 列头 + 根 + 4096 行 × 4 节点

// Dancing Links 十字链表
int L[MAXNODE];
int R[MAXNODE];
int U[MAXNODE];
int D[MAXNODE];
int C[MAXNODE];   // 节点所属列
int S[NCOL + 1];  // 列的节点数
int ROW[MAXNODE]; // 节点对应的候选行编号

int row_cols[NCELL * N][4]; // 每个候选行覆盖的 4 个约束列

// 列编号：0..255 cell(p), 256..511 row(r,v), 512..767 col(c,v), 768..1023 box(b,v)

int node_cnt; // 当前已用节点数

void init_cols() {
    // 横向环：列头 0..NCOL-1 + 根 ROOT
    for (int i = 0; i <= NCOL; ++i) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = i;
        D[i] = i;
        C[i] = i;
        S[i] = 0;
        ROW[i] = -1;
    }
    L[0] = ROOT;
    R[ROOT] = 0;
    node_cnt = NCOL + 1;
}

void add_row(int row_id, int cols[4]) {
    int first = node_cnt;
    for (int k = 0; k < 4; ++k) {
        int cid = cols[k];
        // 竖向插入到列尾
        U[node_cnt] = U[cid];
        D[node_cnt] = cid;
        D[U[cid]] = node_cnt;
        U[cid] = node_cnt;
        C[node_cnt] = cid;
        ROW[node_cnt] = row_id;
        S[cid]++;
        node_cnt++;
    }
    // 横向成环
    for (int k = 0; k < 4; ++k) {
        int i = first + k;
        L[i] = first + (k + 3) % 4;
        R[i] = first + (k + 1) % 4;
    }
}

void build() {
    init_cols();
    // 预计算每个候选行 (p, v) 的 4 个约束列
    for (int p = 0; p < NCELL; ++p) {
        int r = p >> 4;
        int c = p & 15;
        int b = (r / 4) * 4 + (c / 4);
        for (int v = 0; v < N; ++v) {
            int rid = p * N + v;
            row_cols[rid][0] = p;               // cell(p)
            row_cols[rid][1] = 256 + r * N + v; // row(r,v)
            row_cols[rid][2] = 512 + c * N + v; // col(c,v)
            row_cols[rid][3] = 768 + b * N + v; // box(b,v)
        }
    }
    // 建 4096 个候选行
    for (int rid = 0; rid < NCELL * N; ++rid) {
        add_row(rid, row_cols[rid]);
    }
}

void cover(int cid) {
    L[R[cid]] = L[cid];
    R[L[cid]] = R[cid];
    for (int i = D[cid]; i != cid; i = D[i]) {
        for (int j = R[i]; j != i; j = R[j]) {
            D[U[j]] = D[j];
            U[D[j]] = U[j];
            S[C[j]]--;
        }
    }
}

void uncover(int cid) {
    for (int i = U[cid]; i != cid; i = U[i]) {
        for (int j = L[i]; j != i; j = L[j]) {
            S[C[j]]++;
            D[U[j]] = j;
            U[D[j]] = j;
        }
    }
    L[R[cid]] = cid;
    R[L[cid]] = cid;
}

int sol[300]; // 选中的候选行
int sol_len;

bool search() {
    if (R[ROOT] == ROOT) {
        return true; // 全部覆盖
    }
    // 最小列启发式
    int c = R[ROOT];
    int best = c;
    int best_s = S[c];
    while (c != ROOT) {
        if (S[c] < best_s) {
            best_s = S[c];
            best = c;
        }
        c = R[c];
    }
    if (best_s == 0) {
        return false; // 矛盾
    }
    cover(best);
    for (int i = D[best]; i != best; i = D[i]) {
        sol[sol_len++] = ROW[i];
        for (int j = R[i]; j != i; j = R[j]) {
            cover(C[j]);
        }
        if (search()) {
            return true;
        }
        for (int j = L[i]; j != i; j = L[j]) {
            uncover(C[j]);
        }
        sol_len--;
    }
    uncover(best);
    return false;
}

// 备份数组，用于恢复初始矩阵
int base_L[MAXNODE];
int base_R[MAXNODE];
int base_U[MAXNODE];
int base_D[MAXNODE];
int base_S[NCOL + 1];

char board[NCELL];

void solve_puzzle(const string &puzzle, string &out) {
    // 恢复矩阵到初始状态
    for (int i = 0; i < node_cnt; ++i) {
        L[i] = base_L[i];
        R[i] = base_R[i];
        U[i] = base_U[i];
        D[i] = base_D[i];
    }
    for (int i = 0; i <= NCOL; ++i) {
        S[i] = base_S[i];
    }
    sol_len = 0;
    for (int p = 0; p < NCELL; ++p) {
        board[p] = '-';
    }
    // 处理给定格
    for (int p = 0; p < (int)puzzle.size() && p < NCELL; ++p) {
        char ch = puzzle[p];
        if (ch != '-' && ch != '.') {
            int v = ch - 'A';
            int rid = p * N + v;
            board[p] = ch;
            for (int k = 0; k < 4; ++k) {
                cover(row_cols[rid][k]);
            }
            sol[sol_len++] = rid;
        }
    }
    search();
    for (int i = 0; i < sol_len; ++i) {
        int rid = sol[i];
        int p = rid / N;
        int v = rid % N;
        board[p] = char('A' + v);
    }
    // 输出 16 行
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            out.push_back(board[i * N + j]);
        }
        if (i + 1 < N) {
            out.push_back('\n');
        }
    }
}

char buf[1000000];

int main() {
    build();
    // 备份初始矩阵
    for (int i = 0; i < node_cnt; ++i) {
        base_L[i] = L[i];
        base_R[i] = R[i];
        base_U[i] = U[i];
        base_D[i] = D[i];
    }
    for (int i = 0; i <= NCOL; ++i) {
        base_S[i] = S[i];
    }
    // 读入全部数据
    string all;
    while (fgets(buf, sizeof(buf), stdin)) {
        all += buf;
    }
    // 分词，去掉 end，拼接
    string body;
    int n = all.size();
    int i = 0;
    while (i < n) {
        // 跳过空白
        while (i < n && isspace((unsigned char)all[i])) {
            ++i;
        }
        if (i >= n) break;
        int j = i;
        while (j < n && !isspace((unsigned char)all[j])) {
            ++j;
        }
        string token = all.substr(i, j - i);
        if (token != "end") {
            body += token;
        }
        i = j;
    }
    vector<string> outputs;
    for (size_t pos = 0; pos + NCELL <= body.size(); pos += NCELL) {
        string out;
        solve_puzzle(body.substr(pos, NCELL), out);
        outputs.push_back(out);
    }
    for (size_t k = 0; k < outputs.size(); ++k) {
        if (k > 0) {
            printf("\n\n");
        }
        printf("%s", outputs[k].c_str());
    }
    printf("\n");
    return 0;
}

复杂度

时间：精确覆盖是 NP 完全问题，Algorithm X 没有多项式上界；但每条候选行只覆盖 4 列，删除/恢复代价极低，加上"最小列"启发式，实际效率远高于朴素 DFS——C++ 实现是本题的经典解法，Python 版在本题数据上每个谜面约 1.2s（见下文验证）。
空间：矩阵共 $256\times16=4096$ 行、每行 4 列，X/Y 存储为 $O(4\times4096)=O(16\text{K})$ 个条目，递归深度不超过 $256$ 。

图示解析

以一个 $4\times4$ 迷你数独说明建模方式（ $16\times16$ 完全同理，只是规模放大）：

	c0	c1	c2	c3
r0	`1`	`.`	`.`	`.`
r1	`.`	`.`	`2`	`.`
r2	`.`	`3`	`.`	`.`
r3	`.`	`.`	`.`	`4`

4 类约束列（迷你版共 $4\times4\times4=64$ 个）：

约束类型	例子	迷你版个数
格	`cell(0)`：格 (0,0) 恰填一个数	16
行	`row(1,2)`：第 1 行恰有一个 2	16
列	`col(2,3)`：第 2 列恰有一个 3	16
宫	`box(0,1)`：左上宫恰有一个 1	16

候选行 (格 5, 值 2)（格 (1,1) 填 2）覆盖：cell(5)、row(1,2)、col(1,2)、box(0,2)，恰好 4 列——这就是"每个约束各被满足一次"与"每格每值"的对偶关系。

初始时的给定格（如 (格 0, 值 1)）先 select，随即它的 4 条约束列被弹出，所有与之冲突的候选行（比如 (格 5, 值 1)，因为它会让 row(1,1) 重复）被顺带删除——一次给定直接传播掉成片的候选，这是 Algorithm X 开局就快的原因。

搜索时每一步都挑"当前剩余候选行最少的约束列"：

待覆盖列	剩余候选	是否分支
`cell(5)`	3	是（3 选 1）
`row(1,4)`	1	否（唯一候选，直接选）
`col(3,4)`	0	矛盾，回溯

只有第一类（候选 ≥2）才真正分叉，后两类分别是"免费传播"和"免费剪枝"。

总结

把数独的格/行/列/宫约束翻译成 4 类精确覆盖列、每个"格+值"候选覆盖 4 列，是 Dancing Links 解数独的标准建模。
Algorithm X 的两个核心动作——select 删列删冲突行、按最小列分支——分别对应约束传播与最少候选优先，共同把朴素 DFS 的无效分支削掉。
给定符号在建模阶段就永久 select，谜面的初盘信息全部转化为矩阵缩减，搜索只处理真正的未知部分。
Python 实现的常数较大，但本题本地数据（64 个谜面）约 81s 完成，输出与标准答案完全一致；若在严格 1s 限时的 OJ 上提交，需要 C++ 版的 Dancing Links。

验证记录

用本仓库数据仓的真实测试数据（data/a.in，64 个 $16\times16$ 谜面，2048 行答案）实测：

text

1
2
3[1/1] data/a.in
  result: PASS (81.115s, peak=19.3MB)
总结：PASS=1, FAIL=0, NO_ANSWER=0

本地限时按 python-oj-short 的约定放宽为 120s（OJ 原限时 1000ms），Python 侧存在 TLE 风险，输出正确性已全部通过。

「Sudoku」 数独

目录

形式化题目

正解

思路

代码

复杂度

图示解析

总结

验证记录