P1074 靶形数独解题报告
无秒
2020-05-08 19:28:49
这题就是一个搜索，但是你要用上之前八皇后的技巧。因为这题每行，每列，每个宫格1-9只能出现一次，所以就拿一个数组h[i][j]代表i行j是否出现，而宫格其实用同样的方法，就加上一个差不多哈希函数的东东，9个宫格，可以从上到下，从左到右，依次编为1-9，那么可以被理解为x决定了基础数（3的倍数），然后加上y决定的数，为x/3 * 3+y/3.然后就开始搜索啊！
准备工作：输入时先判断是否为0，不是的话就把之前说的h数组给赋为1，否则num[i]++，这个数组是来记录有多少个未知数的，到后面搜索时会方便点。因为从未知数少的开始搜，那么树就会变小（毕竟可以搜的范围小了，而且玩数独玩多了都知道先从未知数小的下手），然后就OK了。
搜索：一个数记录已经搜了多少个点了，一个数记录此时的总分数，一个数表示剩余数的总和（用于最优化剪枝，当剩余数 * 9+已经有的总分数比记录的答案少的话，return），搜索就是从上到下，从左到右搜，假如这个已经有数了，那么直接把相应的数改变，进入下一个，否则就是枚举1-9然后搜索回溯就行。
代码：
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[10][10],ans=-1,fa[10],num[10];
bool hi[10][10],hj[10][10],hb[10][10];
const int v[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 getb(int x,int y){return x/3*3+y/3;}
bool cmp(int a,int b){return num[a]<num[b];}
void dfs(int cur,int sum,int la)
{
if(cur==81){ans=max(ans,sum);return;}
if(sum+9+la*9<=ans) return;
int i=fa[cur/9],j=cur%9,b=getb(i,j);
if(a[i][j]) dfs(cur+1,sum+a[i][j]*v[i][j],la-a[i][j]);
else
for(int k=1;k<=9;k++)
if(!hi[i][k]&&!hj[j][k]&&!hb[b][k])
{
hi[i][k]=hj[j][k]=hb[b][k]=true;
dfs(cur+1,sum+k*v[i][j],la-k);
hi[i][k]=hj[j][k]=hb[b][k]=false;
}
}
int main()
{
for(int i=0;i<9;i++) fa[i]=i;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
scanf("%d",&a[i][j]);
if(a[i][j])
hi[i][a[i][j]]=hj[j][a[i][j]]=hb[getb(i,j)][a[i][j]]=true;
else num[i]++;
}
sort(fa,fa+9,cmp);
dfs(0,0,405);
printf("%d",ans);
return 0;
}
```