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

int pusta();
int jest(int krzad, int kkol, int n);
int sudoku_glowna();
void dajTablica();

int tablica[9][9] = {
    { 8, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 3, 6, 0, 0, 0, 0, 0 },
    { 0, 7, 0, 0, 9, 0, 2, 0, 0 },
    { 0, 5, 0, 0, 0, 7, 0, 0, 0 },
    { 0, 0, 0, 0, 4, 5, 7, 0, 0 },
    { 0, 0, 0, 1, 0, 0, 0, 3, 0 },
    { 0, 0, 1, 0, 0, 0, 0, 6, 8 },
    { 0, 0, 8, 5, 0, 0, 0, 1, 0 },
    { 0, 9, 0, 0, 0, 0, 4, 0, 0 }
};


int rzad, kol;

void main()
{
    int i, j, rozwiazanie = 0;
    char ch;
    printf("Sudoku: \n");
    dajTablica();
    printf("Wcisnij 'T' jesli chcesz rozwiazac sudoku. \nWcisnij 'N' jesli nie chcesz rozwiazac.");
    ch = getc(stdin);
    if (ch == 'n')
        exit(0);
    else if (ch == 't')
    {
        rozwiazanie = sudoku_glowna();
        if (rozwiazanie)
        {
            printf("\n\nRozwiazane sudoku:\n\n");
            dajTablica();
            printf("\nMILEGO DNIA :)\n\n");
        }
        else
            printf("\nBrak rozwiazania!\n\n");
        getc(stdin);
    }

}

int pusta()
{
    int i, j;
    for (i = rzad; i <= 8; i++)
        for (j = 0; j <= 8; j++)
        {
            if (tablica[i][j] == 0)
            {
                rzad = i; kol = j;
                return 1;
            }
        }
    return 0;

}

int jest(int krzad, int kkol, int n)
{
    int i, j;
    int rzadStart = (krzad / 3) * 3;
    int kolStart = (kkol / 3) * 3;

    for (j = 0; j <= 8; j++) {
        if (tablica[krzad][j] == n)
            return 0;
        if (tablica[j][kkol] == n)
            return 0;
    }

    for (i = rzadStart; i <= rzadStart + 2; i++)
        for (j = kolStart; j <= kolStart + 2; j++)
            if (tablica[i][j] == n)
                return 0;

    return 1;
}

int sudoku_glowna()
{
    int d;
    int przad, pkol;
    if (!pusta())
        return 1;

    for (d = 1; d <= 9; d++)
    {
        if (jest(rzad, kol, d))
        {
            tablica[rzad][kol] = d;
            przad = rzad; pkol = kol;
            if (sudoku_glowna())
                return 1;
            rzad = przad; kol = pkol;
            tablica[rzad][kol] = 0;
        }
    }
    return 0;
}


void dajTablica()
{
    int i, j;
    printf("\n");
    for (i = 0; i<9; i++)
    {
        printf("\t");
        for (j = 0; j<9; j++)
        {
            if (j == 0)
                printf("| ");
            if (tablica[i][j] == 0)
                printf(". ");
            else
                printf("%d ", tablica[i][j]);
            if ((j + 1) % 3 == 0)
                printf("| ");
        }
        if ((i + 1) % 3 == 0)
            printf("\n");
        printf("\n");
    }
}