#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std; 

bool b=true;

int m=10,kol =0;

int s[][9]={1,0,9,0,0,0,0,0,0
           ,0,0,0,0,0,8,7,0,2
           ,0,0,2,0,0,5,0,3,0
           ,0,0,0,0,0,0,9,2,8
           ,0,0,0,0,2,0,0,0,0
           ,0,0,0,7,5,4,0,0,0
           ,9,4,0,3,0,0,0,0,0
           ,0,0,0,1,0,0,0,6,4
           ,0,2,0,0,0,0,0,8,0};

int sudo[9][9][100]; 



class point{
    bool row_col(int f,int k)
    {
        for (int i=0;i<9;i++) if (sudo[i][y][k]==f) return false;
        for (int i=0;i<9;i++) if (sudo[x][i][k]==f) return false;
        return true;
    }

    bool subset(int f,int k)
    {
        if (x>=0 && x<=2 && y<=2 && y>=0) {for (int i=0;i<3;i++) for (int j=0;j<3;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=3 && x<=5 && y<=2 && y>=0) {for (int i=3;i<6;i++) for (int j=0;j<3;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=6 && x<=8 && y<=2 && y>=0) {for (int i=6;i<9;i++) for (int j=0;j<3;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=0 && x<=2 && y<=5 && y>=3) {for (int i=0;i<3;i++) for (int j=3;j<6;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=3 && x<=5 && y<=5 && y>=3) {for (int i=3;i<6;i++) for (int j=3;j<6;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=6 && x<=8 && y<=5 && y>=3) {for (int i=6;i<9;i++) for (int j=3;j<6;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=0 && x<=2 && y<=8 && y>=6) {for (int i=0;i<3;i++) for (int j=6;j<9;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=3 && x<=5 && y<=8 && y>=6) {for (int i=3;i<6;i++) for (int j=6;j<9;j++) if (sudo[i][j][k]==f) return false;}
        else if (x>=6 && x<=8 && y<=8 && y>=6) {for (int i=6;i<9;i++) for (int j=6;j<9;j++) if (sudo[i][j][k]==f) return false;}
        return true;
    }
public:

    int var[9];// массив вариантов

    int var_count;// количество вариантов
   
    int x,y; // координаты

    bool get_var(int k) // сбор вариантов
    {
        var_count=-1;
        if (sudo[x][y][k]) {var_count=10; return false;} else 
            for (int i=1;i<10;i++) 
                if (row_col(i,k)) if (subset(i,k)) {var_count ++;var[var_count] = i;}
        if (var_count==0) {
            sudo[x][y][k]=var[0];
            var_count=10;
            return true;
        }
        m=min(var_count,m);
        return false;
    }
};


point a[9][9];

 
 void pris(int k);
 bool end(int k);
 void recursion();
 void show(int k);
 void take_vars(int k);


int main ()
{
    setlocale(LC_ALL,"Russian");
    for (int i=0;i<9;i++)
        for (int j=0;j<9;j++){
            sudo[i][j][0]=s[i][j];
            a[i][j].x=i;
            a[i][j].y=j;
        }
    show(0);
    take_vars(0);
    show(0);
    recursion();
    return 0;
}




void pris(int k)
{
    for (int i=0;i<9;i++)
        for (int j=0;j<9;j++)
            sudo[i][j][k]=sudo[i][j][k-1];
}


bool end(int k)// проверка конца решения
{
    for (int i=0;i<9;i++)
        for (int j=0;j<9;j++)
            if (!sudo[i][j][k]) return false;
    return true;
}

void recursion() // рекурсия
{   
    pris(++kol);
    for (int i=0;i<9;i++)
        for (int j=0;j<9;j++){
            if (a[i][j].var_count==m) {
                b=true;
                for (int g=0;g<=m;g++){
                    pris(kol);
                    sudo[i][j][kol]=a[i][j].var[g];
                    show(kol);
                    take_vars(kol);
                    show(kol);
                    if (!b) break;
                    else if (end(kol)) {show(kol);return;}
                    recursion();
                }
            }
        }
}

void show(int k)// вывод на экран 
{
    for (int i=0;i<9;i++){
        cout << endl;
        if (i%3==0) cout << endl;
        for (int j=0;j<9;j++){
            cout << sudo[i][j][k] << ' ';
            if ((j+1)%3==0) cout << "  ";
        }
    }
    cout << endl << endl << endl;
}    


void  take_vars(int k) // получение вариантов
{
    m=10;
    for (int i=0;i<9;i++)
        for (int j=0;j<9;j++)
            if (a[i][j].get_var(k)) { take_vars(k); return;}
            else if (a[i][j].var_count==-1) {b=false;break;}
}