假装自己会了:)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=9,M=1<<N;
int ones[M],map[M];//ones保存的是0~2^9 每一个数包含多少个1 map存每一位二进制位代表数字几
int row[N],col[N],cell[3][3];//分别用来记录每一行每一列 每一个小方格的状态 每一位都是一个二进制数 比如row[0]=010101100 表示第0行2 4 6 7可以填
char str[100];
void init()
{
for(int i=0;i<N;i++) row[i]=col[i]=(1<<N)-1;//每一位都初始化为1表示没有填数
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cell[i][j]=(1<<N)-1;
}
void draw(int x,int y,int t,bool is_set){//表示在[x,y]位置上填一个数字t 用is_set表示在[x,y]位置填一个数还是删去
if(is_set) str[x*N+y]='1'+t;//t是0~8
else str[x*N+y]='.';
/*其实这里就是如果选了某个数,我们就应该修改行和列以及每个小方块的该数所在位置的状态
因为1表示该数没有用过,既然我们用了 就应该将这个数所在的位置修改为0
比如是2 那么2所在的位置其实是 1<<1(t从0开始的原因也是如此)=10 (2进制)
将row[x]减去10(2进制) 其实就是将x行2 所在的位置变成了0
如果没有选 取反即可
*/
int v=1<<t;
if(!is_set) v=-v;//取反就是将0变成1
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;
}
int lowbit(int x){
return x&-x;
}
int get(int x,int y){//求x,y这个格子上能填哪些数
return row[x]&col[y]&cell[x/3][y/3];
}
bool dfs(int cnt){
if(!cnt) return true;
int minv=10;
int x,y;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(str[i*N+j]=='.'){//没有填数的时候才枚举
int state=get(i,j);//得到[i,j]位置上能填的数的状态
if(ones[state]<minv){//找到一个1 的个数最小的 即选择分支最小
minv=ones[state];
x=i,y=j;
}
}
}
}
int state=get(x,y);//得到分支最小的二进制数
for(int i=state;i;i-=lowbit(i)){//枚举这个二进制数的一的个数
int t=map[lowbit(i)];//得到二进制数的每一位1代表的数字
draw(x,y,t,true);//填这个数
if(dfs(cnt-1)) return true;//填的话 空格数量减一
draw(x,y,t,false);//回溯
}
return false;
}
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++)
ones[i]+=i>>j&1;
while(cin>>str,str[0]!='e'){
init();
int cnt=0;//表示空格的数量
for(int i=0,k=0;i<N;i++){
for(int j=0;j<N;j++,k++){
if(str[k]!='.'){
int t =str[k]-'1';
draw(i,j,t,true);
}
else cnt++;
}
}
dfs(cnt);
puts(str);
}
return 0;
}