洛谷 P1074 [NOIP 2009 提高组] 靶形数独

// P1074 的**第一版**：从左上角逐格往右下填，每次试 1~9，扫一遍行、列、宫看撞不撞。
//
// ⚠ 这一版**是对的** —— 它把所有合法填法都走了一遍，取分最高的那个。
//   它的问题只有一个字：慢。而「慢在哪」有两层，页面上第 ② ③ 步各拆一层：
//     ① 判重靠扫（每试一个数就扫 27 格）—— 换成位运算就没了（p1074Plain.cpp）；
//     ② ★★★ 顺序是死的（左上 → 右下）—— 这一层才是大头（p1074.cpp）。
//
// ⚠ 别把「它错」和「它慢」搞混：这一版交上去是 TLE，不是 WA。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9];
static long long best = -1, tries = 0, sols = 0, checks = 0;
// checks = ok() 被调用了多少次，每次都要扫 27 格 —— 这一版真正的工作量在这儿

static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }

/** 把 v 放进 (r, c) 合不合法：行扫 9 格、列扫 9 格、宫扫 9 格。 */
static bool ok(int r, int c, int v) {
    checks++;
    for (int j = 0; j < 9; j++) if (g[r][j] == v) return false;
    for (int i = 0; i < 9; i++) if (g[i][c] == v) return false;
    int br = r / 3 * 3, bc = c / 3 * 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) if (g[br + i][bc + j] == v) return false;
    return true;
}

static long long score() {
    long long s = 0;
    for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) s += (long long)val(r, c) * g[r][c];
    return s;
}

static void dfs(int p) {
    if (p == 81) { sols++; best = max(best, score()); return; }
    int r = p / 9, c = p % 9;
    if (g[r][c]) { dfs(p + 1); return; }
    for (int v = 1; v <= 9; v++)
        if (ok(r, c, v)) { tries++; g[r][c] = v; dfs(p + 1); g[r][c] = 0; }
}

int main(int argc, char** argv) {
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) if (!(cin >> g[r][c])) return 0;
    // ⚠ 已给的数字自己就可能打架 —— 那种输入直接无解
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            if (g[r][c]) {
                int v = g[r][c]; g[r][c] = 0; bool good = ok(r, c, v); g[r][c] = v;
                if (!good) { cout << -1 << "\n"; return 0; }
            }
    dfs(0);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "tries=" << tries << " sols=" << sols << " checks=" << checks << "\n";
    return 0;
}

// P1074 第二版：**只把判重换成位运算**，顺序还是死的（左上 → 右下）。
//
// ★★★ 这一版存在的全部意义，是把「慢」拆成两层，一次只换一个主语：
//   和 p1074Slow.cpp 相比，它**搜索树一模一样** —— 走的格子、试的数字、
//   回溯的时机全都不差一个。⇒ **试填次数会逐个相同**，只有秒表会变。
//   （这就是[第 4 章 P1219](/sol/p1219/) 那条「换尺子数次数也有失效的时候」的现场：
//     这一层的收益，数次数是量不出来的。）
//
// 三个掩码：row_[i] / col_[j] / box_[k]，第 d-1 位是 1 表示数字 d 在那一行/列/宫用过了。
// 判「(r,c) 能不能填 d」从「扫 27 格」变成「三个数或一下、看一位」。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9], row_[9], col_[9], box_[9];
static long long best = -1, cur = 0, tries = 0, sols = 0, scans = 0;
// scans = 「算了多少次『这个空格现在能填哪些数』」—— 一把和机器无关的工作量尺子

static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static void dfs(int p) {
    if (p == 81) { sols++; best = max(best, cur); return; }
    int r = p / 9, c = p % 9;
    if (g[r][c]) { dfs(p + 1); return; }
    int k = boxId(r, c);
    int m = ~(row_[r] | col_[c] | box_[k]) & 0x1FF;
    scans++;
    for (; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, b = 1 << (d - 1);
        tries++;
        g[r][c] = d; row_[r] |= b; col_[c] |= b; box_[k] |= b; cur += (long long)val(r, c) * d;
        dfs(p + 1);
        g[r][c] = 0; row_[r] ^= b; col_[c] ^= b; box_[k] ^= b; cur -= (long long)val(r, c) * d;
    }
}

int main(int argc, char** argv) {
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!(cin >> g[r][c])) return 0;
            if (g[r][c] == 0) continue;
            int b = 1 << (g[r][c] - 1);
            if ((row_[r] | col_[c] | box_[boxId(r, c)]) & b) { cout << -1 << "\n"; return 0; }
            row_[r] |= b; col_[c] |= b; box_[boxId(r, c)] |= b;
            cur += (long long)val(r, c) * g[r][c];
        }
    dfs(0);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "tries=" << tries << " sols=" << sols << " scans=" << scans << "\n";
    return 0;
}

// P1074 第三版：位运算 ＋ ★「**行按空格数从少到多**」的固定顺序（网上流传最广的写法）。
//
// ★ 想法很自然：空格越少的行，可填的花样越少 —— 先把它填掉，树的上层就窄。
//   这是本章第 4 步「搜索顺序剪枝」的一个**便宜实现**：顺序在开搜之前算一次就定死了，
//   搜索过程中一次都不用重算。
//
// ⚠ 而它和 p1074.cpp（每一步都重新挑候选最少的格子）差的正是「一次」和「每一步」：
//   填掉几个格子之后，各行的松紧早就不是开搜时那样了。
//   ⇒ 页面上第 ⑤ 步那张表量了这个差值 —— 它不是「差不多」。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9], row_[9], col_[9], box_[9];
static long long best = -1, cur = 0, tries = 0, sols = 0, scans = 0;
static int order_[81], tot = 0;              // 按「行空格数」排好的格子顺序（只存空格）

static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static void dfs(int i) {
    if (i == tot) { sols++; best = max(best, cur); return; }
    int r = order_[i] / 9, c = order_[i] % 9, k = boxId(r, c);
    int m = ~(row_[r] | col_[c] | box_[k]) & 0x1FF;
    scans++;
    for (; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, b = 1 << (d - 1);
        tries++;
        g[r][c] = d; row_[r] |= b; col_[c] |= b; box_[k] |= b; cur += (long long)val(r, c) * d;
        dfs(i + 1);
        g[r][c] = 0; row_[r] ^= b; col_[c] ^= b; box_[k] ^= b; cur -= (long long)val(r, c) * d;
    }
}

int main(int argc, char** argv) {
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!(cin >> g[r][c])) return 0;
            if (g[r][c] == 0) continue;
            int b = 1 << (g[r][c] - 1);
            if ((row_[r] | col_[c] | box_[boxId(r, c)]) & b) { cout << -1 << "\n"; return 0; }
            row_[r] |= b; col_[c] |= b; box_[boxId(r, c)] |= b;
            cur += (long long)val(r, c) * g[r][c];
        }

    int blank[9] = {0};
    for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (!g[r][c]) blank[r]++;
    int rid[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    stable_sort(rid, rid + 9, [&](int a, int b) { return blank[a] < blank[b]; });
    for (int i = 0; i < 9; i++)
        for (int c = 0; c < 9; c++) if (!g[rid[i]][c]) order_[tot++] = rid[i] * 9 + c;

    dfs(0);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "tries=" << tries << " sols=" << sols << " scans=" << scans << "\n";
    return 0;
}

// P1074 靶形数独 —— 位运算判重 ＋ ★ 搜索顺序剪枝（★ 这一版就能 AC）
//
// 题目：9 × 9 数独，`0` 是空格。每格有一个分值（离中心越近越高，见页面上那张图），
//       总分 = Σ 格子分值 × 填进去的数字。求**所有合法填法里的最高分**；无解输出 -1。
//
// ★ 和普通数独的差别只有一句话，可它决定了整个搜索的形状：
//   普通数独**找到一个解就能停**；这道题要**把所有解都走一遍**才知道哪个分最高。
//   ⇒ 「找到就 return」是这道题最容易写错的一行（p1074First.cpp）。
//
// ★★★ 这一版相对上一版（p1074Row.cpp）只换了一件事：**下一个填哪一格**。
//   固定顺序（左上 → 右下）挑到的格子可能有 8 个候选，一层就岔出 8 条路；
//   而**候选最少的那一格**可能只有 1 个候选 —— 那一层根本不分岔。
//   这就是本章第 4 步「三板斧」里的**搜索顺序剪枝**，也是这道题的题眼。
//   ⚠ 它还白送一条**可行性剪枝**：扫的时候只要有一个空格候选数为 0，当场回头。
//
// 位运算部分：row[i] / col[j] / box[k] 各存一个 9 位掩码，第 d-1 位是 1 表示 d 已经用过。
//   某格能填什么 = ~(row | col | box) & 0x1FF，`__builtin_popcount` 一句就是候选个数。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9];
static int row_[9], col_[9], box_[9];       // 9 位掩码：第 d-1 位 = 1 ⇒ 数字 d 已用
static long long best = -1;                 // ★ 初值必须是 -1，不是 0（见 p1074Zero.cpp）
static long long cur = 0;                   // 当前已填部分的得分
static long long tries = 0, sols = 0;       // ★ 试填次数（换尺子用）／ 完整解的个数
static long long scans = 0;                 // ★ 另一把尺子：算了多少次「这个空格能填哪些数」

/** 格子 (r, c) 的分值：最外圈 6 分，往里一圈加 1，正中间 10 分。 */
static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static void dfs(int left) {                 // left = 还剩几个空格
    if (left == 0) { sols++; best = max(best, cur); return; }

    // ★ 搜索顺序剪枝：扫一遍所有空格，挑候选最少的那一个
    int br = -1, bc = -1, bm = 0, bcnt = 10;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            int m = ~(row_[r] | col_[c] | box_[boxId(r, c)]) & 0x1FF;
            scans++;
            int cnt = __builtin_popcount(m);
            if (cnt == 0) return;           // ⚠ 白送的可行性剪枝：这一格已经没得填了
            if (cnt < bcnt) { bcnt = cnt; bm = m; br = r; bc = c; if (cnt == 1) goto found; }
        }
found:
    for (int m = bm; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, b = 1 << (d - 1), k = boxId(br, bc);
        tries++;                            // ★ 尺子：数「往格子里写了几次数字」，各版本可比
        g[br][bc] = d; row_[br] |= b; col_[bc] |= b; box_[k] |= b; cur += (long long)val(br, bc) * d;
        dfs(left - 1);
        g[br][bc] = 0; row_[br] ^= b; col_[bc] ^= b; box_[k] ^= b; cur -= (long long)val(br, bc) * d;
    }
}

int main(int argc, char** argv) {
    int left = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!(cin >> g[r][c])) return 0;
            if (g[r][c] == 0) { left++; continue; }
            int b = 1 << (g[r][c] - 1);
            // ⚠ 题面只说「一个尚未填满的数独方格」，**没保证已给的数字自己不打架**
            if ((row_[r] | col_[c] | box_[boxId(r, c)]) & b) { cout << -1 << "\n"; return 0; }
            row_[r] |= b; col_[c] |= b; box_[boxId(r, c)] |= b;
            cur += (long long)val(r, c) * g[r][c];
        }
    dfs(left);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "tries=" << tries << " sols=" << sols << " scans=" << scans << "\n";
    return 0;
}

// P1074 第五版：在正解（p1074.cpp）之上再加一招 ★**最优性剪枝**。
//
// 想法：搜到一半时，把「剩下的空格全部按它现在还能填的最大数字」算一个乐观上界 ——
//   `cur + Σ 分值 × 最大候选`。如果这个上界都不比已知的 best 大，这条路不用走了。
//   ⚠ 而这个上界**是免费的**：为了挑「候选最少的格子」本来就要扫一遍所有空格，
//     顺手把每格的最大候选取出来即可，一次额外的循环都不用加。
//
// ★★★ 页面上第 ⑥ 步量了它值多少钱 —— 结论相当反直觉，这里先不剧透。
//   （提示：这道题的搜索树有一个**任何剪枝都砍不掉的下界**。）

#include <bits/stdc++.h>
using namespace std;

static int g[9][9], row_[9], col_[9], box_[9];
static long long best = -1, cur = 0, tries = 0, sols = 0, cuts = 0, scans = 0;

static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static void dfs(int left) {
    if (left == 0) { sols++; best = max(best, cur); return; }

    int br = -1, bc = -1, bm = 0, bcnt = 10;
    long long ub = 0;                        // 剩余空格的乐观得分上界
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            int m = ~(row_[r] | col_[c] | box_[boxId(r, c)]) & 0x1FF;
            scans++;
            if (m == 0) return;
            int cnt = __builtin_popcount(m);
            ub += (long long)val(r, c) * (32 - __builtin_clz(m));   // 最高位 = 还能填的最大数字
            if (cnt < bcnt) { bcnt = cnt; bm = m; br = r; bc = c; }
        }
    if (cur + ub <= best) { cuts++; return; }   // ★ 最优性剪枝

    for (int m = bm; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, b = 1 << (d - 1), k = boxId(br, bc);
        tries++;
        g[br][bc] = d; row_[br] |= b; col_[bc] |= b; box_[k] |= b; cur += (long long)val(br, bc) * d;
        dfs(left - 1);
        g[br][bc] = 0; row_[br] ^= b; col_[bc] ^= b; box_[k] ^= b; cur -= (long long)val(br, bc) * d;
    }
}

int main(int argc, char** argv) {
    int left = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!(cin >> g[r][c])) return 0;
            if (g[r][c] == 0) { left++; continue; }
            int b = 1 << (g[r][c] - 1);
            if ((row_[r] | col_[c] | box_[boxId(r, c)]) & b) { cout << -1 << "\n"; return 0; }
            row_[r] |= b; col_[c] |= b; box_[boxId(r, c)] |= b;
            cur += (long long)val(r, c) * g[r][c];
        }
    dfs(left);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count")
        cerr << "tries=" << tries << " sols=" << sols << " cuts=" << cuts << " scans=" << scans << "\n";
    return 0;
}

// P1074 的**错法一**：和 p1074.cpp 一模一样，只把「走完所有解」改成「★ 找到一个解就 return」。
//
// ⚠ 这是从「普通数独」抄过来最自然的一个动作 —— 普通数独只要一个解，找到就该停。
//   可这道题问的是**所有填法里分最高的那个**：第一个被搜到的解，分数是随手来的。
//
// ★★★ 而「跑一下样例就发现了」这句话在这道题上**只对了一半**（页面第 ⑦ 步实测）：
//   样例 1 它照样输出 2829 —— 那张盘面只有 3 个解，而搜到的第一个正好就是分最高的；
//   样例 2 它输出 2842，比正确答案 2852 少 10 分，**这一组才挡得住它**。
//   ⇒ 「官方样例挡不挡得住」的主语是**哪一组样例**，不是「样例」。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9];
static int row_[9], col_[9], box_[9];       // 9 位掩码：第 d-1 位 = 1 ⇒ 数字 d 已用
static long long best = -1;
static bool done = false;                   // ★ 找到一个解就收工
static long long cur = 0;                   // 当前已填部分的得分
static long long tries = 0, sols = 0;       // ★ 试填次数（换尺子用）／ 完整解的个数

/** 格子 (r, c) 的分值：最外圈 6 分，往里一圈加 1，正中间 10 分。 */
static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static void dfs(int left) {                 // left = 还剩几个空格
    if (left == 0) { sols++; best = max(best, cur); done = true; return; }   // ★ 错在这里

    // ★ 搜索顺序剪枝：扫一遍所有空格，挑候选最少的那一个
    int br = -1, bc = -1, bm = 0, bcnt = 10;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            int m = ~(row_[r] | col_[c] | box_[boxId(r, c)]) & 0x1FF;
            int cnt = __builtin_popcount(m);
            if (cnt == 0) return;           // ⚠ 白送的可行性剪枝：这一格已经没得填了
            if (cnt < bcnt) { bcnt = cnt; bm = m; br = r; bc = c; if (cnt == 1) goto found; }
        }
found:
    for (int m = bm; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, b = 1 << (d - 1), k = boxId(br, bc);
        tries++;                            // ★ 尺子：数「往格子里写了几次数字」，各版本可比
        g[br][bc] = d; row_[br] |= b; col_[bc] |= b; box_[k] |= b; cur += (long long)val(br, bc) * d;
        dfs(left - 1);
        if (done) { g[br][bc] = 0; row_[br] ^= b; col_[bc] ^= b; box_[k] ^= b; cur -= (long long)val(br, bc) * d; return; }
        g[br][bc] = 0; row_[br] ^= b; col_[bc] ^= b; box_[k] ^= b; cur -= (long long)val(br, bc) * d;
    }
}

int main(int argc, char** argv) {
    int left = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!(cin >> g[r][c])) return 0;
            if (g[r][c] == 0) { left++; continue; }
            int b = 1 << (g[r][c] - 1);
            // ⚠ 题面只说「一个尚未填满的数独方格」，**没保证已给的数字自己不打架**
            if ((row_[r] | col_[c] | box_[boxId(r, c)]) & b) { cout << -1 << "\n"; return 0; }
            row_[r] |= b; col_[c] |= b; box_[boxId(r, c)] |= b;
            cur += (long long)val(r, c) * g[r][c];
        }
    dfs(left);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "tries=" << tries << " sols=" << sols << "\n";
    return 0;
}

// P1074 对拍生成器：`./p1074Gen <seed> [k] [mode]`
//   k    = 盘面上留几个已知数（题面保证 ≥ 24，默认 30）
//   mode = 0 挖洞（★ 一定有解）／ 1 随便撒（★ 大概率无解）
//
// ★★★ 这两个 mode 是这一页最值钱的一处对照，理由和[第 12 章 P1226](/sol/p1226/)
//   那条「对拍 0 次有两种原因」是同一件事：
//
//   mode 0 先造一张**完整的合法数独**，再随机挖洞 —— 挖出来的盘面**一定有解**
//     （至少那张原图就是一个解）。⇒ 用它对拍，「无解时该输出 -1」那类 bug
//     （p1074Zero.cpp）**在结构上永远抓不到**，不是概率低，是精确的 0。
//
//   mode 1 往空盘上一个一个撒数字，只要求撒下去的那一刻行、列、宫都不冲突 ——
//     这样的盘面**看着合法**，可它多半没有解。⇒ 这一档才问得出「无解怎么办」。
//
// ⚠ 别把 mode 1 当成「更好的生成器」：它造出来的盘面几乎全是无解的，
//   于是所有版本一起秒退，**别的 bug 在这一档反而全瞎**。两档都要跑。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9];
static mt19937 rng;

static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static bool ok(int r, int c, int v) {
    for (int j = 0; j < 9; j++) if (g[r][j] == v) return false;
    for (int i = 0; i < 9; i++) if (g[i][c] == v) return false;
    int br = r / 3 * 3, bc = c / 3 * 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) if (g[br + i][bc + j] == v) return false;
    return true;
}

/** 随机化 DFS 填出一张完整的合法数独。 */
static bool fill(int p) {
    if (p == 81) return true;
    int r = p / 9, c = p % 9;
    int d[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    shuffle(d, d + 9, rng);
    for (int i = 0; i < 9; i++)
        if (ok(r, c, d[i])) { g[r][c] = d[i]; if (fill(p + 1)) return true; g[r][c] = 0; }
    return false;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int k = argc > 2 ? atoi(argv[2]) : 30;
    int mode = argc > 3 ? atoi(argv[3]) : 0;
    rng.seed(seed * 2654435761u + 12345u);
    k = max(0, min(81, k));

    if (mode == 0) {
        fill(0);
        int idx[81];
        for (int i = 0; i < 81; i++) idx[i] = i;
        shuffle(idx, idx + 81, rng);
        for (int i = 0; i < 81 - k; i++) g[idx[i] / 9][idx[i] % 9] = 0;   // 挖掉 81 - k 格
    } else {
        int put = 0;
        for (int guard = 0; guard < 20000 && put < k; guard++) {
            int r = rng() % 9, c = rng() % 9, v = rng() % 9 + 1;
            if (g[r][c] || !ok(r, c, v)) continue;
            g[r][c] = v; put++;
        }
    }

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) printf("%d%c", g[r][c], c == 8 ? '\n' : ' ');
    }
    (void)boxId;
    return 0;
}

// P1074 的**错法二**：和 p1074.cpp 一模一样，只把 `best` 的初值从 `-1` 写成了 `0`。
//
// 题面最后一句：「如果这个数独无解，则输出整数 -1」。`best` 写成 `0` 起步，
// 有解的时候一分不差 —— **无解的时候它打印 0**。
//
// ★★★ 这个 bug 值得单独留一份，是因为它在对拍里的表现：
//   用「挖洞」生成器（p1074Gen 的 mode 0）跑多少轮都抓不到，而且是**精确的 0** ——
//   挖洞造出来的盘面**一定有解**，这一行代码根本没有机会执行。
//   ⇒ [第 12 章 P1226](/sol/p1226/) 那条判据：**造一档违反它的数据**（mode 1 随便撒），
//     它当场就活了。「对拍 0 次」的两种原因里，这是**生成器缺一档**那一种。

#include <bits/stdc++.h>
using namespace std;

static int g[9][9];
static int row_[9], col_[9], box_[9];       // 9 位掩码：第 d-1 位 = 1 ⇒ 数字 d 已用
static long long best = 0;  // ★ 错在这里：无解时它会打印 0                 // ★ 初值必须是 -1，不是 0（见 p1074Zero.cpp）
static long long cur = 0;                   // 当前已填部分的得分
static long long tries = 0, sols = 0;       // ★ 试填次数（换尺子用）／ 完整解的个数

/** 格子 (r, c) 的分值：最外圈 6 分，往里一圈加 1，正中间 10 分。 */
static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

static void dfs(int left) {                 // left = 还剩几个空格
    if (left == 0) { sols++; best = max(best, cur); return; }

    // ★ 搜索顺序剪枝：扫一遍所有空格，挑候选最少的那一个
    int br = -1, bc = -1, bm = 0, bcnt = 10;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            int m = ~(row_[r] | col_[c] | box_[boxId(r, c)]) & 0x1FF;
            int cnt = __builtin_popcount(m);
            if (cnt == 0) return;           // ⚠ 白送的可行性剪枝：这一格已经没得填了
            if (cnt < bcnt) { bcnt = cnt; bm = m; br = r; bc = c; if (cnt == 1) goto found; }
        }
found:
    for (int m = bm; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, b = 1 << (d - 1), k = boxId(br, bc);
        tries++;                            // ★ 尺子：数「往格子里写了几次数字」，各版本可比
        g[br][bc] = d; row_[br] |= b; col_[bc] |= b; box_[k] |= b; cur += (long long)val(br, bc) * d;
        dfs(left - 1);
        g[br][bc] = 0; row_[br] ^= b; col_[bc] ^= b; box_[k] ^= b; cur -= (long long)val(br, bc) * d;
    }
}

int main(int argc, char** argv) {
    int left = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!(cin >> g[r][c])) return 0;
            if (g[r][c] == 0) { left++; continue; }
            int b = 1 << (g[r][c] - 1);
            // ⚠ 题面只说「一个尚未填满的数独方格」，**没保证已给的数字自己不打架**
            if ((row_[r] | col_[c] | box_[boxId(r, c)]) & b) { cout << -1 << "\n"; return 0; }
            row_[r] |= b; col_[c] |= b; box_[boxId(r, c)] |= b;
            cur += (long long)val(r, c) * g[r][c];
        }
    dfs(left);
    cout << best << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "tries=" << tries << " sols=" << sols << "\n";
    return 0;
}

// P1074 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1074Count`      人看的版本
// `./p1074Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① 官方两组样例：五个版本各走了多少步（★ 两把尺子：试填次数 ／ 算掩码的次数）；
//   ② 随机挖洞盘面（已知数 k = 24 / 26 / 30 / 34 / 40），同样两把尺子；
//   ③ ★★★ 这一页的主线：**解的个数** —— 官方样例只有 3 个和 85 个，
//      而随机挖到同样多已知数的盘面动辄上万个。顺手写的生成器和真题不是一回事；
//   ④ 「找到一个解就 return」那个错法的抓获率（⚠ 官方样例 ① 放它过去了）；
//   ⑤ 「best 初值写成 0」那个错法：挖洞档**精确的 0**，随便撒那档当场就活。
//
// ⚠ 里面的生成器必须和 p1074Gen.cpp 逐字一致（同样的 mt19937 种子算法、同样的 shuffle），
//   否则这里算出来的数和真跑对拍对不上。

#include <bits/stdc++.h>
using namespace std;

static bool CSV = false;
static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

static inline int val(int r, int c) { return 6 + min(min(r, c), min(8 - r, 8 - c)); }
static inline int boxId(int r, int c) { return r / 3 * 3 + c / 3; }

/* ───────────────────────── 生成器（和 p1074Gen.cpp 逐字一致） ───────────────────────── */
static int gg[9][9];
static mt19937 rng;

static bool okScan(int r, int c, int v) {
    for (int j = 0; j < 9; j++) if (gg[r][j] == v) return false;
    for (int i = 0; i < 9; i++) if (gg[i][c] == v) return false;
    int br = r / 3 * 3, bc = c / 3 * 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) if (gg[br + i][bc + j] == v) return false;
    return true;
}
static bool fillAll(int p) {
    if (p == 81) return true;
    int r = p / 9, c = p % 9, d[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    shuffle(d, d + 9, rng);
    for (int i = 0; i < 9; i++)
        if (okScan(r, c, d[i])) { gg[r][c] = d[i]; if (fillAll(p + 1)) return true; gg[r][c] = 0; }
    return false;
}
/** 造一张盘面到 board[9][9]。mode 0 = 挖洞（一定有解）／ 1 = 随便撒（多半无解）。 */
static void gen(int seed, int k, int mode, int board[9][9]) {
    memset(gg, 0, sizeof gg);
    rng.seed((unsigned)seed * 2654435761u + 12345u);
    k = max(0, min(81, k));
    if (mode == 0) {
        fillAll(0);
        int idx[81];
        for (int i = 0; i < 81; i++) idx[i] = i;
        shuffle(idx, idx + 81, rng);
        for (int i = 0; i < 81 - k; i++) gg[idx[i] / 9][idx[i] % 9] = 0;
    } else {
        int put = 0;
        for (int guard = 0; guard < 20000 && put < k; guard++) {
            int r = rng() % 9, c = rng() % 9, v = rng() % 9 + 1;
            if (gg[r][c] || !okScan(r, c, v)) continue;
            gg[r][c] = v; put++;
        }
    }
    memcpy(board, gg, sizeof gg);
}

/* ───────────────────────── 五个版本，一份参数化的实现 ───────────────────────── */
enum Order { FIXED, ROWSORT, MRV };

struct Res { long long best, tries, scans, sols, cuts; };

static int b_[9][9], rowM[9], colM[9], boxM[9];
static long long B_best, B_cur, B_tries, B_scans, B_sols, B_cuts;
static bool B_bound, B_first, B_done;
static Order B_ord;
static int B_order[81], B_tot;

static void solveDfs(int i, int left) {
    if (left == 0) {
        B_sols++;
        B_best = max(B_best, B_cur);
        if (B_first) B_done = true;
        return;
    }
    int br, bc, bm;
    if (B_ord == MRV || B_bound) {
        br = bc = -1; bm = 0;
        int bcnt = 10;
        long long ub = 0;
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                if (b_[r][c]) continue;
                int m = ~(rowM[r] | colM[c] | boxM[boxId(r, c)]) & 0x1FF;
                B_scans++;
                if (m == 0) return;
                int cnt = __builtin_popcount(m);
                if (B_bound) ub += (long long)val(r, c) * (32 - __builtin_clz(m));
                if (cnt < bcnt) { bcnt = cnt; bm = m; br = r; bc = c; if (cnt == 1 && !B_bound) goto found; }
            }
        if (B_bound && B_cur + ub <= B_best) { B_cuts++; return; }
    found:;
    } else {
        int p = B_order[i];
        br = p / 9; bc = p % 9;
        bm = ~(rowM[br] | colM[bc] | boxM[boxId(br, bc)]) & 0x1FF;
        B_scans++;
    }
    int k = boxId(br, bc);
    for (int m = bm; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1, bit = 1 << (d - 1);
        B_tries++;
        b_[br][bc] = d; rowM[br] |= bit; colM[bc] |= bit; boxM[k] |= bit;
        B_cur += (long long)val(br, bc) * d;
        solveDfs(i + 1, left - 1);
        b_[br][bc] = 0; rowM[br] ^= bit; colM[bc] ^= bit; boxM[k] ^= bit;
        B_cur -= (long long)val(br, bc) * d;
        if (B_done) return;
    }
}

static Res solve(const int board[9][9], Order ord, bool bound, bool first, long long init = -1) {
    memcpy(b_, board, sizeof b_);
    memset(rowM, 0, sizeof rowM); memset(colM, 0, sizeof colM); memset(boxM, 0, sizeof boxM);
    B_best = init; B_cur = 0; B_tries = B_scans = B_sols = B_cuts = 0;
    B_bound = bound; B_first = first; B_done = false; B_ord = ord;

    int left = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (!b_[r][c]) { left++; continue; }
            int bit = 1 << (b_[r][c] - 1);
            if ((rowM[r] | colM[c] | boxM[boxId(r, c)]) & bit) return {-1, 0, 0, 0, 0};
            rowM[r] |= bit; colM[c] |= bit; boxM[boxId(r, c)] |= bit;
            B_cur += (long long)val(r, c) * b_[r][c];
        }

    B_tot = 0;
    if (ord == ROWSORT) {
        int blank[9] = {0};
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (!b_[r][c]) blank[r]++;
        int rid[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
        stable_sort(rid, rid + 9, [&](int a, int b) { return blank[a] < blank[b]; });
        for (int i = 0; i < 9; i++)
            for (int c = 0; c < 9; c++) if (!b_[rid[i]][c]) B_order[B_tot++] = rid[i] * 9 + c;
    } else if (ord == FIXED) {
        for (int p = 0; p < 81; p++) if (!b_[p / 9][p % 9]) B_order[B_tot++] = p;
    }
    solveDfs(0, left);
    return {B_best, B_tries, B_scans, B_sols, B_cuts};
}

/** 第一版（扫 27 格判重）：只为了数它的 ok() 调用次数 —— 试填次数和 FIXED 那版必然相同。 */
static long long slowChecks;
static int s_[9][9];
static long long S_tries, S_sols;
static bool sOk(int r, int c, int v) {
    slowChecks++;
    for (int j = 0; j < 9; j++) if (s_[r][j] == v) return false;
    for (int i = 0; i < 9; i++) if (s_[i][c] == v) return false;
    int br = r / 3 * 3, bc = c / 3 * 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) if (s_[br + i][bc + j] == v) return false;
    return true;
}
static void sDfs(int p) {
    if (p == 81) { S_sols++; return; }
    int r = p / 9, c = p % 9;
    if (s_[r][c]) { sDfs(p + 1); return; }
    for (int v = 1; v <= 9; v++)
        if (sOk(r, c, v)) { S_tries++; s_[r][c] = v; sDfs(p + 1); s_[r][c] = 0; }
}
static void slowRun(const int board[9][9]) {
    memcpy(s_, board, sizeof s_);
    slowChecks = S_tries = S_sols = 0;
    // ⚠ 和 p1074Slow.cpp 逐字对齐：它开搜之前还要把已给的数字自己验一遍
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            if (s_[r][c]) { int v = s_[r][c]; s_[r][c] = 0; sOk(r, c, v); s_[r][c] = v; }
    sDfs(0);
}

/* ───────────────────────────────── 主程序 ───────────────────────────────── */
static const char* SAMPLE[2] = {
    "7 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",
    "0 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",
};

static void parse(const char* txt, int board[9][9]) {
    istringstream in(txt);
    for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) in >> board[r][c];
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");

    /* ① 官方两组样例 */
    if (!CSV) printf("① 官方两组样例（答案 / 试填次数 / 算掩码次数 / 解数）\n");
    for (int s = 0; s < 2; s++) {
        int board[9][9];
        parse(SAMPLE[s], board);
        Res fx = solve(board, FIXED, false, false);
        Res rw = solve(board, ROWSORT, false, false);
        Res mv = solve(board, MRV, false, false);
        Res bd = solve(board, MRV, true, false);
        Res ft = solve(board, MRV, false, true);
        slowRun(board);
        if (!CSV)
            printf("  样例 %d：答案 %lld，解 %lld 个｜第一版 试填 %lld / 扫 27 格 %lld 次"
                   "｜位运算 试填 %lld / 掩码 %lld｜行排序 %lld / %lld｜候选最少 %lld / %lld"
                   "｜再加上界 %lld / %lld（走完的解 %lld、剪 %lld 次）｜找到就停 → %lld\n",
                   s + 1, mv.best, mv.sols, S_tries, slowChecks, fx.tries, fx.scans,
                   rw.tries, rw.scans, mv.tries, mv.scans, bd.tries, bd.scans, bd.sols, bd.cuts, ft.best);
        char key[32];
        snprintf(key, sizeof key, "sample%d", s + 1);
        row(key, {mv.best, mv.sols, S_tries, slowChecks, fx.tries, fx.scans, rw.tries, rw.scans,
                  mv.tries, mv.scans, bd.tries, bd.scans, bd.sols, bd.cuts, ft.best});
    }

    /* ② 随机挖洞盘面：已知数 k 一档一档往下压 */
    const int KS[5] = {40, 34, 30, 26, 24};
    const int BOARDS = 10;
    if (!CSV) printf("\n② 随机挖洞盘面（每档 %d 张，四个版本的 试填次数 / 掩码次数 合计）\n", BOARDS);
    vector<long long> avgSols, maxSols;
    for (int t = 0; t < 5; t++) {
        long long a[8] = {0}, sols = 0, mxSols = 0, bdSols = 0;
        for (int s = 1; s <= BOARDS; s++) {
            int board[9][9];
            gen(s, KS[t], 0, board);
            Res fx = solve(board, FIXED, false, false);
            Res rw = solve(board, ROWSORT, false, false);
            Res mv = solve(board, MRV, false, false);
            Res bd = solve(board, MRV, true, false);
            a[0] += fx.tries; a[1] += fx.scans; a[2] += rw.tries; a[3] += rw.scans;
            a[4] += mv.tries; a[5] += mv.scans; a[6] += bd.tries; a[7] += bd.scans;
            sols += mv.sols; mxSols = max(mxSols, mv.sols); bdSols += bd.sols;
        }
        avgSols.push_back(sols * 100 / BOARDS);
        maxSols.push_back(mxSols);
        if (!CSV)
            printf("  k = %2d：位运算 %lld / %lld｜行排序 %lld / %lld｜候选最少 %lld / %lld"
                   "｜再加上界 %lld / %lld｜解数合计 %lld（平均 %.2f，最多 %lld）\n",
                   KS[t], a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], sols,
                   sols * 1.0 / BOARDS, mxSols);
        if (!CSV) printf("        └ 加了上界那版真正「走完」的解只有 %lld 个\n", bdSols);
        char key[32];
        snprintf(key, sizeof key, "k%d", KS[t]);
        row(key, {a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], sols, bdSols});
    }

    row("avgSols", avgSols);
    row("maxSols", maxSols);

    /* ③ ★★★ 主线在这儿：官方样例只有 3 个和 85 个解，而随机挖到同样多已知数的盘面上万个。
          （数字就是 ① 和 ② 里的 sols —— 不再重算一遍，省一份 check:viz 的时间。） */

    /* ④ 「找到一个解就 return」的抓获率 */
    if (!CSV) printf("\n④ 「找到就停」那个错法：300 轮里被抓多少次\n");
    {
        vector<long long> got;
        for (int k : {40, 30, 24}) {
            int bad = 0;
            for (int s = 1; s <= 300; s++) {
                int board[9][9];
                gen(s, k, 0, board);
                if (solve(board, MRV, false, true).best != solve(board, MRV, false, false).best) bad++;
            }
            got.push_back(bad);
            if (!CSV) printf("  k = %2d：%d / 300\n", k, bad);
        }
        row("firstCatch", got);
    }

    /* ⑤ 「best 初值 0」的抓获率：挖洞档必然是 0，随便撒那档才活 */
    if (!CSV) printf("\n⑤ 「best 初值写成 0」那个错法：两种生成器差在哪\n");
    {
        vector<long long> got;
        for (int mode : {0, 1}) {
            int bad = 0, unsolvable = 0;
            for (int s = 1; s <= 300; s++) {
                int board[9][9];
                gen(s, 26, mode, board);
                long long okAns = solve(board, MRV, false, false).best;
                long long zero = solve(board, MRV, false, false, 0).best;
                if (okAns == -1) unsolvable++;
                if (okAns != zero) bad++;
            }
            got.push_back(bad); got.push_back(unsolvable);
            if (!CSV) printf("  mode %d（%s）：抓到 %d / 300，其中正解就是 -1 的有 %d 轮\n",
                             mode, mode == 0 ? "挖洞" : "随便撒", bad, unsolvable);
        }
        row("zeroCatch", got);
    }

    /* ⑥ ★ 一条和搜索完全无关的验算路：题面**第二张图**上那个填好的盘面，
          逐格抄下来，直接按「分值 × 数字」加一遍 —— 看它是不是真的 2829，
          以及它是不是样例 ① 的**最高分**那一个。 */
    if (!CSV) printf("\n⑥ 题面那张 2829 分的图：逐格抄下来自己加一遍\n");
    {
        static const char* FILLED =
            "7 5 4 9 3 8 2 6 1 1 2 8 6 4 5 9 3 7 6 3 9 2 1 7 4 8 5 "
            "8 6 5 4 2 9 1 7 3 9 7 2 3 5 1 6 4 8 4 1 3 8 7 6 5 2 9 "
            "5 4 7 1 8 2 3 9 6 2 9 1 7 6 3 8 5 4 3 8 6 5 9 4 7 1 2";
        int f[9][9];
        parse(FILLED, f);
        long long sum = 0;
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) sum += (long long)val(r, c) * f[r][c];
        // 合法性：每行 / 每列 / 每宫都恰好是 1~9
        int bad = 0;
        for (int i = 0; i < 9; i++) {
            int mr = 0, mc = 0, mb = 0;
            for (int j = 0; j < 9; j++) {
                mr |= 1 << (f[i][j] - 1);
                mc |= 1 << (f[j][i] - 1);
                mb |= 1 << (f[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - 1);
            }
            if (mr != 0x1FF || mc != 0x1FF || mb != 0x1FF) bad++;
        }
        // 它是不是样例 ① 的解（每个已给的数字都对得上）
        int s1[9][9];
        parse(SAMPLE[0], s1);
        int mismatch = 0;
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++)
            if (s1[r][c] && s1[r][c] != f[r][c]) mismatch++;
        if (!CSV) printf("  得分 %lld｜不合法的行/列/宫 %d 处｜和样例 ① 已给数字对不上的 %d 处\n",
                         sum, bad, mismatch);
        row("figure", {sum, bad, mismatch});
    }
    return 0;
}