/* ------------------------------------------------------------------ */
/* Benchmark na praci s celociselnymi poli:                           */
/* reseni Sudoku metodou brute-force                                  */
/*                                                                    */
/* Autor: Pavel Tisnovsky                                             */
/* ------------------------------------------------------------------ */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ODDELOVAC puts("+--------+--------+--------+");



/* vstupni data: */
/* 1-9 znama hodnota */
/* 0   neznama hodnota (prazdne policko) */
const int src[9][9]={
     {5, 6, 9,   0, 0, 7,   2, 1, 8},
     {7, 0, 2,   0, 0, 1,   0, 3, 0},
     {1, 3, 8,   9, 2, 0,   4, 0, 0},
                            
     {0, 0, 7,   2, 0, 9,   6, 5, 0},
     {0, 0, 4,   0, 0, 5,   8, 9, 3},
     {9, 0, 0,   8, 6, 0,   0, 4, 0},
                            
     {8, 0, 0,   6, 1, 0,   3, 0, 0},
     {4, 1, 0,   3, 9, 2,   0, 0, 0},
     {2, 0, 0,   0, 5, 8,   1, 0, 4}
};

/* pracovni matice */
int wrk[9][9];

/* matice obsahujici povolene hodnoty pro kazde policko */
int povol[9][9][9];

/* pomocna matice s minimalni povolenou hodnotou pro kazde policko */
int minim[9][9];



/* ------------------------------------------------------------------ */
/* Snizeni poctu moznych kombinaci zjistenim duplicit ve sloupcich    */
/* ------------------------------------------------------------------ */
void testSloupce0(void)
{
    int radek, sloupec;
    int cifry[9], cifra;
    int i;
    for (sloupec=0; sloupec<9; sloupec++) {
        for (i=0; i<9; i++)
            cifry[i]=0;
        /* projdi vsechny bunky v radku a zjisti zapsana cisla */
        for (radek=0; radek<9; radek++) {
            cifra=src[radek][sloupec];
            if (cifra>0) { /* obsad cifru */
                cifry[cifra-1]=1;
            }
        }
        /* v matici povol zmen cely radek */
        for (radek=0; radek<9; radek++) {
            if (src[radek][sloupec]==0) {
                for (i=0; i<9; i++) {
                    if (cifry[i])
                        povol[radek][sloupec][i]=0;
                }
            }
        }
    }
}



/* ------------------------------------------------------------------ */
/* Snizeni poctu moznych kombinaci zjistenim duplicit na radcich      */
/* ------------------------------------------------------------------ */
void testRadku0(void)
{
    int radek, sloupec;
    int cifry[9], cifra;
    int i;
    for (radek=0; radek<9; radek++) {
        for (i=0; i<9; i++)
            cifry[i]=0;
        /* projdi vsechny bunky ve sloupci a zjisti zapsana cisla */
        for (sloupec=0; sloupec<9; sloupec++) {
            cifra=src[radek][sloupec];
            if (cifra>0) { /* obsad cifru */
                cifry[cifra-1]=1;
            }
        }
        /* v matici povol zmeni cely sloupec */
        for (sloupec=0; sloupec<9; sloupec++) {
            if (src[radek][sloupec]==0) {
                for (i=0; i<9; i++) {
                    if (cifry[i])
                        povol[radek][sloupec][i]=0;
                }
            }
        }
    }
}



/* ------------------------------------------------------------------ */
/* Snizeni poctu moznych kombinaci zjistenim duplicit v blocich 3x3   */
/* ------------------------------------------------------------------ */
void testBloky0(void)
{
    int blokx, bloky;
    int cifry[9], cifra;
    int i, j;
    for (bloky=0; bloky<9; bloky+=3) {
        for (blokx=0; blokx<9; blokx+=3) {
            for (i=0; i<9; i++) /* v kazdem bloku 3x3 nejprve vymazeme seznam cifer */
                cifry[i]=0;
            for (j=0; j<3; j++) { /* projdi blok a zjisti cisla */
                for (i=0; i<3; i++) {
                    cifra=src[j+bloky][i+blokx];
                    if (cifra>0) { /* obsad cifru */
                        cifry[cifra-1]=1;
                    }
                }
            }
            for (j=0; j<3; j++) { /* projdi blok a znuluj nalezene cifry */
                for (i=0; i<3; i++) {
                    if (src[j+bloky][i+blokx]==0) { /* v tomto poli ma smysl menit cifry */
                        int k;
                        for (k=0; k<9; k++) {
                            if (cifry[k])
                                povol[j+bloky][i+blokx][k]=0;
                        }
                    }
                }
            }
        }
    }
}



/* ------------------------------------------------------------------ */
/* Test, zda je ve vsech sloupcich devet ruznych hodnot               */
/* ------------------------------------------------------------------ */
int testSloupce(void)
{
    int radek, sloupec;
    int cifry[9];
    for (sloupec=0; sloupec<9; sloupec++) {
        for (radek = 0; radek<9; radek++) {
            cifry[radek] = 0;
        }
        /* projdu vsechny polozky v radku a zjistim cisla */
        for (radek=0; radek < 9; radek++) {
            /* cifra je uz obsazena? */
            if (cifry[wrk[radek][sloupec]-1] != 0)
                return 0;
            else  /* obsad cifru */
                cifry[wrk[radek][sloupec]-1]=1;
        }
    }
    return 1;
}



/* ------------------------------------------------------------------ */
/* Test, zda je na vsech radcich devet ruznych hodnot                 */
/* ------------------------------------------------------------------ */
int testRadky(void)
{
    int radek, sloupec;
    int cifry[9];
    for (radek=0; radek<9; radek++) {
        for (sloupec=0; sloupec<9; sloupec++) {
            cifry[sloupec] = 0;
        }
        /* projdu vsechny polozky v radku a zjistim cisla */
        for (sloupec=0; sloupec<9; sloupec++) {
            /* cifra je uz obsazena? */
            if (cifry[wrk[radek][sloupec]-1] != 0)
                return 0;
            else  /* obsad cifru */
                cifry[wrk[radek][sloupec]-1]=1;
        }
    }
    return 1;
}



/* ------------------------------------------------------------------ */
/* Test, zda je ve vsech blocich 3x3 devet ruznych hodnot             */
/* ------------------------------------------------------------------ */
int testBloky(void)
{
    int blokx, bloky;
    int cifry[9], cifra;
    int i, j;
    for (bloky=0; bloky<9; bloky+=3) {
        for (blokx=0; blokx<9; blokx+=3) {
            memset(cifry, 0, 9 * sizeof(int));
            for (j=0; j<3; j++) {
                for (i=0; i<3; i++) {
                    cifra=wrk[j+bloky][i+blokx];
                    if (cifry[cifra-1])
                        return 0;
                    else  /* obsad cifru */
                        cifry[cifra-1]=1;
                }
            }
        }
    }
    return 1;
}



/* ------------------------------------------------------------------ */
/* Tisk nalezeneho reseni                                             */
/* ------------------------------------------------------------------ */
void tiskVysledku(void)
{
    int i, j;
    putchar('\n');
    ODDELOVAC
    for (j=0; j<9; j++) {
        printf("| ");
        for (i=0; i<9; i++) {
            printf("%d ", wrk[j][i]);
            if (i % 3 == 2) printf(" | ");
        }
        putchar('\n');
        if (j % 3 == 2)
            ODDELOVAC
    }
}



/* ------------------------------------------------------------------ */
/* Reseni Sudoku                                                      */
/* ------------------------------------------------------------------ */
void solve(void)
{
    int i, j, k;
    int done=0;
    double counter=0;
    double max=1;
    int cnt=0;

    /* zjisteni poctu kombinaci pro vypis */
    for (j=0; j<9; j++) {
        for (i=0; i<9; i++) {
            int cnt=0;
            for (k=0; k<9; k++) {
                if (povol[j][i][k])
                    cnt++;
            }
            max=max*cnt;
        }
    }

    while (!done) {
        /* test, zda je Sudoku vyreseno */
        if (testRadky() && testSloupce() && testBloky()) {
            tiskVysledku();
            return;
        }

        /* vypis prubeznych vysledku */
        if (cnt==5e6) {
            printf("Kombinaci: %.0f z %.f  zbyva %.f = %7.3f%%\n", counter, max, max-counter, 100.0 - 100.0*counter/max);
            cnt=0;
        }
        for (j=0; j<9; j++) {
            for (i=0; i<9; i++) {
                if (!src[j][i]) { /* jde o nevyplnenou polozku -> zvysime jeji hodnotu */
                    if (wrk[j][i]<9) {
                        do { /* prejit na dalsi povolenou cifru */
                            wrk[j][i]++;
                            k=wrk[j][i];
                        } while (povol[j][i][k-1]==0 && k<=9);
                        if (k>9 || povol[j][i][k-1]==0) { /* uz jsme na konci rady povolenych cisel? */
                            wrk[j][i]=minim[j][i];        /* prejdeme na dalsi policko */
                        }
                        else {
                            goto KONEC;
                        }
                    }
                    else { /* jsme na konci -> nastavime prvni povolenou cifru */
                        wrk[j][i]=minim[j][i];
                        if (j==8 && i==8) done=1;
                    }
                }
            }
        }
KONEC:
        counter++;
        cnt++;
    }
}



/* ------------------------------------------------------------------ */
/* Vypis vsech kombinaci cisel pro kazde policko                      */
/* ------------------------------------------------------------------ */
void vypisPovol()
{
    double counter=1;
    int i, j, k;
    /* vypsani povol matice */
    for (j=0; j<9; j++) {
        for (i=0; i<9; i++) {
            int cnt=0;
            int prvniCislo=1;
            putchar('(');
            for (k=0; k<9; k++) {
                if (povol[j][i][k]) {
                    if (prvniCislo)
                        prvniCislo = 0;
                    else
                        putchar(' ');
                    putchar('1'+k);
                    cnt++;
                }
            }
            putchar(')');
            putchar(' ');
            putchar(' ');
            counter=counter*cnt;
        }
        putchar('\n');
    }
    printf("Kombinaci celkem: %g\n\n", counter);
}



/* ------------------------------------------------------------------ */
/* Funkce zavolana po startu konzolove aplikace                       */
/* ------------------------------------------------------------------ */
int main(void)
{
    int i, j, k;

    /* inicializace pracovni matice */
    for (j=0; j<9; j++)
        for (i=0; i<9; i++) {
            wrk[j][i]=src[j][i];
            if (wrk[j][i]==0) wrk[j][i]=1;
        }

    /* inicializace povol matice */
    for (j=0; j<9; j++) {
        for (i=0; i<9; i++) {
            for (k=0; k<9; k++) {
                povol[j][i][k]=1;
            }
        }
    }
    puts("Pocet kombinaci v nevyplnenych polickach:");
    vypisPovol();

    /* zruseni polozek v matici SRC */
    for (j=0; j<9; j++) {
        for (i=0; i<9; i++) {
            if (src[j][i]>0)
                for (k=0; k<9; k++) {
                    if (k+1!=src[j][i])
                        povol[j][i][k]=0;
                }
        }
    }

    testSloupce0();
    puts("Odstraneni jiz vyplnenych cislic ve sloupcich:");
    vypisPovol();

    testRadku0();
    puts("Odstraneni jiz vyplnenych cislic v radcich:");
    vypisPovol();

    testBloky0();
    puts("Odstraneni jiz vyplnenych cislic v blocich 3x3:");
    vypisPovol();

    /* inicializace minimalnich polozek */
    for (j=0; j<9; j++) {
        for (i=0; i<9; i++) {
            if (src[j][i]==0) { /* volna polozka */
                for (k=0; k<9; k++) {
                    if (povol[j][i][k]) {
                        minim[j][i]=k+1;
                        break;
                    }
                }
            }
        }
    }

    /* nastaveni prvnich volnych polozek */
    for (j=0; j<9; j++) {
        for (i=0; i<9; i++) {
            if (src[j][i]==0) /* volna polozka */
                wrk[j][i]=minim[j][i];
        }
    }

    puts("Mozne kombinace cisel:");
    vypisPovol();

    puts("Jdeme na to ... trpelivost ...");
    solve();

    return 0;
}



/* ------------------------------------------------------------------ */
/* finito                                                             */
/* ------------------------------------------------------------------ */