思路分析：

一：搜索顺序：

1：随便选择一个空白格
2：枚举该位置可以填的数，然后进入下一层递归

二：优化：

1：优化搜索顺序，每次选择可选择性最小的空白格
2：枚举某个位置可以填什么可以用位运算来进行

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int row[9], col[9], c[3][3];//用来判断行列九宫格哪些位置可用
char str[100];
int m[1<<9], ones[1<<9];//m用来结合lowbit用，ones用来统计有几位1

inline int lowbit(int x){
    return x & -x;
}

void init_ones(){
    for(int i = 0;i < 1 << 9;++i){
        int cnt = 0;
        for(int j = i;j > 0;j -= lowbit(j)) ++cnt;
        ones[i] = cnt;
    }
}

void init_m(){
    for(int i = 0;i < 9;++i) m[1 << i] = i;
}

void init_row_col_c(){
    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)
            c[i][j] = (1 << 9) - 1;
}

inline int get(int x, int y){
    return row[x] & col[y] & c[x/3][y/3];
}

bool dfs(int cnt){
    if(!cnt) {
        //cout << str << endl;
        return true;
    }
    int minv = 9;
    int x, y;
    for (int i = 0; i < 9; i ++ )
        for (int j = 0; j < 9; j ++ )
            if (str[i * 9 + j] == '.')
            {
                int t = ones[get(i, j)];
                if (t < minv)
                {
                    minv = t;
                    x = i, y = j;
                }
            }

    for(int i = get(x, y);i;i -= lowbit(i)){
        int t = m[lowbit(i)];
        row[x] -= 1 << t;
        col[y] -= 1 << t;
        c[x/3][y/3] -= 1 << t;
        str[x*9+y] = t + '1';

        if(dfs(cnt - 1)) return true;

        row[x] += 1 << t;
        col[y] += 1 << t;
        c[x/3][y/3] += 1 << t;
        str[x*9+y] = '.';
    }
    return false;
}

int main(){
    init_ones();
    init_m();
    while(cin >> str && strcmp(str, "end")){
        init_row_col_c();

        int cnt = 0;
        for(int i = 0;i < 9;++i)
            for(int j = 0;j < 9;++j)
                if(str[i*9+j] != '.'){
                    int t = str[i*9+j] - '1';
                    row[i] ^= 1 << t;
                    col[j] ^= 1 << t;
                    c[i/3][j/3] ^= 1 << t;
                }else ++cnt;

        dfs(cnt);
        cout << str << endl;
    }
    return 0;
}