123123

#include<stdio.h>

int map[11][11];
int hang_hash[11][11];
int lie_hash[11][11];
int box[11][11];
int shudu[11][11] = {{0},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},    
    {0,7,7,7,8,8,8,9,9,9},    
    {0,7,7,7,8,8,8,9,9,9},    
    {0,7,7,7,8,8,8,9,9,9},
};
bool dfs(int hang, int lie)
{
    if(map[hang][lie] != 0)
    {
        if(lie == 9)
        {
            if(hang == 9)
                return 1;
            if(dfs(hang + 1, 1) == 1)
                return 1;
        }
        else
        {
            if(dfs(hang, lie + 1) == 1)
                return 1;
        }
        return 0;
    }
    int i, j;
//    int b = get_box(hang, lie);
    int b = shudu[hang][lie];
    for(i = 1; i <= 9; i++)
    {
        if(hang_hash[hang][i] == 0 && lie_hash[lie][i] ==0 && box[b][i] == 0)
        {
            map[hang][lie] = i;
            hang_hash[hang][i] = 1;
            lie_hash[lie][i] = 1;
            box[b][i] = 1;
            if(lie == 9)
            {
                if(hang == 9)
                    return 1;
                if(dfs(hang + 1, 1) == 1)
                    return 1;
            }
            else
            {
                if(dfs(hang, lie + 1) == 1)
                    return 1;
            }
            map[hang][lie] = 0;
            hang_hash[hang][i] = 0;
            lie_hash[lie][i] = 0;
            box[b][i] = 0;
        }
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int i, j;
        for(i = 0; i < 11; i++)
        {
            for(j = 0; j < 11; j++)
            {
                map[i][j] = hang_hash[i][j] = lie_hash[i][j] = box[i][j] = 0;
            }
        }
        for(i = 1; i <= 9; i++)
        {
            for(j = 1; j <= 9; j++)
            {
                scanf("%d", &map[i][j]);
                if(map[i][j] != 0)
                {
            //        int b = get_box(i, j);
                    int b = shudu[i][j];
                    hang_hash[i][map[i][j]] = 1;
                    lie_hash[j][map[i][j]] = 1;
                    box[b][map[i][j]] = 1;
                }
            }
        }
        dfs(1, 1);
        for(i = 1; i<= 9; i++)
        {
            for(j = 1; j <= 9; j++)
            {
                printf("%d ", map[i][j]);
            }
            printf("
");
        }
    }
    return 0;
}