DFS剪枝
1. 选择分支最小的格子进行扩展
2. 使用位运算， 0 表示不能使用， 1表示可以使用。 行、列、单元格内相与不能为0的数就能用。

import java.io.*;
import java.util.*;
class Main{

    static int N = 9, M = 1 << N;
    static char[][] a = new char[N][N];
    static int[] row = new int[N], col = new int[N];
    static int[][] cell = new int[3][3];
    static Map<Integer, Integer> map = new HashMap();
    static Map<Integer, Integer> umap = new HashMap();
    static int[] one = new int[M];
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void init(){
        int x, res;
        for(int i = 1; i < M; i++){
            x = i;
            res = 0;
            while(x != 0){
                res++;
                x -= lowBit(x);
            }
            one[i] = res;
        }

        for(int i = 1; i <= N; i++) {
            map.put(i, 1 << (i - 1) );
            umap.put(1 << (i - 1), i);
        }

        Arrays.fill(row, (1 << N) - 1);
        Arrays.fill(col, (1 << N) - 1);
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                cell[i][j] = (1 << N) - 1;
            }
        }
    }

    public static int lowBit(int x){
        return x & -x;
    }
    public static void main(String[] args) throws Exception{
        while(true){
            String s = read.readLine();
            if("end".equals(s)) break;
            int idx = 0, cnt = 0;
            init();
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    char c = s.charAt(idx++);
                    a[i][j] = c;
                    if(c != '.'){
                        draw(i, j, c - '0', true);
                    }else cnt++;
                }
            }
            dfs(cnt);
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    log.write(a[i][j]);
                }
            }
            log.write("\n");

        }
        log.flush();

    }

    public static void draw(int x, int y, int num, boolean draw){
        int digit = map.get(num);
        if(draw) a[x][y] = (char)(num + '0');
        else {
            a[x][y] = '.';
            digit = -digit;
        }
        row[x] -= digit;
        col[y] -= digit;
        cell[x / 3][y / 3] -= digit;
    }

    public static boolean dfs(int cnt){
        if(cnt == 0)    return true;
        int x = 0, y = 0, minV = 10, and = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(a[i][j] == '.'){
                    int na = row[i] & col[j] & cell[i / 3][j / 3];
                    if(one[na] < minV){
                        minV = one[na];
                        and = na;
                        x = i;
                        y = j;
                    }
                }
            }
        }

        while(and != 0){
            int lowBit = lowBit(and);
            int num = umap.get(lowBit);
            draw(x, y, num, true);
            if(dfs(cnt - 1)) return true;
            draw(x, y, num, false);
            and -= lowBit;
        }
        return false;
    }

}