#include <stdio.h> 
#include <stdbool.h>
#include <time.h>
#define LEER 0
int FALSCH, VERSUCH;

void beispielFeld(int feld[9][9])
{
	int beispiel[9][9] = {	{5, 3, 0, 0, 7, 0, 0, 0, 0},
							{6, 0, 0, 1, 9, 5, 0, 0, 0},
							{0, 9, 8, 0, 0, 0, 0, 6, 0},
							{8, 0, 0, 0, 6, 0, 0, 0, 3},
							{4, 0, 0, 8, 0, 3, 0, 0, 1},
							{7, 0, 0, 0, 2, 0, 0, 0, 6},
							{0, 6, 0, 0, 0, 0, 2, 8, 0},
							{0, 0, 0, 4, 1, 9, 0, 0, 5},
							{0, 0, 0, 0, 8, 0, 0, 7, 9}};
	int zeile, spalte;
	for (zeile = 0; zeile < 9; zeile++)
		for (spalte = 0; spalte < 9; spalte++)
			feld[zeile][spalte] = beispiel[zeile][spalte];
}

void beispielFeldSchwierig(int feld[9][9])
{
	int beispiel[9][9] = {	{0, 0, 5, 3, 0, 0, 0, 0, 0},
							{8, 0, 0, 0, 0, 0, 0, 2, 0},
							{0, 7, 0, 0, 1, 0, 5, 0, 0},
							{4, 0, 0, 0, 0, 5, 3, 0, 0},
							{0, 1, 0, 0, 7, 0, 0, 0, 6},
							{0, 0, 3, 2, 0, 0, 0, 8, 0},
							{0, 6, 0, 5, 0, 0, 0, 0, 9},
							{0, 0, 4, 0, 0, 0, 0, 3, 0},
							{0, 0, 0, 0, 0, 9, 7, 0, 0}};
	int zeile, spalte;
	for (zeile = 0; zeile < 9; zeile++)
		for (spalte = 0; spalte < 9; spalte++)
			feld[zeile][spalte] = beispiel[zeile][spalte];
}

void setzeFeld(int feld[9][9])
{
	char eingabe[9];
	int zeile;
	int spalte;
	printf("Gib Sudoku zeilenweise ein. Leere Zelle ist 0 - z.B.: Zeile 1: 530070000\n");
	for (zeile = 0; zeile < 9; zeile++)
	{
		printf("Zeile %d: ", zeile+1);
		for (spalte = 0; spalte < 9; spalte++)
			eingabe[spalte] = 0;
		scanf("%s", eingabe);
		for (spalte = 0; spalte < 9; spalte++)
		{
			feld[zeile][spalte] = (int)(eingabe[spalte])-48;			
		}
	}
}

void zeichneFeld(int feld[9][9])
{
	int zeile, spalte;
	printf("\n");
	for (zeile = 0; zeile < 9; zeile++)
	{
		printf("\n");
		for (spalte = 0; spalte < 9; spalte++)
		{
			if(feld[zeile][spalte] == LEER)
				printf("   ");
			else		
				printf(" %d ", feld[zeile][spalte]);
			if(spalte%3 == 2)
			printf("  ");
		}
		if(zeile%3 == 2)
			printf("\n");
	}
	printf("\n");
}

bool zeilenKonflikt(int feld[9][9], int zeile, int zahl)
{
	int spalte;
	for (spalte = 0; spalte < 9; spalte++)
		if (feld[zeile][spalte] == zahl) 
			return true;
	return false;
}

bool spaltenKonflikt(int feld[9][9], int spalte, int zahl)
{
	int zeile;
	for (zeile = 0; zeile < 9; zeile++)
		if (feld[zeile][spalte] == zahl)
			return true;
	return false;
}

bool quadratKonflikt(int feld[9][9], int boxStartRow, int boxStartCol, int zahl)
{
	int zeile, spalte;
	for (zeile = 0; zeile < 3; zeile++)
		for (spalte = 0; spalte < 3; spalte++)
			if (feld[zeile+boxStartRow][spalte+boxStartCol] == zahl)
			return true;
	return false;
}

bool nichtOK(int feld[9][9], int zeile, int spalte, int zahl)
{
	return zeilenKonflikt(feld, zeile, zahl) || spaltenKonflikt(feld, spalte, zahl) || quadratKonflikt(feld, zeile - zeile%3 , spalte - spalte%3, zahl);
}

int findeLeereZelle(int feld[9][9], int zeile, int spalte)
{
	for (zeile = 0; zeile < 9; zeile++)
		for (spalte = 0; spalte < 9; spalte++)
		{
			if (feld[zeile][spalte] == LEER)
			{
				return zeile*9+spalte;
			}
		}
return -1;
}

bool sudoku(int feld[9][9])
{
	int zeile, spalte, zahl;
	int leereZelleGefunden;
	leereZelleGefunden = (findeLeereZelle(feld, zeile, spalte));
	zeile = leereZelleGefunden/9;
	spalte = leereZelleGefunden%9;
	if (leereZelleGefunden < 0) 
	{
		printf("Sudoku geloest!\n");		
		return true;
	}
	for (zahl = 1; zahl <= 9; zahl++)
	{
		if (!nichtOK(feld, zeile, spalte, zahl))
		{
			VERSUCH++;
			printf(" Schreibe %d in Zeile%d-Spalte%d ", zahl, zeile+1, spalte+1);
 			feld[zeile][spalte] = zahl;
			zeichneFeld(feld);	
			if (sudoku(feld) == true)
				return true;  
			printf(" Loesche Zeile%d-Spalte%d ", zeile+1, spalte+1);		
			feld[zeile][spalte] = LEER;
			FALSCH++; 			
		}
	}
	return false; 							
}

bool sudokuBlind(int feld[9][9])
{
	int zeile, spalte, zahl;
	int leereZelleGefunden;
	leereZelleGefunden = (findeLeereZelle(feld, zeile, spalte));
	zeile = leereZelleGefunden/9;
	spalte = leereZelleGefunden%9;
	if (leereZelleGefunden < 0) 
		return true;
	for (zahl = 1; zahl <= 9; zahl++)
	{
		if (!nichtOK(feld, zeile, spalte, zahl))
		{
 			feld[zeile][spalte] = zahl;
			if (sudokuBlind(feld) == true)
				return true;  
			feld[zeile][spalte] = LEER;
		}
	}
	return false; 							
}

void main()
{
	int feld[9][9];
	int zeile;
	int spalte;
	int aufgabe;
	int ok;
	int ausgabe;
	bool loesbar;
	time_t start,end;
	double dif;
	while((aufgabe < 1) || (aufgabe > 3))
	{
		printf("1 - Beispiel Sudoku loesen \n2 - Schwieriges Beispiel Sudoku loesen \n3 - Eigenes Sudoku eingeben \n");
		scanf("%d", &aufgabe);
	}
	if(aufgabe == 1)
	{
		beispielFeld(feld);	
		zeichneFeld(feld);
	}
	if(aufgabe == 2)
	{
		beispielFeldSchwierig(feld);	
		zeichneFeld(feld);
	}	
	if(aufgabe == 3)
		while((ok != 1) && (ok != 2))
		{
			setzeFeld(feld);
			zeichneFeld(feld);
			printf("1 - OK \n2 - Korrigieren \n");
			scanf("%d", &ok);
		}
	while((ausgabe != 1) && (ausgabe != 2))
	{
		printf("1 - Ausfuehrliche Ausgabe \n2 - Nur Ergebnis Anzeigen \n");
		scanf("%d", &ausgabe);
	}
	if(ausgabe == 1)
	{
		time (&start);
		loesbar = sudoku(feld);
		time (&end);
		dif = difftime (end,start);
		if(loesbar)
			printf("Dieses Sudoku war loesbar in %.0lf Sekunden.\n%d Annahmen getroffen, wovon %d falsch waren.\n", dif, VERSUCH, FALSCH);
		else
			printf("Dieses Sudoku ist unloesbar.\n");
	}
	if(ausgabe == 2)
	{
		time (&start);
		loesbar = sudokuBlind(feld);
		time (&end);
		dif = difftime (end,start);
		zeichneFeld(feld);
		if(loesbar)
			printf("Dieses Sudoku war loesbar in %.0lf Sekunden.\n", dif);
		else
			printf("Dieses Sudoku ist unloesbar.\n");
	}	
}