#include <cstdlib>

using namespace std;


const int rozmerCtverce = 3;
const int rozmerHry = rozmerCtverce * rozmerCtverce;


bool pripustnaHodnota( const int sudoku[ rozmerHry ][ rozmerHry ],
                       const int radek,
                       const int sloupec)
{
    for( int i = 0; i<rozmerHry; i++)
    {        
        if( ( i != sloupec && sudoku[ radek ][i] == sudoku[radek][sloupec] ) ||
            ( i != radek && sudoku[ i ][sloupec] == sudoku[radek][sloupec] ) )
            return false;
    }
    int radekVeCtverci = (radek/rozmerCtverce)*rozmerCtverce;
    int sloupecVeCtverci = (sloupec/rozmerCtverce)*rozmerCtverce;
    for(int i=0 ; i < rozmerCtverce; i++ )
        for(int j=0 ; j < rozmerCtverce; j++ )
        {           
            if( ( radekVeCtverci + i ) != radek && 
                ( sloupecVeCtverci + j ) != sloupec &&
                sudoku[ radekVeCtverci + i ][sloupecVeCtverci + j ] == sudoku[radek][sloupec] )
                return false;
        }    
    return true;
}

bool krokVpred( int* radek, int* sloupec,
                const bool zadane[ rozmerHry ][ rozmerHry ] )
{    
    do
    {
        *sloupec++;
        if( *sloupec == rozmerHry )
        {
            *radek++;
            *sloupec = 0;
        }
        if( *radek == rozmerHry )
            return false;            
    }
    while( zadane[ *radek ][ *sloupec ] );
    return true;
}

bool resSudoku( int sudoku[ rozmerHry ][ rozmerHry ],
                bool zadane[ rozmerHry ][ rozmerHry ] )
{
    int sloupec = -1;
    int radek = 0;
    if( !krokVpred( &radek, &sloupec, zadane ) )
        return false;
    
    while(true)
    {
        do
        {
            sudoku [radek][sloupec]++;            
        }
        while( ! pripustnaHodnota(sudoku,radek,sloupec) &&
                 sudoku [radek][sloupec] <= rozmerHry);
        if(sudoku [radek][sloupec] == rozmerHry + 1){
            sudoku[radek][sloupec] = 0;
            if(!krokZpet(&radek, &sloupec, zadane))
                return false;
        }
        else
           if( ! krokVpred(&radek, &sloupec, zadane) )
               return true;
               
    }
}

int main(int argc, char** argv)
{
    int sudoku[ rozmerHry ][ rozmerHry ];
    bool zadane[ rozmerHry ][ rozmerHry ];

    for( int i = 0; i < rozmerHry; i++ )
        for( int j = 0; j < rozmerHry; j++ )
        {
            sudoku[ i ][ j ] = 0;
            zadane[ i ][ j ] = false;
        }
    
    /****
     * Zadani hry = zadani cisel a oznaceni zadanych pozic 
     * jako true v poli 'zadane'.
     */
    
    if( ! resSudoku( sudoku, zadane ) )
    {
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}