x，y，z 分别记录行，列和九宫格内已填数的集合
每次选可填数最少的格子进行扩展1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
const int n=9,N=10;
const int score[N][N]={{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
int ans=0,cnt=0,w[N][N],x[N],y[N],z[N],idx[1<<N];
int F(int u,int v){return (u-1)/3*3+(v+2)/3;}
int calc()
{
int ret=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ret=ret+w[i][j]*score[i][j];
return ret;
}
void dfs()
{
if (cnt==n*n)
{
ans=max(ans,calc());
return;
}
int u,v,sz=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if (!w[i][j])
{
int s=x[i]|y[j]|z[F(i,j)];
if (idx[s]<=idx[sz]) u=i,v=j,sz=s;
}
for(int i=1;i<=n;i++)
if ((sz>>(i-1))&1^1)
{
w[u][v]=i,cnt++;
x[u]|=1<<(i-1);
y[v]|=1<<(i-1);
z[F(u,v)]|=1<<(i-1);
dfs();
x[u]^=1<<(i-1);
y[v]^=1<<(i-1);
z[F(u,v)]^=1<<(i-1);
w[u][v]=0,cnt--;
}
}
int main()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&w[i][j]);
for(int s=0;s<(1<<n);s++)
for(int i=1;i<=n;i++)
idx[s]+=(s>>(i-1))&1^1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if (w[i][j])
{
int s=1<<(w[i][j]-1);
if ((x[i]|y[j]|z[F(i,j)])&s)
{
puts("0");
return 0;
}
x[i]|=s,y[j]|=s;
z[F(i,j)]|=s,cnt++;
}
dfs();
printf("%d\n",ans?ans:-1);
return 0;
}