靶形数独

GitHub跳转原题关系图返回列表

把行、列、宫的已用数字压成三个位掩码，DFS 时用 MRV 先填候选最少的空格，再用「剩余空格各填候选里最大数字」的上界剪枝，求带权数独的最大总分。

OJ: roj

题目 ID: 3076

难度:提高

标签:搜索深度优先搜索DFS剪枝位运算优化

创建: 2026-10-01 14:48

更新: 2026-10-07 13:50

相似题目

roj 3575[NOIP2009-提高] 靶形数独同一张盘面：先求任意一个合法填法，本题再升级为在解集合上最大化靶形加权总分

形式化题目

给定一个 $9 \times 9$ 的盘面，每个格子要么已经填好 $1 \sim 9$ 中的一个数字，要么留空（输入中用 0 表示）。求一个合法填法，即把每个空格填上 $1 \sim 9$ 中的一个数，使得

每一行、每一列、每个 $3 \times 3$ 宫内，数字 $1 \sim 9$ 各出现恰好一次；

并且最大化总分

\sum_{\text{盘面中每个格子 } g} (\text{格 } g \text{ 上的数字}) \times w_g

其中分值 $w_g$ 只与位置有关：以中心格为原点，按切比雪夫距离 $d = \max(|r-4|, |c-4|)$ 分层， $d = 0,1,2,3,4$ 分别给 $10,9,8,7,6$ 分。若不存在合法填法，输出 $-1$ 。

下面的表把这段文字变成具体数字，单元格里就是该格的分值系数（行、列从 1 编号）。

行\列	1	2	3	4	5	6	7	8	9
1	6	6	6	6	6	6	6	6	6
2	6	7	7	7	7	7	7	7	6
3	6	7	8	8	8	8	8	7	6
4	6	7	8	9	9	9	8	7	6
5	6	7	8	9	10	9	8	7	6
6	6	7	8	9	9	9	8	7	6
7	6	7	8	8	8	8	8	7	6
8	6	7	7	7	7	7	7	7	6
9	6	6	6	6	6	6	6	6	6

观察重点：分值只按「离中心的圈数」分层，四个角都是 6 分、正中一格是 10 分，所以它是一个与搜索过程无关的常量表——这一点是后面能把题目简化成纯搜索优化的前提。

题面样例对应的盘面如下（· 表示空格），一共 30 个已知数字、51 个空格：

行\列	1	2	3	4	5	6	7	8	9
1	7	·	·	9	·	·	·	·	1
2	1	·	·	·	·	5	9	·	·
3	·	·	·	2	·	·	·	8	·
4	·	·	5	·	2	·	·	·	3
5	·	·	·	·	·	·	6	4	8
6	4	1	3	·	·	·	·	·	·
7	·	·	7	·	·	2	·	9	·
8	2	·	1	·	6	·	8	·	4
9	·	8	·	5	·	4	·	1	2

该盘面的最高总分是 $2829$ ，即题面的输出样例；把它与上面的分值表逐格相乘相加，就能核对「总分 = 数字 × 分值」这一定义。

正解

思路

朴素做法及其瓶颈。 最直接的想法是按行优先遍历 81 个格子，每个空格逐个尝试 $1 \sim 9$ ，填满后检查是否合法、并更新最大总分。空格最多有 $9^m$ 种组合（ $m$ 为空格数，极端情况 $m=57$ ），显然枚举不完。但数独的约束收缩极快：沿着行优先顺序推进时，一个空格能填的数字通常只剩两三个，而且大量分支在刚放上数字时就已经和同行、同列、同宫冲突了。所以正确的方向不是换算法，而是把搜索树上无用的分支剪掉，让同样的回溯搜索尽快跑完。

第一步：把分数拆成常量 + 变量。 已知数字带来的分数是固定的，可以一开始就累加成 gain；题目于是变成「最大化空格上的贡献」，最后输出 gain + 最大值。这一步还顺便解决了无解的歧义：把答案初值设为 $-1$ （而不是 0），只有走到「所有空格都填完」的叶子才更新它，所以搜索一趟都没走通时输出就是 $-1$ 。

第二步：用位掩码维护三类约束。 搜索过程中要反复问「数字 $d$ 能不能放进这一格」。给每一行、每一列、每一宫各开一个整数当集合，第 $d$ 位为 1 表示数字 $d$ 已经用过，并取

python

1FULL = 0b1111111110  # 数字 1..9 各占一位，第 0 位空着

让第 $d$ 位天然对应数字 $d$ ，不必再写 d - 1。这样一格的候选数字集合就是

C = \texttt{FULL} \;\&\; \sim(R_r \mid C_c \mid B_b)

一次取反、两次按位或、一次按位与，全是常数级操作。判合法、取候选、撤销（按位异或两次复原）都变成了整数运算。

第三步：MRV——候选最少的空格先决策。 行优先的顺序有个坏毛病：某个空格只剩唯一候选、或者干脆已经没有候选，这个「马上就要失败」的位置可能排在很后面，导致前面先展开了整片无意义的子树。于是每一层都重新算出一批候选集合，然后挑候选个数最少（bit_count() 最小）的那个空格来决策。这样「快失败」的格子会被提到搜索树上层，候选为 0 的格子下一层立刻回溯消失，整棵搜索树的宽度和深度同时下降。仍以题面样例为例，按 MRV 选出的前五个格子和当时的候选是：

步	选中的格子 (行,列)	候选数字	当时剩余空格数
1	(4,8)	7	51
2	(4,7)	1	50
3	(5,1)	9	49
4	(4,2)	6	48
5	(4,1)	8	47

可以看到第 4 行是「候选唯一」密集的地方，而它在行优先顺序里排在很后面； MRV 把这一串唯一候选直接提到最前面，一放下去大片格子的候选也随之收窄。

第四步：上界剪枝（分支定界）。 维护「剩余空格的分值之和」rest（每递归一层就减掉当前格的分值）。最松的界是「剩余空格全填 9」，但如果每个空格都填它自己候选里的最大数字，能拿到一个紧得多的上界：

\texttt{score} + \sum_{j \in \text{alive}} \big(\max C_j\big) \cdot w_j \;\leqslant\; \texttt{best} \;\Longrightarrow\; \text{剪掉这条分支}

$\max C_j$ 在代码里就是 cands[j].bit_length() - 1。这个界对每个空格都成立，所以剪掉的每条分支里都不存在能超过 best 的完整解，剪枝是安全的。

第五步：先试大数字。 内层枚举候选数字时从大到小（bit = 1 << bits.bit_length() - 1）。先试大数字能让 best 更快被抬高，从而让上界剪枝更早生效；而高分格上的大数字本来就更可能出现在最优解里，搜索也更容易命中。实现上，「尝试下一个数字」表现为从候选集合里删掉一位（bits ^= bit），而三个掩码的放置与撤销成对地用 |= 和 ^=，同一位置异或两次就复原，不必保存副本。

把上面五步合起来，搜索框架是：

text

1
2
3
4
5
6
7
8
9dfs(score, rest, alive):
    alive 为空            -> best = max(best, score)，得到完整解
    score + 上界 <= best  -> 剪枝返回
    cands = 每个空格的候选集合
    g = alive 中候选最少的那个空格          (MRV)
    for d = 候选里的最大数字 downto 最小数字:   (大数字优先)
        在 g 上放 d，更新行/列/宫的掩码
        dfs(score + d * w[g], rest - w[g], alive - {g})
        撤销 d

搜索时只搬「空格编号」，每层的 行/列/宫/分值 都从预先建好的四张一维表（row_of、col_of、box_of、w_of）里查，避免在递归里反复做整除取模。

无解与边界。 best 初值为 $-1$ ，只有到达叶子才更新，所以无解自然输出 $-1$ ；盘面本来就填满时，叶子判定在函数入口命中，输出 gain；某个空格候选为空时它会被 MRV 优先选中，内层循环一次都不进，立刻回溯。

代码

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#!/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 14:48
# update_at: 2026-10-01 14:58

import sys

FULL = 0b1111111110  # 数字 1..9 各占一位，第 0 位空着，方便用位运算直接取候选
RING = (10, 9, 8, 7, 6)  # 按到中心的切比雪夫距离分层：中心 10 分，最外圈 6 分


def solve() -> None:
    weight = [RING[max(abs(i // 9 - 4), abs(i % 9 - 4))] for i in range(81)]  # 81 格的分值
    values = list(map(int, sys.stdin.buffer.read().split()))

    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9  # 第 1..9 位分别是数字 1..9 是否已用
    gain = 0                                       # 已知数字贡献的固定分数
    blanks: list[int] = []                         # 所有空格的一维下标 r*9+c
    for i, value in enumerate(values):
        if value == 0:
            blanks.append(i)
            continue
        bit = 1 << value
        r, c = divmod(i, 9)
        rows[r] |= bit
        cols[c] |= bit
        boxes[r // 3 * 3 + c // 3] |= bit
        gain += value * weight[i]

    # 空格的位置信息按“空格编号”建表，搜索里只搬编号，不再反复做整除取模
    row_of = [i // 9 for i in blanks]
    col_of = [i % 9 for i in blanks]
    box_of = [i // 27 * 3 + i % 9 // 3 for i in blanks]
    w_of = [weight[i] for i in blanks]
    best = -1

    def dfs(score: int, rest: int, alive: tuple[int, ...]) -> None:
        """在未填的空格 alive 上继续搜；score 是当前总分，rest 是这些空格的分值之和。"""
        nonlocal best
        if not alive:                        # 每个空格都填上了，得到完整解
            best = max(best, score)
            return
        cands = [FULL & ~(rows[row_of[i]] | cols[col_of[i]] | boxes[box_of[i]]) for i in alive]
        # 上界：每个空格都填自己候选里的最大数字（bit_length()-1），这样都追不上当前最优就剪掉
        cap = sum((c.bit_length() - 1) * w_of[j] for c, j in zip(cands, alive))
        if score + cap <= best:
            return
        k = min(range(len(alive)), key=lambda t: cands[t].bit_count())  # MRV：候选最少的格子先决策
        bits, pos = cands[k], alive[k]
        rest -= w_of[pos]
        alive = alive[:k] + alive[k + 1:]
        while bits:
            bit = 1 << bits.bit_length() - 1  # 从最大的数字开始试：先拿到高分，界更紧
            bits ^= bit
            rows[row_of[pos]] |= bit
            cols[col_of[pos]] |= bit
            boxes[box_of[pos]] |= bit
            dfs(score + (bit.bit_length() - 1) * w_of[pos], rest, alive)
            rows[row_of[pos]] ^= bit         # 回溯：撤销这个数字
            cols[col_of[pos]] ^= bit
            boxes[box_of[pos]] ^= bit

    dfs(gain, sum(w_of), tuple(range(len(blanks))))
    print(best)


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/**
 * 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:40
 * update_at: 2026-10-06 17:40
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int FULL = 0b1111111110; // 数字 1..9 各占一位，第 0 位空着

int weight[81];          // 每格的分值
int row_of[81];          // 空格编号 -> 行
int col_of[81];          // 空格编号 -> 列
int box_of[81];          // 空格编号 -> 宫
int w_of[81];            // 空格编号 -> 分值
int rows[9], cols[9], boxes[9]; // 行/列/宫的已用数字位掩码
int blanks[81];          // 空格的一维下标
int blank_cnt;           // 空格数量
ll best;                 // 当前最优总分
ll gain;                 // 已知数字的固定分数

// 上界：每个空格都填自己候选里的最大数字，若仍不超 best 则剪枝
inline ll upper_bound(int *alive, int alive_cnt) {
    ll cap = 0;
    for (int i = 0; i < alive_cnt; ++i) {
        int pos = alive[i];
        int cands = FULL & ~(rows[row_of[pos]] | cols[col_of[pos]] | boxes[box_of[pos]]);
        if (cands == 0) return 0; // 无候选，这条分支已死
        int max_d = 31 - __builtin_clz(cands); // 最高位的 1 对应的数字
        cap += (ll)max_d * w_of[pos];
    }
    return cap;
}

void dfs(ll score, ll rest, int *alive, int alive_cnt) {
    if (alive_cnt == 0) { // 所有空格填完，得到完整解
        if (score > best) best = score;
        return;
    }
    // 上界剪枝
    ll cap = upper_bound(alive, alive_cnt);
    if (score + cap <= best) return;

    // MRV：找候选最少的空格
    int min_cands = 10;
    int chosen_idx = -1;
    int chosen_cands = 0;
    for (int i = 0; i < alive_cnt; ++i) {
        int pos = alive[i];
        int cands = FULL & ~(rows[row_of[pos]] | cols[col_of[pos]] | boxes[box_of[pos]]);
        int cnt = __builtin_popcount(cands);
        if (cnt < min_cands) {
            min_cands = cnt;
            chosen_idx = i;
            chosen_cands = cands;
            if (cnt == 1) break; // 不可能更少
        }
    }

    int pos = alive[chosen_idx];
    // 把选中的空格从 alive 中移除（与最后一个交换）
    alive[chosen_idx] = alive[alive_cnt - 1];

    // 从大到小枚举候选数字
    while (chosen_cands) {
        // 取当前候选集合里的最大数字（最高位）
        int d = 31 - __builtin_clz(chosen_cands);
        int use_bit = 1 << d;
        chosen_cands ^= use_bit;

        rows[row_of[pos]] |= use_bit;
        cols[col_of[pos]] |= use_bit;
        boxes[box_of[pos]] |= use_bit;

        dfs(score + (ll)d * w_of[pos], rest - w_of[pos], alive, alive_cnt - 1);

        rows[row_of[pos]] ^= use_bit;
        cols[col_of[pos]] ^= use_bit;
        boxes[box_of[pos]] ^= use_bit;
    }

    // 恢复 alive 数组
    alive[chosen_idx] = pos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预计算分值表：按到中心的切比雪夫距离分层
    for (int i = 0; i < 81; ++i) {
        int r = i / 9, c = i % 9;
        int d = max(abs(r - 4), abs(c - 4));
        weight[i] = 10 - d; // d=0->10, d=1->9, ..., d=4->6
    }

    gain = 0;
    blank_cnt = 0;
    memset(rows, 0, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    memset(boxes, 0, sizeof(boxes));

    for (int i = 0; i < 81; ++i) {
        int x;
        cin >> x;
        if (x == 0) {
            blanks[blank_cnt++] = i;
        } else {
            int bit = 1 << x;
            int r = i / 9, c = i % 9;
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[r / 3 * 3 + c / 3] |= bit;
            gain += (ll)x * weight[i];
        }
    }

    // 按空格编号建表，搜索时只搬编号
    for (int i = 0; i < blank_cnt; ++i) {
        int p = blanks[i];
        row_of[i] = p / 9;
        col_of[i] = p % 9;
        box_of[i] = p / 27 * 3 + p % 9 / 3;
        w_of[i] = weight[p];
    }

    best = -1;
    int alive[81];
    for (int i = 0; i < blank_cnt; ++i) alive[i] = i;

    dfs(gain, 0, alive, blank_cnt);

    cout << best << "\n";
    return 0;
}

复杂度

每个搜索节点： $O(m)$ （算一遍候选、求和上界、取 MRV 最小）， $m$ 为空格数（ $\leqslant 57$ ）。
节点数：无剪枝时上界为 $O(9^m)$ ；本题数据保证已知数字不少于 24 个（ $m \leqslant 57$ ），在上述三项剪枝下实测远小于该上界。
空间 $O(m)$ ：递归深度 $m$ ，加上四张长度为 $m$ 的预计算表，没有任何大数组。
依据数据范围「非 0 数字不少于 24 个」，这是本题正解（回溯 + 位运算 + 剪枝）的标准复杂度； Python 常数较大，在 1000ms 限制下最慢测例本地约 2.5s，属于规则允许的 Python 超时范围，算法本身与正解同阶。

总结

分值与搜索无关，先做成常量表，并把已知数字的分数累加为 gain；答案初值取 $-1$ 天然表达「无解」。
行、列、宫各用一个整数位掩码，FULL = 0b1111111110 让第 $d$ 位就是数字 $d$ ，候选集合写成一次 &~(|)，放置与撤销用 |= / ^=。
三项剪枝决定能否跑完：MRV 把候选最少的空格提到上层、候选最大数字上界截断追不上 best 的分支、大数字优先让 best 更快抬高。

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。

但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在9×9的大九宫格中有9个3×3的小九宫格（用粗黑色线隔开的）。

在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。

每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。

但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高（如下图所示）。

上图具体的分值分布是：最里面一格（黄色区域）为10分，黄色区域外面的一圈（红色区域）每个格子为9分，再外面一圈（蓝色区域）每个格子为8分，蓝色区域外面一圈（棕色区域）每个格子为7分，最外面一圈（白色区域）每个格子为6 分，如上图所示。

比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。

而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。

如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。

游戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

输入格式

输入一共包含9行。

每行 9 个整数（每个数都在 0—9 的范围内），表示一个尚未填满的数独方格，未填的空格用“0”表示。

每两个数字之间用一个空格隔开。

输出格式

输出可以得到的靶形数独的最高分数。

如果这个数独无解，则输出整数-1。

数据范围

40%的数据，数独中非 0 数的个数不少于 30。

80%的数据，数独中非 0 数的个数不少于 26。

100%的数据，数独中非 0 数的个数不少于 24。

输入样例：

text

1
2
3
4
5
6
7
8
97 0 0 9 0 0 0 0 1 
1 0 0 0 0 5 9 0 0 
0 0 0 2 0 0 0 8 0 
0 0 5 0 2 0 0 0 3 
0 0 0 0 0 0 6 4 8 
4 1 3 0 0 0 0 0 0 
0 0 7 0 0 2 0 9 0 
2 0 1 0 6 0 8 0 4 
0 8 0 5 0 4 0 1 2

输出样例：

text

来源

《算法竞赛进阶指南》
acwing 可能含有视频讲解

行\列	1	2	3	4	5	6	7	8	9
1	6	6	6	6	6	6	6	6	6
2	6	7	7	7	7	7	7	7	6
3	6	7	8	8	8	8	8	7	6
4	6	7	8	9	9	9	8	7	6
5	6	7	8	9	10	9	8	7	6
6	6	7	8	9	9	9	8	7	6
7	6	7	8	8	8	8	8	7	6
8	6	7	7	7	7	7	7	7	6
9	6	6	6	6	6	6	6	6	6

行\列	1	2	3	4	5	6	7	8	9
1	7	·	·	9	·	·	·	·	1
2	1	·	·	·	·	5	9	·	·
3	·	·	·	2	·	·	·	8	·
4	·	·	5	·	2	·	·	·	3
5	·	·	·	·	·	·	6	4	8
6	4	1	3	·	·	·	·	·	·
7	·	·	7	·	·	2	·	9	·
8	2	·	1	·	6	·	8	·	4
9	·	8	·	5	·	4	·	1	2

行\列	1	2	3	4	5	6	7	8	9
1	6	6	6	6	6	6	6	6	6
2	6	7	7	7	7	7	7	7	6
3	6	7	8	8	8	8	8	7	6
4	6	7	8	9	9	9	8	7	6
5	6	7	8	9	10	9	8	7	6
6	6	7	8	9	9	9	8	7	6
7	6	7	8	8	8	8	8	7	6
8	6	7	7	7	7	7	7	7	6
9	6	6	6	6	6	6	6	6	6

行\列	1	2	3	4	5	6	7	8	9
1	7	·	·	9	·	·	·	·	1
2	1	·	·	·	·	5	9	·	·
3	·	·	·	2	·	·	·	8	·
4	·	·	5	·	2	·	·	·	3
5	·	·	·	·	·	·	6	4	8
6	4	1	3	·	·	·	·	·	·
7	·	·	7	·	·	2	·	9	·
8	2	·	1	·	6	·	8	·	4
9	·	8	·	5	·	4	·	1	2

靶形数独

目录

形式化题目

正解

思路

代码

复杂度

总结

行\列	1	2	3	4	5	6	7	8	9
1	6	6	6	6	6	6	6	6	6
2	6	7	7	7	7	7	7	7	6
3	6	7	8	8	8	8	8	7	6
4	6	7	8	9	9	9	8	7	6
5	6	7	8	9	10	9	8	7	6
6	6	7	8	9	9	9	8	7	6
7	6	7	8	8	8	8	8	7	6
8	6	7	7	7	7	7	7	7	6
9	6	6	6	6	6	6	6	6	6

行\列	1	2	3	4	5	6	7	8	9
1	7	·	·	9	·	·	·	·	1
2	1	·	·	·	·	5	9	·	·
3	·	·	·	2	·	·	·	8	·
4	·	·	5	·	2	·	·	·	3
5	·	·	·	·	·	·	6	4	8
6	4	1	3	·	·	·	·	·	·
7	·	·	7	·	·	2	·	9	·
8	2	·	1	·	6	·	8	·	4
9	·	8	·	5	·	4	·	1	2