洛谷P1074 靶形数独

https://www.luogu.org/problemnew/show/P1074

这道题单独以每个位置递归纯暴力搜索的话，复杂度9^81，考虑剪枝，和八皇后类似，在同一行同一列同一宫则不能放。另外，想象解答树，先搜索情况少的位置和先搜索情况多的位置总结点数是一样的，不一样的地方在于先搜情况少的的话，靠近树根的分叉少，靠近枝叶稠密，若先搜情况多的，则树根处稠密，枝叶稀疏。考虑剪枝，显然先搜索情况少的，容易很快剪掉很大的一棵棵子树，先搜情况多的则达不到这样的效果。因此按每行的空位排序，空位少的行优先搜索，显然在实际玩数独游戏时，也是这样的方法。

这题写的遇到了很多的曲折。

先是想着以一行为单位，递归9次，但显然，这样的思路是没有办法写出代码的。

改变思路以一格为单位，递归81次，又想到了一个贪心，越靠近中间分数越高，那就优先填大数字，等到搜索到第一组可行解时，就把它作为最优解，但显然，以及一般情况下，这样的贪心都是大错特错的。

然后用先搜索冲突少的地方的方法来写，对于整个9*9方阵按每个点行列宫已有数排序，设置好搜索完每一个点后的下一个点，写了120+行，TLE得很惨。原因是：假如每一行有5个空位，按上面的方法，先搜一下这里，下次跳到很远的地方搜一下，右跳到别处...而这样几次没有相互干扰，这样不利于剪枝。

因此，最后策略：按每行的空位排序，空位少的行优先搜索这一行，这一行搜索完才搜索其他行。在实际玩数独游戏时也是这样的方法。

交上去RE，结果是因为在函数里面定义的数组并不赋初值0，使用里面的值越界了，把它当全局变量用了...

改了以后终于AC了。

#include<bits/stdc++.h>
using namespace std;

int n=9,a[10][10],num[10][10],ans=-1;
int row[10][10],col[10][10],block[10][10];
int nxt[10],hang[10];

const int score[10][10]=
{{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}};

inline int Block(int i,int j){return (i-1)/3*3+(j-1)/3+1;}

bool cmp(int i,int j)
{
	return hang[i]>hang[j];
}

void init()
{
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		scanf("%d",&a[i][j]);
		if(a[i][j])
		{
			hang[i]++;
			row[i][a[i][j]]=1;
			col[j][a[i][j]]=1;
			block[Block(i,j)][a[i][j]]=1;
		}
	}
	
	int d[10]={0};for(int i=1;i<=n;i++)d[i]=i;
	sort(d+1,d+1+n,cmp);
	for(int i=0;i<n;i++)nxt[d[i]]=d[i+1];
}

void search(int r,int c,int tot)
{
	if(!r){ans=max(ans,tot);}
	else if(a[r][c])
	{
		if(c+1<=n)search(r,c+1,tot+a[r][c]*score[r][c]);
		else search(nxt[r],1,tot+a[r][c]*score[r][c]);
	}
	else for(int i=9;i>=1;i--)
	{
		if(row[r][i]||col[c][i]||block[Block(r,c)][i])continue;
		row[r][i]=col[c][i]=block[Block(r,c)][i]=1;
		num[r][c]=i;
		if(c+1<=n)search(r,c+1,tot+num[r][c]*score[r][c]);
		else search(nxt[r],1,tot+num[r][c]*score[r][c]);
		row[r][i]=col[c][i]=block[Block(r,c)][i]=0;
	}
}

int main()
{
	freopen("input.in","r",stdin);
	init();
	search(nxt[0],1,0);
	printf("%d\n",ans);
	//debug();
	return 0;
}