#include <iostream>
#include <algorithm>
#include <iterator>
#include <queue>
#include <set>

#define sudoku_t int

using namespace std;

class CSudoku
{
    private:
        sudoku_t m_table[3][3][3][3];
        set<sudoku_t> m_cant[3][3][3][3];       

    public:
        CSudoku(istream& in);
       
        void            set_p_table(int i, int j, sudoku_t t);
        sudoku_t&       p_table(int i, int j) { return m_table[i/3][j/3][i%3][j%3]; };
        set<sudoku_t>&  p_cant (int i, int j) { return m_cant[i/3][j/3][i%3][j%3]; };
        bool            solve(int progres);
   
};

CSudoku::CSudoku(istream& fin)
{
    sudoku_t t;
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++)
        {
            fin>>t;
            if (t<0 || t>9) {
                cout<<"Nepravilan SU-DO-KU format fajla :("<<endl;
                cout<<"Ucitana vrijednost je: "<<t<<" a dozvoljeni su brojevi od 0-9"<<endl;
                exit(-2);
            }
           
            set_p_table(i,j,t); 
        }
    }
}

void CSudoku::set_p_table(int i, int j, sudoku_t t) {
    int bigi = i/3;
    int bigj = j/3;
    int smai = i%3;
    int smaj = j%3;
   
    m_table[bigi][bigj][smai][smaj] = t;
    if (t == 0)
        return;
           
    for (int ii=0; ii<9; ii++)
    {   // postavljanje uspravno i vodoravno
        if (ii != i) {
            set<int>& g = p_cant(ii,j);
            g.insert(t);
        }
       
        if (ii != j) {
            set<int>& g = p_cant(i,ii);
            g.insert(t);
        }
    }
    // postavljanje kocke
    for (int ii=0; ii<3; ii++)
        for (int jj=0; jj<3; jj++)
            if (ii!=smai && jj!=smaj)
                m_cant[bigi][bigj][ii][jj].insert(t);
}

ostream& operator<<(ostream& os, CSudoku& s ) {
    os<<"------------------"<<endl;
    for (int i=0; i<9; i++, os<<endl)
        for (int j=0; j<9; j++)
            os<<s.p_table(i,j)<<" ";
   
    os<<"------------------";
    return os;
}

bool CSudoku::solve(int progres) {
    int fi = progres/9;
    int fj = progres%9;
   
    //cout<<*this<<endl;
   
    for (int i=fi; i<9; i++) {
        int j;
        if (i==fi)
            j=fj;
        else
            j=0;
        for(; j<9; j++) {
            if (p_table(i,j) == 0) {
                // NASHAO SAM PRAZNO POLJE:
                // URADITI ITERACIJE
                int child_progres = i*9+j;           
                set<sudoku_t>& cant = p_cant(i,j);
               
                for (int m=1; m<=9; m++) {
                    if (cant.find(m) == cant.end()) {
                        CSudoku child(*this);
                        child_progres;
                        child.set_p_table(i,j,m);
                        if (child.solve(child_progres)) {
                            *this = child;
                            return true;   
                        } else {
                            continue;   // slijedeci m broj
                        }
                    }
                }
                // ne moze niti jedan broj
                return false;
            }
        }
    }
    return true;
}

void print_help() {
    cout<<"\tProgram koristi samo stdin i stdout."<<endl;
    cout<<"\tPrimjer:"<<endl;
    cout<<"\t\t./sudoku < fajlsamapom.txt > rezultat.txt"<<endl;
    cout<<endl;
    cout<<"\tOvu poruku mozete vidjeti ako pokrenete"<<endl;
    cout<<"\t\t./sudoku --help"<<endl;
    cout<<"\tMoguce je staviti --silent kao argument, onda program"<<endl;
    cout<<"\tispisuje *samo* rijeshenje, ovo koristi supyku program"<<endl;
    cout<<endl;
    cout<<"\tDakle, koristite redirekciju za rad sa fajlovima"<<endl;
    cout<<"\tProgram inace ne uzima argumente, osim ako ga ne poziva"<<endl;
    cout<<"\tsupyku program (interfejs uradjen u pygtk za linux, odnosno"<<endl;
    cout<<"\tu vb-u za windows)."<<endl;
}

int main(int argc, char** argv)
{
    bool silent = false;    // da li ispisuje 'proces'
    if (argc==1) {
        // nema argumenata ? valjda koristenje iz konzole
    } else if (argc==2) {
        string arg = string(argv[1]);
        if (arg == "--silent")
            silent = true;
        else if (arg == "--help") {
            print_help();
            return -1;
        } else {
            print_help();
            return -3;
        }
    } else {
        print_help();
        return -2;
    }
   
    CSudoku sudo(cin);
    if (!silent)
        cout<<sudo<<endl<<"Iteracija u toku ..."<<endl;

    if (sudo.solve(0)) {
        if (!silent)
            cout<<"Rijeshenje:"<<endl;
       
        cout<<sudo<<endl;
    } else {
        if (!silent)
            cout<<"Nema rijeshenja :/ :( :P :O"<<endl;
        return 1;
    }   
    //sudo.print_cant(cout);
    if (!silent)   
        cout<<"\tKraj, (C) che.guevara"<<endl;
    return 0;
}