题解

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

// 靶形分值表（从外到内，实际按行列索引计算）
int score[9][9] = {
    {6, 6, 6, 6, 6, 6, 6, 6, 6},
    {6, 7, 7, 7, 7, 7, 7, 7, 6},
    {6, 7, 8, 8, 8, 8, 8, 7, 6},
    {6, 7, 8, 9, 9, 9, 8, 7, 6},
    {6, 7, 8, 9, 10, 9, 8, 7, 6},
    {6, 7, 8, 9, 9, 9, 8, 7, 6},
    {6, 7, 8, 8, 8, 8, 8, 7, 6},
    {6, 7, 7, 7, 7, 7, 7, 7, 6},
    {6, 6, 6, 6, 6, 6, 6, 6, 6}
};

int grid[9][9];           // 数独棋盘
int row[9], col[9], box[9]; // 位掩码：行、列、九宫格
int maxScore = -1;        // 最高分
int emptyCount = 0;       // 空格数
vector<pair<int, int>> emptyCells; // 空格位置

// 获取九宫格索引
inline int getBox(int i, int j) {
    return (i / 3) * 3 + j / 3;
}

// 深度优先搜索
void dfs(int idx, int currentScore) {
    if (idx == emptyCount) {
        maxScore = max(maxScore, currentScore);
        return;
    }
    
    // 找候选数最少的空格（剪枝优化）
    int minCandidates = 10, bestIdx = -1;
    int bestX, bestY;
    for (int k = idx; k < emptyCount; k++) {
        int x = emptyCells[k].first, y = emptyCells[k].second;
        int candidates = row[x] & col[y] & box[getBox(x, y)];
        int count = __builtin_popcount(candidates);
        if (count < minCandidates) {
            minCandidates = count;
            bestIdx = k;
            bestX = x; bestY = y;
        }
    }
    
    if (minCandidates == 0) return; // 无解
    
    // 交换到当前位置
    swap(emptyCells[idx], emptyCells[bestIdx]);
    int x = emptyCells[idx].first, y = emptyCells[idx].second;
    int boxIdx = getBox(x, y);
    int candidates = row[x] & col[y] & box[boxIdx];
    
    // 尝试所有候选数字
    for (int num = 1; num <= 9; num++) {
        if (candidates & (1 << (num - 1))) {
            // 放置数字
            grid[x][y] = num;
            row[x] ^= (1 << (num - 1));
            col[y] ^= (1 << (num - 1));
            box[boxIdx] ^= (1 << (num - 1));
            
            // 递归搜索
            dfs(idx + 1, currentScore + num * score[x][y]);
            
            // 回溯
            grid[x][y] = 0;
            row[x] ^= (1 << (num - 1));
            col[y] ^= (1 << (num - 1));
            box[boxIdx] ^= (1 << (num - 1));
        }
    }
    
    // 恢复位置
    swap(emptyCells[idx], emptyCells[bestIdx]);
}

int main() {
    // 初始化位掩码（全1表示所有数字可用）
    for (int i = 0; i < 9; i++) {
        row[i] = col[i] = box[i] = (1 << 9) - 1;
    }
    
    int baseScore = 0;
    
    // 读入数独
    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];
                baseScore += num * score[i][j];
                // 更新约束
                row[i] ^= (1 << (num - 1));
                col[j] ^= (1 << (num - 1));
                box[getBox(i, j)] ^= (1 << (num - 1));
            } else {
                emptyCells.push_back({i, j});
            }
        }
    }
    
    emptyCount = emptyCells.size();
    
    // 深度优先搜索
    dfs(0, baseScore);
    
    cout << maxScore << endl;
    return 0;
}