[NOIP2009-提高] 靶形数独

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

行/列/宫三个 9 位掩码维护候选，DFS 每层选候选最少的空格（MRV），并用「剩余格都取最大候选数字」的逐层真实上界剪枝，遍历解集合取加权总分最大值。

OJ: roj

题目 ID: 3575

难度:提高+/省选-

标签:搜索DFS回溯剪枝位运算数独

创建: 2026-10-02 08:26

更新: 2026-10-10 11:30

前置题目
leetcodecn n-queensN 皇后B 的 DFS 骨架直接沿用 A 教的「用标记数组实时记录已占用约束、放置前检查、递归后恢复」这一步：把 A 的 col/diag1/diag2 换成行/列/宫三个位掩码，放置 |= 、撤销 ^=，只是在其上叠加 MRV 选格与逐层真实上界分支定界来最大化靶形总分。
相似题目
roj 3076靶形数独同一张盘面：先求任意一个合法填法，本题再升级为在解集合上最大化靶形加权总分

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定一个 9×99 \times 9 的盘面，每个格子是 0∼90 \sim 9 的整数，0 表示空格。要把空格填上 1∼91 \sim 9，使得每一行、每一列、每个 3×33 \times 3 宫内 1∼91 \sim 9 各出现恰好一次（给定数字固定不动）。

每个格子的分值只与位置有关：设格 (r,c)(r, c)（r,cr, c 从 00 起）到中心的切比雪夫距离 d=max⁡(∣r−4∣,∣c−4∣)d = \max(|r-4|, |c-4|)，则分值 w=10−dw = 10 - d，即中心 1010 分、向外一圈 9,8,7,69, 8, 7, 6 分。总分为全部格子「填入数字 ×\times 分值」之和。求所有合法填法中总分的最大值；若不存在合法填法，输出 −1-1。

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

行\列 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

表的对称结构一目了然：分值只依赖切比雪夫距离，对角线两侧完全镜像；WEIGHT[r][c] = 10 - max(abs(r-4), abs(c-4)) 一行推导式就能生成它，不需要手抄 81 个数。全表分值之和为 570570，这就是「全部填 9 分数字」时总分的理论上限。

正解

思路

朴素做法及其瓶颈。 最直接的想法是按行优先顺序枚举每个空格的 1∼91\sim9 种填法， 每放一个数字扫一遍行、列、宫检查冲突，填满后算总分并更新最大值。空格数 mm 最多 5757（数据保证非 0 数字不少于 2424 个），最坏 9579^{57} 种组合显然枚举不完。但数独的 约束收缩极快：绝大多数分支在放上第一个数字时就与同行、同列或同宫矛盾了。所以 方向不是换算法，而是把回溯搜索中无用的分支尽快剪掉，同时让正确的分支尽快走完。

第一步：位掩码——让约束检查便宜下来。 每行、每列、每宫各自维护一个 9 位整数， 第 dd 位表示数字 dd 是否已被占用（位 0 不用，全集 ALL = 0b1111111110）。于是 某空格 (r,c)(r,c) 的候选集合就是一次位运算：

cand(r,c)=ALL  &∼  (row[r]∣col[c]∣box[b]) \text{cand}(r,c) = \text{ALL} \;\&\sim\; \big(\text{row}[r] \mid \text{col}[c] \mid \text{box}[b]\big)

放置一个数字是三个 |=，撤销是三个 ^=，候选检查从「扫 27 格」降到「3 次或再取反」。 分值矩阵与搜索无关，先离线算好；题面给定数字的分数也可以在读入时先累加进 base， 搜索只关心空格的增量分数。

第二步：MRV——候选最少的空格先决策。 行优先顺序有个坏毛病：某个只剩唯一候选、 甚至已经没有候选的格子可能排在很后面，导致前面先展开整片注定失败的子树。所以 每一层都重新扫描剩余空格，挑候选个数最少（bit_count() 最小）的那个来决策。 候选为 0 的格子当层立刻返回，矛盾不再向下传播。以样例 1 为例，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、5 行的扫描末尾才轮得到。MRV 把这串「马上就能 定死」的位置提到搜索树最上层，一放下去，周围格子的候选也随之收窄，整棵搜索树的 宽度和深度同时下降。

第三步：逐层真实上界剪枝（分支定界）。 维护当前已经拿到的分数 score 与 历史最优 best。每层扫描时顺带计算一个乐观估计：

bound=score+∑剩余空格 gwg×(格 g 当前最大候选数字) \text{bound} = \text{score} + \sum_{\text{剩余空格 } g} w_g \times \big(\text{格 } g \text{ 当前最大候选数字}\big)

每一项都 ⩾\geqslant 该格最终真实的得分（候选集合只会越搜越窄），所以这条分支里任何 完整解的分数都不超过 bound；一旦 bound⩽best\text{bound} \leqslant \text{best}，整条分支安全剪掉。 相比「剩余分值总和 ×9\times 9」的静态上界，用真实候选数字的上界随搜索加深迅速收紧。 在最慢的一组真实数据（m=57m=57）上实测：41.4 万个搜索节点中，「候选为 0 提前返回」 发生 8 6938\,693 次、「上界截断」发生 34 37334\,373 次，两项合计剪掉了约一成的节点并把 大量矛盾在最浅层暴露。剪枝要起作用，best 必须尽早抬高——所以同一格的候选 按数字从大到小尝试，第一个找到的完整解通常就接近最高分，之后的上界判断立刻变得锋利。

收尾。 空格列表初始按候选数升序排一次（第一次下潜就走上大概率正确的路径）， 每层用交换把 MRV 格换到当前位置、回溯时换回。空格填满即 best = max(best, score)； best 初值取 −1-1，若整棵树搜完仍是 −1-1，正好就是题面要求的「无解输出 −1-1」， 不需要任何特判。

代码

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

typedef long long ll;

int weight[9][9];
const int ALL = (1 << 10) - 2;   // 数字 1..9 的位都为 1

int grid[9][9];
int rows[9], cols[9], boxes[9];
int best;
int n_empties;
vector<tuple<int, int, int> > empties;   // (行, 列, 宫)

void dfs(int k, int score) {
    if (k == n_empties) {
        best = max(best, score);
        return;
    }
    int bound = score;
    int pick = -1, pick_cand = 0, pick_cnt = 10;
    for (int i = k; i < n_empties; i++) {
        int r = get<0>(empties[i]), c = get<1>(empties[i]), b = get<2>(empties[i]);
        int cand = ALL & ~(rows[r] | cols[c] | boxes[b]);
        if (!cand) return;
        bound += weight[r][c] * (31 - __builtin_clz((unsigned)cand));
        int cnt = __builtin_popcount((unsigned)cand);
        if (cnt < pick_cnt) { pick = i; pick_cand = cand; pick_cnt = cnt; }
    }
    if (bound <= best) return;

    swap(empties[k], empties[pick]);
    int r = get<0>(empties[k]), c = get<1>(empties[k]), b = get<2>(empties[k]);
    while (pick_cand) {
        int low = pick_cand & (-pick_cand);
        pick_cand ^= low;
        int v = 31 - __builtin_clz((unsigned)low);
        rows[r] |= low; cols[c] |= low; boxes[b] |= low;
        dfs(k + 1, score + weight[r][c] * v);
        rows[r] ^= low; cols[c] ^= low; boxes[b] ^= low;
    }
    swap(empties[k], empties[pick]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            weight[r][c] = 10 - max(abs(r - 4), abs(c - 4));

    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            cin >> grid[r][c];

    int base = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            int b = r / 3 * 3 + c / 3;
            if (grid[r][c]) {
                int bit = 1 << grid[r][c];
                rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
                base += weight[r][c] * grid[r][c];
            } else {
                empties.push_back(make_tuple(r, c, b));
            }
        }
    best = -1;
    n_empties = (int)empties.size();
    dfs(0, base);
    cout << best << "\n";
    return 0;
}
python
#!/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-02 08:26
# update_at: 2026-10-02 08:46

import sys

WEIGHT = [[10 - max(abs(r - 4), abs(c - 4)) for c in range(9)] for r in range(9)]  # 靶形分值，中心 10 分向外递减
ALL = 0b1111111110  # 候选集合：数字 1..9 的位都为 1


def max_score(grid: list[list[int]]) -> int:
    """返回该数独所有填法中的最高总分；无数独解时返回 -1。"""
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    empties: list[tuple[int, int, int]] = []  # 空格 (行, 列, 宫)
    base = 0  # 题目给定数字已经拿到的分数

    for r in range(9):
        for c in range(9):
            b = r // 3 * 3 + c // 3
            if v := grid[r][c]:
                bit = 1 << v
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
                base += WEIGHT[r][c] * v
            else:
                empties.append((r, c, b))

    best = -1
    n = len(empties)

    def dfs(k: int, score: int) -> None:
        """填第 k..n-1 号空格；同时用各空格的真实候选做上界剪枝。"""
        nonlocal best
        if k == n:
            best = max(best, score)
            return

        # 一轮扫描：既找候选最少的空格，也顺带算出"每个格子都取最大候选数字"的上界
        bound = score
        pick, pick_cand, pick_cnt = -1, 0, 10
        for i in range(k, n):
            r, c, b = empties[i]
            cand = ALL & ~(rows[r] | cols[c] | boxes[b])  # 该空格当前还能填的数字集合
            if not cand:  # 有格子无数字可填，本分支必死
                return
            bound += WEIGHT[empties[i][0]][empties[i][1]] * (cand.bit_length() - 1)
            cnt = cand.bit_count()
            if cnt < pick_cnt:  # 越少候选越优先定下
                pick, pick_cand, pick_cnt = i, cand, cnt
        if bound <= best:  # 乐观估计也追不上当前最优
            return

        empties[k], empties[pick] = empties[pick], empties[k]  # 选中格换到 k，剩下的仍在 k+1..n-1
        r, c, b = empties[k]
        while pick_cand:
            bit = 1 << (pick_cand.bit_length() - 1)  # 从大数字往小试，尽快抬高手头的 best
            pick_cand ^= bit
            v = bit.bit_length() - 1
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
            dfs(k + 1, score + WEIGHT[r][c] * v)
            rows[r] ^= bit
            cols[c] ^= bit
            boxes[b] ^= bit

    dfs(0, base)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    grid = [[next(data) for _ in range(9)] for _ in range(9)]  # 9 行每行 9 个数
    print(max_score(grid))


if __name__ == "__main__":
    solve()

复杂度

  • 时间：搜索树节点数上界为 O(9m)O(9^m)（m⩽57m \leqslant 57），每个节点做一轮 O(m)O(m) 扫描（死分支检测 + 上界累加 + MRV 选择）；在位掩码、MRV、逐层上界、大数字优先 四项优化下实测远小于上界，最慢单点（空格数 5757）约 0.9 s0.9\,\text{s}。
  • 空间：O(m)O(m)——递归深度 mm，三张长度 99 的掩码表、长度 mm 的空格列表与常数 大小的 WEIGHT 表，没有任何大数组。
  • 与 C++ 正解（回溯 + 位运算 + 剪枝）同阶；Python 常数较大，在 1000 ms 限时下 属于允许的 Python 超时范围。

总结

  • 靶形数独 = 数独判定 + 解集合上的加权最大化，回溯 DFS 天然覆盖两件事：每个完整解 对应一条到叶子的路径，叶子处取 max 即得最优总分。
  • 三个位掩码把行/列/宫约束压成一次 &~(|)；候选数、上界、MRV 全部可以从候选集合 一处推导，不需要额外状态。
  • 决定能否跑完的是三项剪枝的配合：MRV 让矛盾最早上浮，逐层真实上界截断 追不上 best 的分支，大数字优先让 best 更快抬高、上界更早生效。
  • best 初值 −1-1 天然表达无解；实测另一仓库 20 组真实数据全部输出一致 （含无解样例与题面两个样例），最慢单点约 0.9 s0.9\,\text{s}。