靶形数独

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2071 字
位掩码 DFS 选候选最少格并上界剪枝
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1447
// 题意：靶形数独每个格子有权重（中心 10 分向外每层递减到 6 分），求填完数独后「格子权重 * 所填数字」之和的最大值，无解输出 -1。
// 思路：位掩码 DFS + 最少候选优先（MRV）。
// 1. 用行、列、宫三个 9 位掩码记录已用数字，空格可填集合为三者并集的补集。
// 2. 每步选择候选数最少的空格展开，分支数最少。
// 3. 用「剩余空格全部填 9 分」作上界剪枝，不可能超过当前最优就回溯。
// 复杂度：搜索树被剪枝得很小，实际很快
// 易错点：初始分数要把题目已经给出的数字也计入，不能只统计自己填的格子。
// 易错点：上界剪枝里的剩余贡献要用权重 * 9 估算，别写成 9 * 剩余格数。
#include <bits/stdc++.h>
using namespace std;
int g[9][9], w[9][9];
int rowM[9], colM[9], boxM[9];
int best = -1;
int boxId(int i, int j){
    return (i / 3) * 3 + j / 3;
}
void dfs(int score, int rest){
    if(score + rest <= best) return;
    int bi = -1, bj = -1, bmask = 0, bcnt = 10;
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            if(g[i][j]) continue;
            int mask = ~(rowM[i] | colM[j] | boxM[boxId(i, j)]) & 0x1FF;
            int cnt = __builtin_popcount(mask);
            if(cnt < bcnt){
                bcnt = cnt;
                bi = i;
                bj = j;
                bmask = mask;
            }
        }
    }
    if(bi < 0){
        best = max(best, score);
        return;
    }
    for(int v = 9; v >= 1; v--){
        int bit = 1 << (v - 1);
        if(!(bmask & bit)) continue;
        g[bi][bj] = v;
        rowM[bi] |= bit;
        colM[bj] |= bit;
        boxM[boxId(bi, bj)] |= bit;
        dfs(score + v * w[bi][bj], rest - 9 * w[bi][bj]);
        rowM[bi] ^= bit;
        colM[bj] ^= bit;
        boxM[boxId(bi, bj)] ^= bit;
        g[bi][bj] = 0;
    }
}
int main(){
    int score = 0, rest = 0;
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            if(!(cin >> g[i][j])) return 0;
            w[i][j] = 6 + min(min(i, 8 - i), min(j, 8 - j));
            if(g[i][j]){
                int bit = 1 << (g[i][j] - 1);
                rowM[i] |= bit;
                colM[j] |= bit;
                boxM[boxId(i, j)] |= bit;
                score += g[i][j] * w[i][j];
            }else{
                rest += 9 * w[i][j];
            }
        }
    }
    dfs(score, rest);
    cout << best << "\n";
    return 0;
}
靶形数独

正文

一本通·提高篇的其它内容
