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

int solve(int sudokufeld[9][9], int solvedsudokufeld[9][9]);

int main()
{
    int i=0;
    int j=0;
    char zahl[1] = {0};
    int sudokufeld[9][9];
    int solvedsudokufeld[9][9] = {0};
    
    printf("Bitte geben sie das ganze Spielfeld an. Alle Eingaben != 1-9 werden als unbekannt angenommen\n");
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            zahl[0] = getch();
            sudokufeld[i][j] = atoi(zahl);
            printf("%2i", sudokufeld[i][j]);
        }
        printf("\n");
    }
    
    solve(sudokufeld, solvedsudokufeld);
    
    printf("\n\nLoesung:\n");
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            printf("%2i", solvedsudokufeld[i][j]);
        }
        printf("\n");
    }
    //printf("\n%i\n", IstMoeglich(sudokufeld));
    
    //Auf q warten
    getch();
}

void kopiereSudoku(int quelleSudokufeld[9][9], int zielSudokufeld[9][9])
{
    int i, j;
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            zielSudokufeld[i][j] = quelleSudokufeld[i][j];
        }
    }
}

//0 wenn wiedersprüche
//1 wenn Sudoku OK
int IstMoeglich(int refSudokufeld[9][9])
{
    int i, j, zusammenh, zusammenv;
    for (i = 0; i < 9; i++)
    {
        //Horizontal
        zusammenh = 0;
        zusammenv = 0;
        for (j = 0; j < 9; j++) //Alle Zellen zusammenrechnen
        {
            zusammenh+=refSudokufeld[i][j];
            zusammenv+=refSudokufeld[j][i];
        }
        if (zusammenh != 45 || zusammenv != 45)
            return 0;
    }
    return 1;
}

int solve(int refSudokufeld[9][9], int solvedSudokufeld[9][9])
{
    int i, j, k;
    int tempsudokufeld[9][9];
    
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            //Das Feld darf nur bearbeitet werden, wenn es unbekannt ist
            if (refSudokufeld[i][j] == 0)
            {
                for (k = 1; k <= 9; k++)
                {
                    kopiereSudoku(refSudokufeld, tempsudokufeld);
                    tempsudokufeld[i][j] = k;
                    //Wenn Sudoku nun gelöst, dann 1 zurück
                    if (IstMoeglich(tempsudokufeld))
                    {
                        kopiereSudoku(tempsudokufeld, solvedSudokufeld);
                        return 1;
                    }
                    else //Sonst sich selber aufrufen
                    {
                        if (solve(tempsudokufeld, solvedSudokufeld))
                            return 1;
                    }
                }
            }
        }
    }
    return 0;
}