算法

(搜索，剪枝) $O(9^{81})$

搜索顺序：依次枚举每个空格放哪个数字，枚举过程中维护当前所得分数。

在搜索时分别记录每行、每列、每个九宫格内当前未填写的数字有哪些。
这里采用位运算来加速：

1. 每行、每列、每个九宫格内，分别用一个9位的二进制数来表示哪些数字可填。
2. 每个空格内所有可选的数字就是其所在行、列、九宫格内可选数字的交集，这里直接将三个9位二进制数按位与(&)即可求出交集，然后通过lowbit运算可以快速枚举出所有是1的位。
3. 当填上某个数字时，将对应的行、列、九宫格的二进制状态的对应位置改成0即可；当回溯时，将对应的位置改成1即可。

另外还需要优化搜索顺序，每次选择分支最少的空格来枚举。

时间复杂度

最坏情况下需要枚举81个空格，每个空格有9种选择，因此最坏情况下的计算量是 $9^{81}$。

但由于剪枝的存在，实际搜索的空间远小于最坏情况。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
int g[N][N];
int ans = -1;

inline int lowbit(int x)
{
    return x & -x;
}

void init()
{
    for (int i = 0; i < N; i++) map[1 << i] = i;
    for (int i = 0; i < M; i++)
        for (int j = i; j; j -= lowbit(j))
            ones[i] ++;

    for (int i = 0; i < 9; i++) row[i] = col[i] = cell[i / 3][i % 3] = M - 1;
}

inline int get_score(int x, int y, int t)
{
    return (min(min(x, 8 - x), min(y, 8 - y)) + 6) * t;
}

inline void draw(int x, int y, int t)
{
    int s = 1;
    if (t > 0) g[x][y] = t;
    else
    {
        s = -1;
        t = -t;
        g[x][y] = 0;
    }

    t--;
    row[x] -= (1 << t) * s;
    col[y] -= (1 << t) * s;
    cell[x / 3][y / 3] -= (1 << t) * s;
}

inline int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

void dfs(int cnt, int score)
{
    if (!cnt)
    {
        ans = max(ans, score);
        return;
    }

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (!g[i][j])
            {
                int t = ones[get(i, j)];
                if (t < minv)
                {
                    minv = ones[get(i, j)];
                    x = i, y = j;
                }
            }

    for (int i = get(x, y); i; i -= lowbit(i))
    {
        int t = map[lowbit(i)] + 1;
        draw(x, y, t);
        dfs(cnt - 1, score + get_score(x, y, t));
        draw(x, y, -t);
    }
}

int main()
{
    init();

    int cnt = 0, score = 0;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j++)
        {
            int x;
            cin >> x;
            if (x)
            {
                draw(i, j, x);
                score += get_score(i, j, x);
            }
            else cnt++;
        }

    dfs(cnt, score);

    cout << ans << endl;

    return 0;
}