难点是如何实现每次都搜索分支数最少的?
y总这里实现了一种很妙的方法
利用二进制表示每行每列每个九宫格的状态交后计数即可
#include<iostream>
#include<cstring>
using namespace std;
const int N=9,M=1<<N;
int count[M],map[M];
int ha[N],le[N],col[3][3];
char sta[100];
int cnt;
int lowbit(int x)
{
return x&-x;
}
int get(int x,int y)
{
return ha[x]&le[y]&col[x/3][y/3];
}
void draw(int x,int y,int t,bool falg)
{
if(falg)sta[x*N+y]=t+'1';
else sta[x*N+y]='.';
int v;
if(falg)v=1<<t;
else v=-1<<t;
ha[x]-=v;
le[y]-=v;
col[x/3][y/3]-=v;
}
bool dfs(int sum)
{
if(sum==0)return true;
int miv=10,x,y;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(sta[i*N+j]=='.')
{
int tt=get(i,j);
if(count[tt]<miv)
{
x=i,y=j;
miv=count[tt];
}
}
}
int tt=get(x,y);
for(int i=tt;i;i-=lowbit(i))
{
int t=map[lowbit(i)];
draw(x,y,t,true);
if(dfs(sum-1))return true;
draw(x,y,t,false);
}
return false;
}
void init()
{
for(int i=0;i<N;i++)ha[i]=le[i]=(1<<N)-1;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
col[i][j]=(1<<N)-1;
}
int main()
{
for(int i=0;i<N;i++)map[1<<i]=i;
for(int i=0;i<1<<N;i++)
{
for(int j=0;j<N;j++)
{
if(i>>j&1)count[i]+=1;
}
}
while(cin>>sta,sta[0]!='e')
{
init();
int cnt=0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(sta[i*N+j]!='.')
{
int t=sta[i*N+j]-'1';
draw(i,j,t,true);
}
else cnt++;
}
dfs(cnt);
cout<<sta<<endl;
}
return 0;
}