[NOIP 2009 提高组] 靶形数独

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

位掩码维护行列宫约束，每层选择候选最少空格并回溯最大化加权分数。

OJ: luogu

题目 ID: P1074

难度:提高+/省选-

标签:回溯MRV数独位运算python

日期: 2026-07-16 20:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

补全数独，并最大化每格数字乘靶形权重的总和；无解输出 -1。

思路

行、列、九宫格各用 9 位掩码记录已用数字。候选集合是 FULL & ~(row | column | block)。

每层在剩余空格中选择候选数最少的格子（MRV），能最快暴露冲突。通过交换空格列表把选中格放到当前下标，尝试数字后用异或撤销三个掩码；填满时更新最高分。

Python 知识

  • mask.bit_count() 直接统计候选数。
  • divmod(position, 9) 从一维输入位置取得行列。
  • 权重可由 10 - max(abs(r-4), abs(c-4)) 计算，无需硬编码矩阵。
  • 数字按 9 到 1 尝试，较早得到高分完整解。

代码

python
import sys


values = list(map(int, sys.stdin.buffer.read().split()))
FULL = (1 << 9) - 1
row = [0] * 9
column = [0] * 9
block = [0] * 9
empty = []
score = 0
valid = True

for position, digit in enumerate(values):
    r, c = divmod(position, 9)
    weight = 10 - max(abs(r - 4), abs(c - 4))
    if not digit:
        empty.append((r, c, weight))
        continue
    bit = 1 << (digit - 1)
    box = r // 3 * 3 + c // 3
    if row[r] & bit or column[c] & bit or block[box] & bit:
        valid = False
    row[r] |= bit
    column[c] |= bit
    block[box] |= bit
    score += digit * weight

best = -1


def dfs(index, current_score):
    global best
    if index == len(empty):
        best = max(best, current_score)
        return
    chosen = index
    chosen_mask = 0
    minimum = 10
    for i in range(index, len(empty)):
        r, c, _ = empty[i]
        mask = FULL & ~(row[r] | column[c] | block[r // 3 * 3 + c // 3])
        count = mask.bit_count()
        if not count:
            return
        if count < minimum:
            minimum, chosen, chosen_mask = count, i, mask
            if count == 1:
                break
    empty[index], empty[chosen] = empty[chosen], empty[index]
    r, c, weight = empty[index]
    box = r // 3 * 3 + c // 3
    for digit in range(9, 0, -1):
        bit = 1 << (digit - 1)
        if chosen_mask & bit:
            row[r] |= bit
            column[c] |= bit
            block[box] |= bit
            dfs(index + 1, current_score + digit * weight)
            row[r] ^= bit
            column[c] ^= bit
            block[box] ^= bit
    empty[index], empty[chosen] = empty[chosen], empty[index]


if valid:
    dfs(0, score)
print(best)

复杂度

最坏指数级，MRV 大幅减少实际分支；额外空间 O(81)O(81)。

总结

约束满足问题中，“先处理候选最少变量”通常比固定顺序搜索有效得多。