算法1
import java.io.*;
import java.util.Scanner;
public class Main {
public static int N=9,M=1<<N;//1<<1 <=>1x2=2 <=> 二进制数:10
//1<<9 <=> 1000000000
public static char[] st=new char[100];
public static int[] row=new int[N];//行
public static int[] col=new int[N];
public static int[][] cell=new int[3][3];
public static int[] ones=new int[M];
public static int[] map=new int[M];
public static void main(String[] args) throws IOException {
for(int i=0;i<1<<N;i++){
for(int j=0;j<N;j++){
ones[i]+=i>>j&1;//打表:每个二进制数有多少个1
}
}
for(int i=0;i<N;i++){
map[1<<i]=i;
}
Scanner scan=new Scanner(System.in);
while(scan.hasNext()){
st=scan.next().toCharArray();
if(st[0]=='e'){
break;
}
init();//初始化
//设置好一开始的row/col/cell数组。
//计算好有多少空位
int cnt=0;
for(int i=0,k=0;i<N;i++){
for(int j=0;j<N;j++,k++){
if(st[k]!='.'){
int t=st[k]-'1';//t表示所填的数字,也表示在二进制中的哪一位
draw(i,j,t,true);
}else {
cnt++;
}
}
}
if(dfs(cnt)){
System.out.println(new String(st));
}
}
}
public static boolean dfs(int cnt){
if(cnt==0){
return true;
}
//找能选的数最少的格子,①优化搜索顺序
int min_x=0;
int min_y=0;
int num=10;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(st[i*N+j]=='.'){
int res=get(i,j);
if(num>ones[res]){
num=ones[res];
min_x=i;
min_y=j;
}
}
}
}
//枚举这个格子可选的有哪些数
for(int i=get(min_x,min_y);i>=1;i-=lowbit(i)){
draw(min_x,min_y,map[lowbit(i)], true);
if (dfs(cnt-1)) return true;
draw(min_x,min_y,map[lowbit(i)],false );
}
return false;
}
public static int lowbit(int x){
return x&-x;
}
public static int get(int x,int y){
return row[x] & col[y] & cell[x/3][y/3];
}
public static void draw(int x,int y,int t,boolean is_set){
if(is_set){
st[x*N+y]=(char) (t+'1');
}else {
st[x*N+y]='.';
}
int v=1<<t;
if(!is_set){
v=-v;
}
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;
}
public static void init(){
for(int i=0;i<N;i++){
row[i]=col[i]=(1<<N)-1;
}
for(int i=0;i<3;i++){
for (int j=0;j<3;j++){
cell[i][j]=(1<<N)-1;
}
}
}
}