考虑使用dfs解决此问题。但是需要注意优化。
使用 \(row_i,col_i,ceil_{i,j}\) 记录某行某列某个九宫中的可用数字。可以用二进制存储。然后对于一个格子 \((x,y)\)，\(row_x \text{ and } col_y\text{ and }ceil_{i,j}\)。每次dfs选择数最小的格子即可。
#include<bits/stdc++.h>
using namespace std;
using PII=pair<int,int>;
char s[100];
int row[9],col[9],ce[3][3],cur,mp[1<<9],ones[1<<9];
PII node[90];
bool flag;
int get(int a,int b){
return row[a]&col[b]&ce[a/3][b/3];
}
void dfs(int dep){
if(flag)return;
if(dep==cur+1){
printf("%s\n",s);
flag=1;
return;
}
int minv=10,a,b;
for(int i=0;i<9;++i)
for(int j=0;j<9;++j)
if(s[i*9+j]=='.'&&ones[get(i,j)]<minv){
a=i;
b=j;
minv=ones[get(i,j)];
}
for(int can=get(a,b);can;can-=can&-can){
int x=mp[can&-can];
row[a]-=1<<x;
col[b]-=1<<x;
ce[a/3][b/3]-=1<<x;
s[a*9+b]=x+'1';
dfs(dep+1);
row[a]+=1<<x;
col[b]+=1<<x;
ce[a/3][b/3]+=1<<x;
s[a*9+b]='.';
}
}
int main(){
for(int i=0;i<1<<9;++i)ones[i]=__builtin_popcount(i);
for(int i=0;i<9;++i)mp[1<<i]=i;
while(scanf("%s",s),s[0]!='e'){
for(int i=0;i<9;++i)row[i]=col[i]=(1<<9)-1;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)ce[i][j]=(1<<9)-1;
cur=flag=0;
int k=0;
for(int i=0;i<9;++i)
for(int j=0;j<9;++j){
int c=s[k++];
if(c!='.'){
c-='1';
row[i]-=1<<c;
col[j]-=1<<c;
ce[i/3][j/3]-=1<<c;
}
else ++cur;
}
dfs(1);
}
return 0;
}