一道比普通数独难度大的搜索题,但思路基本一致(采用yxc大佬的二进制预处理法),先预处理,再搜索
时间复杂度
C++ 代码
#include<bits/stdc++.h>
#define N 9
using namespace std;
int Map[N][N],score[N][N];
int tot[1<<N],f[1<<N],cnt,ans;//tot数组记录每一个数二进制下有几个一(即表示可以填的数的个数
//f数组用于将二进制数转换为十进制数,cnt记录有地方需要填充
int a[N],b[N],c[N];
inline int lowbit(int i)
{
return (i&(-i));
}
inline void init(int x,int y,int k)//预处理每一行,每一列,每一个3*3小方格已有的数字
{
a[x]^=(1<<k);
b[y]^=(1<<k);
c[x/3*3+y/3]^=(1<<k);
}
inline void Init()预处理
{
tot[0]=0;
for(int i=1;i<(1<<9);i++)
tot[i]=tot[i-lowbit(i)]+1;
for(int i=0;i<9;i++){
f[1<<i]=i;
a[i]=b[i]=c[i]=(1<<9)-1;
}
}
void dfs(int now){
if(!now){//搜索完成
int ans_now=0;//计算当前方案的分数和
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
ans_now+=Map[i][j]*score[i][j];
ans=max(ans,ans_now);//更新答案
return;
}
int MAX=10,x,y;
for(int i=0;i<9;i++)//优先搜序可能性小的点
for(int j=0;j<9;j++)
if(!Map[i][j]){
int sum=(a[i]&b[j]&c[i/3*3+j/3]);//该位置上可以填的数的集合(二进制)
if(tot[sum]<MAX){
MAX=tot[sum];
x=i,y=j;
}
}
int num=(a[x]&b[y]&c[x/3*3+y/3]);
while(num){
int sum=f[lowbit(num)];
Map[x][y]=sum+1;
init(x,y,sum);
dfs(now-1);
init(x,y,sum);
Map[x][y]=0;
num-=lowbit(num);//排除当前的可能性
}
}
int main()
{
//freopen("sudoku.in","r",stdin);
//freopen("sudoku.out","w",stdout);
Init();
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
scanf("%d",&Map[i][j]);
if(Map[i][j])
init(i,j,Map[i][j]-1);//二进制储存时需减一
else
cnt++;//记录有几个空需填
if(i==4&&j==4)//以下为记录分数
score[i][j]=10;
else if(i>=3&&i<=5&&j>=3&&j<=5)
score[i][j]=9;
else if(i>=2&&i<=6&&j>=2&&j<=6)
score[i][j]=8;
else if(i>=1&&i<=7&&j>=1&&j<=7)
score[i][j]=7;
else
score[i][j]=6;
}
dfs(cnt);
if(!ans)
printf("-1\n");
else
printf("%d\n",ans);
return 0;
}