算法

dfs剪枝（位运算 + 搜索顺序优化）

按照每个格子中能填数字的个数搜索， 优先搜索个数最少的格子

开三个数组分别表示每行，每列， 每个九宫格里能填的数字。 用一个九位二进制数表示， 1是能填， 0是不能填， 搜索回溯时异或可以转变当前位置的数字

三个数组相与的结果即是一个格子能填的数字

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

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

int now;
int a[N][N];
int cnt[M], map[M];
int row[N], col[N], g[N];
int maxn = -1;

int gc(int x, int y) // 九宫格的下标，0~8
{
    return x / 3 * 3 + y / 3;
}

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

int get(int x, int y, int c) // a[x][y]的值在靶型数独中的值
{
    return (min(min(x, 8 - x), min(y, 8 - y)) + 6) * c;
}

void pd(int x, int y, int z) // 位置(x, y)填z + 1的状态转换，若能填，转为不能填，反之亦然
{
    row[x] ^= 1 << z;
    col[y] ^= 1 << z;
    g[gc(x, y)] ^= 1 << z;
}

void prework() // 预处理，将col, row, g数组都变为每一位为1的9位二进制数
               // map[i << N] 是二的i次幂所在的位置
               // cnt储存二进制下1的个数
{
    for (int i = 0; i < N; i ++ )
        map[1 << i] = i;

    for (int i = 0; i < 9; i ++ )
        row[i] = col[i] = g[i] = M - 1;

    for (int i = 0; i < 1 << 9; i ++ )
        for (int j = i; j; j -= lowbit(j))
            cnt[i] ++ ;
}

void dfs(int now, int score)
{
    if (!now) // 若所有能填的位置都填完，维护最大值，返回
    {
        maxn = max(score, maxn);
        return ;
    }

    int x, y;
    int minn = 10;

    // 寻找当前可填数字最少的空位置
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if(!a[i][j])
            {
                int s = row[i] & col[j] & g[gc(i, j)];
                int t = cnt[s];
                if (t < minn)
                {
                    minn = t;
                    x = i; y = j;
                }
            }

    // 枚举该位置上能填的每一位
    for (int s = row[x] & col[y] & g[gc(x, y)]; s; s -= lowbit(s))
    {
        int c = lowbit(s);
        pd(x, y, map[c]);
        a[x][y] = map[c] + 1;
        dfs(now - 1, score + get(x, y, map[c] + 1));
        a[x][y] = 0;
        pd(x, y, map[c]);
    }
}

int main()
{
    prework();
    int ans = 0;
    for (int i = 0; i < 9; i ++ )
        for (int j = 0; j < 9; j ++ )
        {
            int x; scanf("%d", &x);
            if (x)
            {
                a[i][j] = x;
                pd(i, j, x - 1);
                ans += get(i, j, x);
            }
            else now ++ ;
        }
    // puts("\nstop\n");
    dfs(now, ans);
    printf("%d", maxn);

    return 0;
}