//对于DFS搜索的题目，首先我们要确定搜索的顺序，即以什么样的搜索顺序可以将所有的状态都搜索出来
//然后，再去考虑剪枝优化。

//对于本道题目，我们可以将遍历每一个没有数值的位置，并向其放入数值作为DFS的搜索顺序
//遍历每一个位置(x, y)的时候我们都去统计该位置所处的行、列以及九宫格已经出现了哪些数字，
//然后任选一个没有重复的数字放入(x, y)这一位置。
//由于题目中已经指出，对于每一组数据而言，答案有且仅有一个，因此当遍历到某一个状态，
//该状态下所有位置上都放好数字时，即为正确答案，因此本题可以采用初始时空闲位置的个数cnt为搜索顺序，
//当cnt为0时，说明所有空位置都找到了适合自己的数字，即找到了正确答案。

//对于本道题的剪枝优化，首先想到的就是“优化搜索顺序”这一简直方法，
//即从分支较少的状态开始向后遍历，那么如何找到分支最少的状态呢？
//我们去统计某一状态的每一个子状态有多少个分支，优先向下遍历分支最少的那一个子状态
//其次，我们还可以采用“可行性剪枝”进行优化
//即当遍历到某一个空位置(x, y)时，该位置上不论放1~9哪一个数字，都会与所在行/列/九宫格内的数字产生重复，
//此时我们就可以直接回溯

//本道题除了剪枝优化外，还有一个很重要的优化方法——位运算优化
//当我们在统计某一空位置所在的行/列/九宫格有哪些已经存在的数字时，寻常方法就是次次都要去遍历行、列和九宫格
//但当我们采用了位运算之后，可以用二进制的方法，用九位的二进制数对每一行/列/九宫格内1~9出现的情况
//比如某一行元素是：1 . . 5 . 6 8 . 4，那么该行可用二进制(100111010)来标示出该行中1,4,5,6,8已经出现了
//从此，我们在遍历某一空位置，考虑该放置哪一个数字时，直接求该位置所在的行、列和九宫格的二进制状态表示的交集
//比如若某位置(x, y)所在行、列和九宫格二进制状态表示的交集结果为(100000001)，则说明我们只能放1或9在(x, y)位置上，
//此时我们还可以对上述方法进行进一步的优化：按照普通方法，要从交集结果中判断是哪些数可以用，
//通常就是把这个交集结果的二进制表示遍历一遍，找出每一个1所在的位置的值即为可用的数字，
//但如果我们对这种遍历也采用位运算方法进行优化的话，即使用lowbit()函数，时间复杂度可以再降一些，
//lowbit()的含义见笔记内容，每次lowbit()函数返回的值的以2为底的对数，即为交集结果的1所在的位置，即为可以放入到空位置上的数字
//因此为了能快速找回lowbit()返回值的对数，我们可以在最先构造的一个辅助数组map[x]，该数组存储的就是x的以2为底的对数

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 9, M = 1 << N;//1 << x --> 2^x
int map[M], ones[M];
int row[N], cal[N], cell[3][3];
char s[85];
//最最开始时，默认每一个位置都是空的，即每一行/列/九宫格内1~9的出现情况初始时都是：都没出现
//即都用(111111111)来初始表示1~9的出现情况。
void init()
{
    for(int i = 0; i < N; i ++) row[i] = cal[i] = M - 1;
    for(int i = 0; i < 3; i ++)
        for(int j = 0; j < 3; j ++)
            cell[i][j] = M - 1;
}
//辅助函数draw():当需要在某一个位置放置一个数时，或是由于回溯要清空某一位置的数时，
//就调用draw()这个函数。
void draw(int x, int y, int t, bool flag)
{
    if(flag == true)
        s[x * N + y] = t + '1';//为什么不能是'0'?????
    else
        s[x * N + y] = '.';

    int v = 1 << t;//v = 2^t
    if(flag == false) v = -v;
    //(x, y)这一位置所在的行/列/九宫格对应的关于1~9的出现情况需发生改变：
    row[x] -= v;
    cal[y] -= v;
    cell[x / 3][y / 3] -= v;
}
int lowbit(int x)
{
    return x & -x;
}
//通过get()函数可以得到对于位置(x, y)有哪些数字可以使用
int get(int x, int y)
{
    return row[x] & cal[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt)
{
    if(cnt == 0) return true;
    int minv = 10;
    int x, y;
    //遍历整个数独地图，找出拥有分支最少的空位置：
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
        {
            if(s[i * N + j] == '.')
            {
                int state = get(i, j);
                if(ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }
        }
    int state = get(x, y);//state保存的是对于(x, y)这一空位置来说，可用数字的情况（十进制表示）
    for(int i = state; i > 0; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if(dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }
    return false;
}
int main()
{
    //类似于哈希表，将i与2^i建立一一对应的关系
    for(int i = 0; i < N; i ++) map[1 << i] = i;
    //ones[i]存储的是[0, 2^9]中，每一个数的二进制表示里含有的1的个数
    for(int i = 0; i < M; i ++)//遍历[0, 2^9]中的每一个数
        for(int j = 0; j < N; j ++)//遍历i二进制表示的每一位
            ones[i] += i >> j & 1;//依次遍历i二进制表示的每一位是否为1

    while(cin >> s && s[0] != 'e')
    {
        init();
        int cnt = 0;
        for(int i = 0, k = 0; i < N; i ++)
            for(int j = 0; j < N; j ++, k ++)
            {
                if(s[k] != '.')
                {
                    int x = s[k] - '1';//为什么不能是'0'?????
                    draw(i, j, x, true);
                }
                else cnt ++;
            }
        dfs(cnt);
        puts(s);
    }
    return 0;
}