luogu P1074 靶形数独

比较基础的搜索剪枝题。。。。。

几个优化就可以过了

用lowbit代替查找可以填的数

用并集来维护什么数不能填

优先考虑 最小可能性的位置(讲道理我用堆维护还t了。。。。)

然后就可以在

$$

Ω（m{n2}）(n是数独大小，m是可以填的种类数量)解决

实际测试中，远远不到这个上界

$$

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

int a[15][15],tot=0,sum=0;
bool judge=false;
int q1[15],q2[15],q3[15],ans=(-1),cnt[100052];

int score[10][10]=
{{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 zhuan(int x,int y){
	return x/3*3+y/3;
}

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

int two[10002];

void getone(int x,int y,int k){
	q1[x]-=k;
	q2[y]-=k;
	q3[zhuan(x,y)]-=k;
}

void init(){
	for(int i=1,j=0;i<=2048;i=i*2,j++)two[i]=j;
	judge=false;
	
	for(int i=0;i<9;i++){
		q1[i]=q2[i]=q3[i] = ((1<<9)-1);
	}
	
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			if(a[i][j]==0){
				tot++;
				continue;
			}
				sum+=a[i][j]*score[i][j];
				int dx = a[i][j]-1;
				if(q1[i]&(1<<dx))q1[i]-=(1<<dx);
				if(q2[j]&(1<<dx))q2[j]-=(1<<dx);
				if(q3[zhuan(i,j)]&(1<<dx))q3[zhuan(i,j)]-=(1<<dx);
		}
	}
	for(int i=0;i<(1<<9)-1;i++){
		for(int j=i;j;j-=lowbit(j)){
			cnt[i]++;	
		}
	}
}

int solve(int rest,int cal){
	if(rest==0){
		ans = max(ans,cal);
		return 0;
	}
	int minl=15,xa,ya;
	
	
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			if(a[i][j]!=0)continue;
			int now = (q1[i]&q2[j]&q3[zhuan(i,j)]);
			if(cnt[now]<minl){
				minl=cnt[now],xa=i,ya=j;
			}
		}
	}
	
	
	
	int now = (q1[xa]&q2[ya]&q3[zhuan(xa,ya)]);
	while(now){
		int dy = lowbit(now); 
		a[xa][ya] = two[dy]+1;
		getone(xa,ya,dy);
		solve(rest-1,cal+score[xa][ya]*a[xa][ya]);
		getone(xa,ya,-dy);
		a[xa][ya] = 0;
		now = now-dy;
	}
	
}

int main(){
	for(int i=0;i<9;i++)
		for(int j=0;j<9;j++)cin>>a[i][j];
	init();
	solve(tot,sum);
	cout<<ans<<endl;
}