#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

   
/*
 SODUKO SOLVER
 Author: bana, 2007, for program language course

 The program defines a class that takes the soduko sequence from keyboard or file.
 When the soduko is not valid it gives 81 zero values, otherwise the program uses
 the backtrack algorithm.

*/

typedef struct T{
       int e;     //value
       int w;     //writeable ?
} My_Struct;

class My_Soduko{
	public:
		My_Soduko();
		int Reading(char* fname,int type);
		My_Soduko( const My_Soduko& other );
		~My_Soduko();
		
	
		bool Row(int p);
        bool Column(int p);
        bool Square(int p);
        bool Checker(int pozicio);
		
        bool Is_it_valid();
        
        
        bool Solve();
		
        void Display();
		friend void Failed();
	private:
		My_Struct array[81];
};
      
int main(int argc, char *argv[])
{
       My_Soduko Just;
       if( 1 < argc ){ 
    		  Just.Reading(argv[1],1);      
       }else{
              Just.Reading(argv[0],2);
       }
       
       if( Just.Is_it_valid() ){
           if( Just.Solve() ) Just.Display();
           else Failed();
       }else Failed();
 
       //system("PAUSE");
       return EXIT_SUCCESS;
}


/* Constructor */
My_Soduko::My_Soduko()
{
}

/* Inputting .. */
int My_Soduko::Reading(char* fname,int type)
{       
        if( type == 1 ){
            
            ifstream inp( fname );
	        int tmp;
	        
	        if(inp.fail()){
                Failed();          
		        exit(1);
            }
            	     
            for(int i=0;i<81;i++){		
			  inp >> tmp;
			  
              if((!(0<=tmp && tmp <=9))){
                             Failed();          
		                     exit(1);
              }
			  
              array[i].e=tmp;
			  array[i].w=(tmp==0)?1:0;
	        }
	        
            inp.close();
	        
        }else if( type == 2 ){
             int tmp;
             for(int i=0;i<81;i++){		
			     cin >> tmp;
			     
                 if((!(0<=tmp && tmp <=9)) ){
                             Failed();          
		                     exit(1);
                 }
			     
                 array[i].e=tmp;
			     array[i].w=(tmp==0)?1:0;
              } 
         }  
}


/* Destructor */
My_Soduko::~My_Soduko()
{
   delete []array;
}

/* Is it soduko */
bool My_Soduko::Is_it_valid()
{
     for(int i=0;i<81;i++){
             if(array[i].e!=0){
                      Checker(i); 
                      if(!(Checker(i))) return 0; 
             }
     }
     return 1; 
}

/* Backtracking */
bool My_Soduko::Solve()
{
        int ind=0;  
        bool lehetetlen=false; 
        bool kesz=false;
     	
        while(!kesz && !lehetetlen) {                   
    	     do{
      	        if(array[ind].w) array[ind].e++;
             }while(!Checker(ind));
		
             if( array[ind].e==10 ) {
                 array[ind].e=0;
			     do {
				    ind--;				
				    if(ind<0) { lehetetlen=true; break; return 0;}
			     }while(!array[ind].w);
			//continue;
		     } else {

			     do {
				    ind++;
				    if(ind>80) { kesz=true; break; return 0; }
			     }while(!array[ind].w);
			//continue;
		     }
       }
       return 1;
}



/* Checking all conditions */
bool My_Soduko::Checker(int pos) {
     
	if( (Column(pos) && Square(pos)) && Row(pos) ) return 1;
	else return 0;
	
}



/* Checking minimatrix */
bool My_Soduko::Square(int p)
{
    int i,j,kezd,z;		
    kezd=p/9/3*3*9+(p%9)/3*3; // left top item in 3x3 mini matrix
	
	for(i=kezd;i<kezd+3;i++) {
		for(j=0;j<3;j++) {
			z=i+j*9;
			if(z==p)continue;  // do not check the same value
			if(array[p].e==array[z].e)return 0; 
		}
	}
	return 1;
}


/* Checking column */
bool My_Soduko::Column(int p)
{
   
  	int elso,i;	
	elso=p%9;
	
	for(i=elso;i<=elso+9*8;i+=9) {
		if( i==p )continue;  // do not check the same value
		if( array[p].e==array[i].e ) return 0;
	}
	return 1;
     
};

/* Checking row */
bool My_Soduko::Row(int p)
{

  	 int i,elso;
     elso=p/9*9;
	
    for(i=elso;i<elso+9;i++) {
		if(i == p )continue;   // do not check the same value
		if( array[p].e==array[i].e ) return 0;
	}
	return 1;        
};


/* Writing soduko sequence */
void My_Soduko::Display()
{
     for(int i=0;i<81;i++)
     {
       (i==80) ? cout << array[i].e : cout << array[i].e << " ";
     } 
}

/* Friend function for handling erros and writes 81 zeros */
void Failed()
{
     for(int i=0;i<81;i++)
     {
       (i==80) ? cout << "0" : cout << "0" << " ";
     } 
}

     
