我的题解

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

const 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 row[9], col[9], block[9];
int cnt[512], num[512];
int sudoku[9][9];
int ans = -1;

inline int getBlock(int x, int y) {
return (x / 3) * 3 + y / 3;
}

void dfs(int step, int sum) {
if (step == 81) {
ans = max(ans, sum);
return;
}

int minChoices = 10, x = -1, y = -1;
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        if (sudoku[i][j] != 0) continue;
        int b = getBlock(i, j);
        int available = row[i] & col[j] & block[b];
        if (cnt[available] < minChoices) {
            minChoices = cnt[available];
            x = i;
            y = j;
        }
    }
}

if (x == -1) return;

int b = getBlock(x, y);
int available = row[x] & col[y] & block[b];

while (available) {
    int lowbit = available & -available;
    int val = num[lowbit];
    sudoku[x][y] = val + 1;
    row[x] ^= lowbit;
    col[y] ^= lowbit;
    block[b] ^= lowbit;
    
    dfs(step + 1, sum + (val + 1) * score[x][y]);
    
    row[x] ^= lowbit;
    col[y] ^= lowbit;
    block[b] ^= lowbit;
    sudoku[x][y] = 0;
    
    available ^= lowbit;
}

}

int main() {
// 初始化 lowbit 对应的数字
for (int i = 0; i < 9; i++) {
num[1 << i] = i;
}
// 初始化每个状态包含的 1 的个数
for (int i = 0; i < 512; i++) {
cnt[i] = __builtin_popcount(i);
}

// 初始时所有数字都可用
for (int i = 0; i < 9; i++) {
    row[i] = col[i] = block[i] = (1 << 9) - 1;
}

int filled = 0;
int totalScore = 0;
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        cin >> sudoku[i][j];
        if (sudoku[i][j] != 0) {
            int val = sudoku[i][j] - 1;
            int mask = 1 << val;
            row[i] ^= mask;
            col[j] ^= mask;
            block[getBlock(i, j)] ^= mask;
            totalScore += (val + 1) * score[i][j];
            filled++;
        }
    }
}

dfs(filled, totalScore);
cout << ans << endl;

return 0;

}