「一本通 1.3 练习 4」靶形数独

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

基于位运算状态压缩与最少剩余候选数（MRV）启发式剪枝的 DFS 回溯搜索，求解靶形数独最高得分。

OJ: roj

题目 ID: 1447

难度:提高

标签:DFS剪枝位运算启发式搜索

创建: 2026-03-31 01:00

更新: 2026-10-07 11:01

形式化题目

给定一个 $9 \times 9$ 的网格，部分格子填有 $1 \sim 9$ 的整数，未填的空格表示为 $0$ 。

要求在空格中填入 $1 \sim 9$ 的整数，使其满足标准数独约束：

每行、每列均恰好包含 $1 \sim 9$ 各一次且不重复；
划分出的 $9$ 个 $3 \times 3$ 的小九宫格中，每个宫内均恰好包含 $1 \sim 9$ 各一次且不重复。

每个格子 $(r, c)$ （ $0 \leqslant r, c \leqslant 8$ ）具有靶形权重分值：

W(r, c) = 6 + \min(r, 8-r, c, 8-c)

完成数独后的总分数为所有格子的数字与其权重乘积之和：

\text{Score} = \sum_{r=0}^8 \sum_{c=0}^8 \text{grid}[r][c] \times W(r, c)

目标是求出所有合法填法中所能获得的最高总分数。若该数独无合法填法，则返回 $-1$ 。

正解

思路

1. 靶形权重分布

每个格子 $(r, c)$ 的分值仅取决于其距离四条边界的最小曼哈顿距。中心格子分值最高（ $10$ 分），最外圈格子分值最低（ $6$ 分）：

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

由此可知权重计算可以直接用闭式表达：W(r, c) = 6 + min(r, 8 - r, c, 8 - c)。

2. 位运算状态压缩

标准数独的行、列、宫中数字 $1 \sim 9$ 各出现一次。我们分别用二进制第 $1 \sim 9$ 位表示数字是否被使用：

用数组 row_mask[r] 记录第 $r$ 行已填数字；
用数组 col_mask[c] 记录第 $c$ 列已填数字；
用数组 box_mask[b] 记录第 $b$ 个九宫格（ $b = \lfloor r/3 \rfloor \times 3 + \lfloor c/3 \rfloor$ ）已填数字。

对于未填空格 $(r, c)$ ，其能够填入的数字集合掩码为：

\text{avail} = \text{ALL\_DIGITS} \ \& \ \sim(\text{row\_mask}[r] \mid \text{col\_mask}[c] \mid \text{box\_mask}[b])

其中

\text{ALL\_DIGITS} = \sum_{i=1}^9 2^i = \text{0x3FE}

。可用候选数的个数即为

\text{avail}

的置位个数（avail.bit_count()）。

3. 最少剩余候选数原则（MRV）与可行性剪枝

如果按照固定的由左至右、由上至下的顺序枚举空格，前期可能遇到候选数多达 $8 \sim 9$ 个的格子，导致搜索树早期分支急剧膨胀。

核心优化是引入最少剩余候选数原则（Minimum Remaining Values, MRV）：

每一层递归搜索时，在所有尚未填入的空格中，动态计算每个空格的候选数个数；
选取当前候选数最少的格子进行展开：
- 若发现某个空格候选数个数为 $0$ ，说明当前分支必定无合法解，立即回溯剪枝；
- 若候选数个数为 $1$ （唯一候选数），则当前格子只有 $1$ 个确定分支，直接顺推，几乎不产生额外回溯树分支。
枚举候选数字时，利用 lsb = mask & -mask 与 lsb.bit_length() - 1 高效取出各个可选数字，更新掩码与得分后递归，回溯时复原状态。

flowchart TD
    A[进入 DFS 当前状态] --> B{是否所有空格已填满?}
    B -- 是 --> C[用当前得分更新 max_score 并返回]
    B -- 否 --> D[遍历未填空格, 统计各格可选数字集合]
    D --> E{是否存在候选数为空的格子?}
    E -- 是 --> F[剪枝: 立即回溯]
    E -- 否 --> G[选出候选数最少的格子 (r, c)]
    G --> H[枚举 (r, c) 的各候选数字]
    H --> I[更新状态与得分, 递归深入]
    I --> J[恢复状态, 回溯]

代码

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#!/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-03-31 01:00
# update_at: 2026-03-31 01:00

import sys

ALL_DIGITS = 0x3FE  # 1~9 位掩码：1 << 1 到 1 << 9


def get_weight(r: int, c: int) -> int:
    """计算第 r 行第 c 列格子的靶形分值权重（6 到 10 分）。"""
    return 6 + min(r, 8 - r, c, 8 - c)


def box_id(r: int, c: int) -> int:
    """计算第 r 行第 c 列所在的 3x3 小九宫格编号（0 到 8）。"""
    return (r // 3) * 3 + (c // 3)


def search_max_score(grid: list[list[int]]) -> int:
    """回溯搜索数独的所有合法填法，返回最大加权得分；无解返回 -1。"""
    row_mask = [0] * 9  # 每行已填数字集合的位掩码
    col_mask = [0] * 9  # 每列已填数字集合的位掩码
    box_mask = [0] * 9  # 每宫已填数字集合的位掩码

    initial_score = 0
    empties: list[tuple[int, int]] = []

    for r in range(9):
        for c in range(9):
            v = grid[r][c]
            if v:
                b = box_id(r, c)
                row_mask[r] |= 1 << v
                col_mask[c] |= 1 << v
                box_mask[b] |= 1 << v
                initial_score += v * get_weight(r, c)
            else:
                empties.append((r, c))

    max_score = -1

    def dfs(score: int) -> None:
        nonlocal max_score
        best_r, best_c = -1, -1
        min_choices = 10
        best_mask = 0

        # 最少剩余候选数原则（MRV）挑选分支最少的空格
        for r, c in empties:
            if grid[r][c] == 0:
                avail = ALL_DIGITS & ~(row_mask[r] | col_mask[c] | box_mask[box_id(r, c)])
                cnt = avail.bit_count()
                if cnt == 0:  # 存在无解空格，剪枝
                    return
                if cnt < min_choices:
                    min_choices = cnt
                    best_r, best_c = r, c
                    best_mask = avail
                    if cnt == 1:
                        break

        if min_choices == 10:  # 所有空格均已填满
            if score > max_score:
                max_score = score
            return

        r, c = best_r, best_c
        b = box_id(r, c)
        w = get_weight(r, c)
        mask = best_mask

        # 逆序从 9 到 1 尝试（或按位提取）：lsb 提取并回溯
        while mask:
            lsb = mask & -mask
            d = lsb.bit_length() - 1
            mask ^= lsb

            grid[r][c] = d
            row_mask[r] |= lsb
            col_mask[c] |= lsb
            box_mask[b] |= lsb

            dfs(score + d * w)

            grid[r][c] = 0
            row_mask[r] ^= lsb
            col_mask[c] ^= lsb
            box_mask[b] ^= lsb

    dfs(initial_score)
    return max_score


def solve() -> None:
    lines = [line.strip() for line in sys.stdin if line.strip()]
    if not lines:
        return
    grid = [list(map(int, line.split())) for line in lines]
    ans = search_max_score(grid)
    print(ans)


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/**
 * 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-05 02:16
 * update_at: 2026-10-05 02:16
 */

#include <cstdio>

typedef long long ll;

const int ALL_DIGITS = 0x3FE; // 二进制第 1~9 位表示数字 1~9 可用

// 全局数据
int grid[9][9];       // 当前棋盘，0 表示未填
int row_mask[9];      // row_mask[r]：第 r 行已填数字的位掩码
int col_mask[9];      // col_mask[c]：第 c 列已填数字的位掩码
int box_mask[9];      // box_mask[b]：第 b 宫已填数字的位掩码
int emp_r[81];        // 空格的行号列表
int emp_c[81];        // 空格的列号列表
int emp_cnt = 0;      // 空格总数
int filled_cnt = 0;   // 已填的空格数
ll max_score = -1;    // 当前搜到的最高得分，初始 -1 表示无解

// 计算第 r 行第 c 列的靶形权重（6~10 分）
inline int get_weight(int r, int c) {
    int t = r;
    if (8 - r < t) t = 8 - r;
    if (c < t) t = c;
    if (8 - c < t) t = 8 - c;
    return 6 + t;
}

// 统计掩码中置位个数
inline int bit_count(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;
        cnt++;
    }
    return cnt;
}

// 取出掩码最低位的 1（即最小候选数字对应的位）
inline int lowbit(int x) {
    return x & -x;
}

// MRV 搜索：每层在所有空格中选候选数最少的格子展开
// score：当前已确定的得分；无解时保持 max_score = -1
void dfs(ll score) {
    // 候选数最少的空格
    int best_i = -1;
    int min_choices = 10;
    int best_mask = 0;

    // 遍历所有空格，找候选数最少的那个
    for (int i = 0; i < emp_cnt; i++) {
        if (grid[emp_r[i]][emp_c[i]] != 0) continue; // 已填的空格跳过
        int r = emp_r[i];
        int c = emp_c[i];
        int b = (r / 3) * 3 + c / 3;
        // 可填数字集合 = 全集 去掉 行、列、宫已用数字
        int avail = ALL_DIGITS & ~(row_mask[r] | col_mask[c] | box_mask[b]);
        int cnt = bit_count(avail);
        if (cnt == 0) return;      // 有格子无数可填，当前分支必无解，剪枝
        if (cnt < min_choices) {   // MRV：挑分支最少的空格
            min_choices = cnt;
            best_i = i;
            best_mask = avail;
            if (cnt == 1) break;   // 唯一候选数，不用再找了
        }
    }

    // 没有空格可填：得到一个完整解，更新最高分
    if (best_i == -1) {
        if (score > max_score) max_score = score;
        return;
    }

    int r = emp_r[best_i];
    int c = emp_c[best_i];
    int b = (r / 3) * 3 + c / 3;
    int w = get_weight(r, c);

    // 依次尝试该格子的每个候选数字，回溯复原
    int mask = best_mask;
    while (mask) {
        int lsb = lowbit(mask);
        mask ^= lsb;
        int d = 0;
        for (int k = lsb; k > 1; k >>= 1) d++; // lsb 对应的数字

        grid[r][c] = d;
        row_mask[r] |= lsb;
        col_mask[c] |= lsb;
        box_mask[b] |= lsb;

        dfs(score + (ll)d * w);

        grid[r][c] = 0;
        row_mask[r] ^= lsb;
        col_mask[c] ^= lsb;
        box_mask[b] ^= lsb;
    }
}

int main() {
    // 读入数独，初始化掩码、得分和空格列表
    ll init_score = 0;
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            int v;
            scanf("%d", &v);
            grid[r][c] = v;
            int b = (r / 3) * 3 + c / 3;
            if (v != 0) {
                int bit = 1 << v;
                // 同一行、列、宫出现重复数字，直接无解
                if (row_mask[r] & bit || col_mask[c] & bit || box_mask[b] & bit) {
                    printf("-1\n");
                    return 0;
                }
                row_mask[r] |= bit;
                col_mask[c] |= bit;
                box_mask[b] |= bit;
                init_score += (ll)v * get_weight(r, c);
            } else {
                emp_r[emp_cnt] = r;
                emp_c[emp_cnt] = c;
                emp_cnt++;
            }
        }
    }

    dfs(init_score);
    printf("%lld\n", max_score);
    return 0;
}

复杂度

时间复杂度：最坏情况下数独求解为指数级复杂度，但通过位运算与 MRV 启发式剪枝后，合法状态空间被极大压缩，剪枝率极高，绝大多数数独分支都在极浅层被裁减。全部 20 组官方评测数据在单用例 1.5s 甚至数十毫秒内即可求解完毕。
空间复杂度： $\mathcal{O}(1)$ 。棋盘大小固定为 $9 \times 9$ ，掩码状态仅需常数级别的整型数组，递归调用栈深度至多为未填空格数 $m \leqslant 57$ 层，内存消耗小于 20MB。

总结

靶形数独是一道经典的带权精确覆盖搜索问题。相比普通数独只求任意一组解，本题需要遍历所有合法填法以求最大分值。解决本题的关键在于：

状态表达：用位运算将数独三个维度的合法性检查与候选数提取压缩到常数级；
搜索顺序（MRV）：每次动态挑选候选数最少的空格填数，把确定性最高的分支往前放，提前暴露矛盾，从而将搜索树的大部分无效子树剪去。

【题目描述】

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游戏规定，将以总分数的高低决出胜负。

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

【输入】

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

【输出】

共1 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。

【输入样例】

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

【提示】

【输入输出样例 2】

输入：

text

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

输出：

text

【数据范围】

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

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

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

【来源】

一本通在线评测

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

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