题解：靶形数独最高分数（回溯+剪枝优化）

一、解题核心思路

靶形数独是带权值的数独填充问题，需在满足数独规则的前提下，最大化“格子权值×填入数字”的总和。由于数独规模固定（9×9），且非零数字较多（≥24），适合用回溯法求解，关键是通过剪枝和搜索顺序优化减少无效分支。

二、关键预处理

1. 权值矩阵构建

靶形数独的权值由格子到中心的距离决定（中心为$(4,4)$，0-based索引）：

• 距离$d = \max(|i-4|, |j-4|)$（曼哈顿距离的变种）；
• 权值为$10 - d$（中心10分，每外扩一圈减1分）。

预处理权值矩阵score[9][9]：

int score[9][9];
for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
        int d = max(abs(i - 4), abs(j - 4));
        score[i][j] = 10 - d;
    }
}

2. 状态压缩（位掩码）

用位掩码记录每行、每列、每个3×3小九宫格已使用的数字（第$k$位为1表示数字$k+1$已用）：

• row_mask[9]：每行已用数字；
• col_mask[9]：每列已用数字；
• cell_mask[3][3]：每个小九宫格已用数字。

例如，row_mask[0] = 0b101表示第0行已用数字1、3。

三、解题步骤

步骤1：初始化状态与初始分数

读取输入的数独矩阵，初始化位掩码，并计算已填数字的初始分数：

int grid[9][9];
int initial_score = 0;
memset(row_mask, 0, sizeof(row_mask));
memset(col_mask, 0, sizeof(col_mask));
memset(cell_mask, 0, sizeof(cell_mask));

for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
        cin >> grid[i][j];
        if (grid[i][j] != 0) {
            int num = grid[i][j];
            int bit = 1 << (num - 1);
            // 验证合法性（题目保证输入合法，可选）
            if (row_mask[i] & bit || col_mask[j] & bit || cell_mask[i/3][j/3] & bit) {
                cout << -1 << endl;
                return 0;
            }
            // 更新掩码
            row_mask[i] |= bit;
            col_mask[j] |= bit;
            cell_mask[i/3][j/3] |= bit;
            // 累加初始分数
            initial_score += num * score[i][j];
        }
    }
}

步骤2：收集空格并优化搜索顺序

收集所有空格（grid[i][j] == 0），并按可选数字个数升序排序（优先填充分支少的空格，减少搜索树深度）：

struct Space {
    int x, y;
    int cnt; // 可选数字个数
    Space(int x, int y, int cnt) : x(x), y(y), cnt(cnt) {}
    bool operator<(const Space& other) const {
        return cnt < other.cnt;
    }
};

vector<Space> spaces;
for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
        if (grid[i][j] == 0) {
            // 计算可选数字个数
            int mask = row_mask[i] | col_mask[j] | cell_mask[i/3][j/3];
            int cnt = __builtin_popcount(~mask & 0x1ff); // 0x1ff是9位全1
            spaces.emplace_back(i, j, cnt);
        }
    }
}
sort(spaces.begin(), spaces.end());

步骤3：回溯搜索最大分数

递归填充空格，尝试所有合法数字，并通过剪枝提前终止无效分支：

int max_total = -1;

void backtrack(int idx, int current_score) {
    if (idx == spaces.size()) {
        max_total = max(max_total, current_score);
        return;
    }

    int x = spaces[idx].x;
    int y = spaces[idx].y;

    // 剪枝：当前分数 + 剩余空格最大可能分数（全填9）≤ 当前最优，直接返回
    int remaining_max = 0;
    for (int i = idx; i < spaces.size(); ++i) {
        remaining_max += 9 * score[spaces[i].x][spaces[i].y];
    }
    if (current_score + remaining_max <= max_total) {
        return;
    }

    // 计算可选数字
    int mask = row_mask[x] | col_mask[y] | cell_mask[x/3][y/3];
    for (int num = 1; num <= 9; ++num) {
        int bit = 1 << (num - 1);
        if (!(mask & bit)) {
            // 标记数字已用
            row_mask[x] |= bit;
            col_mask[y] |= bit;
            cell_mask[x/3][y/3] |= bit;

            // 递归填充下一个空格
            backtrack(idx + 1, current_score + num * score[x][y]);

            // 回溯：撤销标记
            row_mask[x] &= ~bit;
            col_mask[y] &= ~bit;
            cell_mask[x/3][y/3] &= ~bit;
        }
    }
}

步骤4：输出结果

调用回溯函数，输出最大分数（无解则为-1）：

backtrack(0, initial_score);
cout << max_total << endl;

四、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

struct Space {
    int x, y;
    int cnt;
    Space(int x, int y, int cnt) : x(x), y(y), cnt(cnt) {}
    bool operator<(const Space& other) const {
        return cnt < other.cnt;
    }
};

int grid[9][9];
int score[9][9];
int row_mask[9], col_mask[9], cell_mask[3][3];
int max_total = -1;
vector<Space> spaces;

void backtrack(int idx, int current_score) {
    if (idx == spaces.size()) {
        max_total = max(max_total, current_score);
        return;
    }

    int x = spaces[idx].x;
    int y = spaces[idx].y;

    int remaining_max = 0;
    for (int i = idx; i < spaces.size(); ++i) {
        remaining_max += 9 * score[spaces[i].x][spaces[i].y];
    }
    if (current_score + remaining_max <= max_total) {
        return;
    }

    int mask = row_mask[x] | col_mask[y] | cell_mask[x/3][y/3];
    for (int num = 1; num <= 9; ++num) {
        int bit = 1 << (num - 1);
        if (!(mask & bit)) {
            row_mask[x] |= bit;
            col_mask[y] |= bit;
            cell_mask[x/3][y/3] |= bit;

            backtrack(idx + 1, current_score + num * score[x][y]);

            row_mask[x] &= ~bit;
            col_mask[y] &= ~bit;
            cell_mask[x/3][y/3] &= ~bit;
        }
    }
}

int main() {
    // 预处理权值矩阵
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            int d = max(abs(i - 4), abs(j - 4));
            score[i][j] = 10 - d;
        }
    }

    // 读取数独并初始化
    int initial_score = 0;
    memset(row_mask, 0, sizeof(row_mask));
    memset(col_mask, 0, sizeof(col_mask));
    memset(cell_mask, 0, sizeof(cell_mask));
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] != 0) {
                int num = grid[i][j];
                int bit = 1 << (num - 1);
                if (row_mask[i] & bit || col_mask[j] & bit || cell_mask[i/3][j/3] & bit) {
                    cout << -1 << endl;
                    return 0;
                }
                row_mask[i] |= bit;
                col_mask[j] |= bit;
                cell_mask[i/3][j/3] |= bit;
                initial_score += num * score[i][j];
            }
        }
    }

    // 收集空格并排序
    spaces.clear();
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (grid[i][j] == 0) {
                int mask = row_mask[i] | col_mask[j] | cell_mask[i/3][j/3];
                int cnt = __builtin_popcount(~mask & 0x1ff);
                spaces.emplace_back(i, j, cnt);
            }
        }
    }
    sort(spaces.begin(), spaces.end());

    // 回溯搜索
    backtrack(0, initial_score);
    cout << max_total << endl;

    return 0;
}

五、复杂度分析

• 时间复杂度：最坏为$O(9^k)$（$k$为空格数），但通过搜索顺序优化和剪枝，实际效率极高（空格数≤67，且非零数字≥24，可在毫秒级完成）。
• 空间复杂度：$O(1)$（数独规模固定，额外空间仅用于存储空格列表和掩码）。

该方法通过回溯+剪枝+状态压缩，高效求解靶形数独的最高分数，完全适配题目数据范围。