#include "ada.hh"


class Sudoku {

    int n;              // nombre de files i columnes
    matrix<int> Q;      // el sudoku
    matrix<boolean> F;  // F[i][c] = c Es lliure per fila i
    matrix<boolean> C;  // C[j][c] = c Es lliure per columna j
	matrix<boolean> S;	// S[k][c] = c Es lliure per al k-essim subquadrat

	void omplir()
	{
		for (int i=0; i<n; i++)
		{
			for (int j=0; j<n; j++)
			{
				if (Q[i][j]!=0)
				{
					F[i][Q[i][j]-1] = false;
					C[j][Q[i][j]-1] = false;
					S[j/3+(i/3)*3][Q[i][j]-1] = false;
				}
			}
		}
	}
	
	
	void recursiu (int cas) 
	{
        if (cas==n*n) 
		{ 
            for (int fil=0; fil<n; fil++)
			{
				for (int col=0; col<n;col++)
				{	
					cout << Q[fil][col];
					cout << " ";
				}
				cout << endl;
		}
		cout << endl;

        } 
		else 
		{
            int i = cas/n, j = cas%n;
			if (Q[i][j]==0)
			{
				for (int c=1; c<=n; ++c) 
				{
					if (F[i][c-1] and C[j][c-1] and S[j/3+(i/3)*3][c-1]) 
					{
						Q[i][j] = c;
						F[i][c-1] = C[j][c-1] = S[j/3+(i/3)*3][c-1] = false;
						recursiu(cas+1);
						F[i][c-1] = C[j][c-1] = S[j/3+(i/3)*3][c-1] = true;
					}  
				}   
			}
			else recursiu(cas+1);
		}
	 }        

public:

    Sudoku (int n) 
	{
        this->n = n;
         Q = matrix<int>(n,n);
		for (int i=0; i<n; i++)
			for (int j=0; j<n;j++)
				cin >> Q[i][j];
        F       = matrix<boolean>(n,n,true);
        C       = matrix<boolean>(n,n,true);
		S       = matrix<boolean>(n,n,true);
		omplir();
        recursiu(0);
    }
};



/** Programa principal **/

int main () 
{
   Sudoku sk(9);
}