/*******************************************************************
*  Recursive str8ts solver - programmed by Philip June 2014        *
*  June 2015 - bugfix - check for absolute value (-black)          *
********************************************************************/
#include <stdio.h> 
#include <stdbool.h>
#include <time.h>
#define LEER 0
int FALSCH, VERSUCH;


void beispielFeldEinfach(int feld[9][9])
{
	//weiss positiv, schwarz negativ, leeres schwarzes feld ist -10 da es keine negative 0 gibt
	int beispiel[9][9] = {	{-10,-10,  0,  0,  5,  0,  0, -3,-10},
				{  0,  6,  0,  0,-10,-10,  1,  0,  0},
				{  0,  0,  0,-10, -8,  0,  0,  0,  0},
				{  9,  0,  0, -4,  0,  0,  0,-10,  5},
				{-10,  0,  0,  0,  0,  3,  0,  0,-10},
				{-10,-10,  0,  0,  0, -9,  0,  4,  0},
				{  4,  0,  3,  0,-10,-10,  0,  6,  0},
				{  0,  0,  1,-10,-10,  0,  0,  0,  0},
				{-10,-10,  8,  0,  0,  0,  0,-10, -2}};
	int zeile, spalte;
	for (zeile = 0; zeile < 9; zeile++)
		for (spalte = 0; spalte < 9; spalte++)
			feld[zeile][spalte] = beispiel[zeile][spalte];
}


void beispielFeldTeuflisch(int feld[9][9])
{
	int beispiel[9][9] = {	{-10,-10,  2,  0,  0,-10,  9,  0,  0},
				{-10,  0,  0,  0,  0, -8,  6,  0,-10},
				{  5,  2,  0,  0, -6,  0,  0,  0,-10},
				{  0,  0,  0,  0,  0,  0,  0,  0,  0},
				{  0,-10, -1,  5,  0,  0,-10,-10,  0},
				{  0,  0,  0,  0,  0,  0,  0,  0,  6},
				{-10,  0,  0,  0, -5,  0,  0,  3,  0},
				{ -7,  0,  0, -9,  0,  0,  0,  0,-10},
				{  0,  0,  0,-10,  0,  2,  0, -4,-10}};
	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[99];
	int zeile;
	int spalte;
	printf("Gib Str8ts zeilenweise ein. Leere Zelle ist 0 - z.B.: Zeile 1: 530070000\n");
	printf("fuer schwarze Felder gib p ein\n");
	printf("eine 1 auf schwarzem Feld bekommt man mit q, 2 mit w und so weiter\n");	
	printf("schau einfach auf die qwertz Tastatur - schwarze zahlen sind einfach eine Etage tiefer :-)\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] = 99;
			if (0 <= ((int)(eingabe[spalte])-48) <= 9)
				feld[zeile][spalte] = (int)(eingabe[spalte])-48;
			if ((int)(eingabe[spalte]) == 113)
				feld[zeile][spalte] = -1;
			if ((int)(eingabe[spalte]) == 119)
				feld[zeile][spalte] = -2;
			if ((int)(eingabe[spalte]) == 101)
				feld[zeile][spalte] = -3;
			if ((int)(eingabe[spalte]) == 114)
				feld[zeile][spalte] = -4;
			if ((int)(eingabe[spalte]) == 116)
				feld[zeile][spalte] = -5;
			if ((int)(eingabe[spalte]) == 122 || (int)(eingabe[spalte]) == 121)
				feld[zeile][spalte] = -6;
			if ((int)(eingabe[spalte]) == 117)
				feld[zeile][spalte] = -7;
			if ((int)(eingabe[spalte]) == 105)
				feld[zeile][spalte] = -8;
			if ((int)(eingabe[spalte]) == 111)
				feld[zeile][spalte] = -9;
			if ((int)(eingabe[spalte]) == 112)
				feld[zeile][spalte] = -10;							
		}
	}
}


void zeichneFeld(int feld[9][9])
{
	int zeile, spalte;
	int fehler = 0;
	printf("\n");
	for (zeile = 0; zeile < 9; zeile++)
	{
		printf("\n");
		for (spalte = 0; spalte < 9; spalte++)
		{
			if(feld[zeile][spalte] == LEER)
				printf("\033[0;47;30m   \033[0m");
			if(feld[zeile][spalte] == -10)
				printf("\033[0;40;37m   \033[0m");
			if((-10 < feld[zeile][spalte]) && (feld[zeile][spalte] < 0))
				printf("\033[0;40;37m %d \033[0m", -feld[zeile][spalte]);
			if((0 < feld[zeile][spalte]) && (feld[zeile][spalte] < 10))		
				printf("\033[0;47;30m %d \033[0m", feld[zeile][spalte]);
			if(feld[zeile][spalte] < -10 || feld[zeile][spalte] > 10)
			{
				printf("\033[0;43;31m ? \033[0m");
				fehler++;
			}
		}
	}
	if(fehler)
		printf("\nAchtung dieses Feld enthaelt wohl %d Fehler", fehler);
	printf("\n\n");
}


bool zeilenKonflikt(int feld[9][9], int zeile, int zahl)
{
	int spalte;
	for (spalte = 0; spalte < 9; spalte++)
		if (feld[zeile][spalte] == zahl || 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 || feld[zeile][spalte] == -zahl)
			return true;
	return false;
}


bool str8tsZeilenKonflikt(int feld[9][9], int zeile, int spalte, int zahl)
{
	int laenge = 1;
	int position = spalte;
	int max = zahl;
	int min = zahl;
	while ((position < 8) && (feld[zeile][position + 1] > -1))
		{
			position++;
			laenge++;
			if (feld[zeile][position] > max)
				max = feld[zeile][position];
			if ((feld[zeile][position] < min) && (feld[zeile][position] > 0))
				min = feld[zeile][position];			
		}
	position = spalte;
	while ((position > 0) && (feld[zeile][position - 1] > -1))
		{
			position--;
			laenge++;
			if (feld[zeile][position] > max)
				max = feld[zeile][position];
			if ((feld[zeile][position] < min) && (feld[zeile][position] > 0))
				min = feld[zeile][position];
		}
	if ((max - min) >= laenge)
		return true;
	return false;
}


bool str8tsSpaltenKonflikt(int feld[9][9], int zeile, int spalte, int zahl)
{
	int hoehe = 1;
	int position = zeile;
	int max = zahl;
	int min = zahl;
	while ((position < 8) && (feld[position + 1][spalte] > -1))
		{
			position++;
			hoehe++;
			if (feld[position][spalte] > max)
				max = feld[position][spalte];
			if ((feld[position][spalte] < min) && (feld[position][spalte] > 0))
				min = feld[position][spalte];			
		}
	position = zeile;
	while ((position > 0) && (feld[position - 1][spalte] > -1))
		{
			position--;
			hoehe++;
			if (feld[position][spalte] > max)
				max = feld[position][spalte];
			if ((feld[position][spalte] < min) && (feld[position][spalte] > 0))
				min = feld[position][spalte];
		}
	if ((max - min) >= hoehe)
		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) || str8tsZeilenKonflikt(feld, zeile, spalte, zahl) || str8tsSpaltenKonflikt(feld, zeile, spalte, 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 str8ts(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("Str8ts 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 (str8ts(feld) == true)
				return true;  
			printf(" Loesche Zeile%d-Spalte%d ", zeile+1, spalte+1);		
			feld[zeile][spalte] = LEER;
			FALSCH++; 			
		}
	}
	return false; 							
}


bool str8tsBlind(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 (str8tsBlind(feld) == true)
				return true;  
			feld[zeile][spalte] = LEER;
		}
	}
	return false; 							
}


void main()
{
	int feld[9][9];
	int zeile;
	int spalte;
	int aufgabe = 0;
	int ok = 2;
	int ausgabe;
	bool loesbar;
	time_t start,end;
	double dif;
	FILE * pDatei = NULL;
	char dateiname[99];
	char inhalt[300];
	int z, s;
	int x;
	bool gefunden = false; 
	printf("\n**********  Str8ts-Knacker ***********\n\n");
	while((aufgabe < 1) || (aufgabe > 4))
	{
		printf("1 - Einfaches Beispiel Str8ts loesen \n2 - Teuflisches Beispiel Str8ts loesen \n3 - Eigenes Str8ts eingeben \n4 - Gespeicherte .str8ts-Datei oeffnen\n");
		scanf("%d", &aufgabe);
	}
	if(aufgabe == 1)
	{
		beispielFeldEinfach(feld);	
		zeichneFeld(feld);
	}
	if(aufgabe == 2)
	{
		beispielFeldTeuflisch(feld);	
		zeichneFeld(feld);
	}	
	if(aufgabe == 3)
		while((ok < 1) || (ok == 2) || (ok > 3))
		{
			setzeFeld(feld);
			zeichneFeld(feld);
			printf("1 - OK, weiter \n2 - Korrigieren \n3 - Erst speichern, dann weiter\n");
			scanf("%d", &ok);
			if (ok == 3)
			{
				printf("Gib bitte einen Dateinamen an: ");
				scanf("%s", dateiname);
				sprintf(dateiname, "%s.str8ts", dateiname);
				pDatei = fopen(dateiname, "w");	
				for (z = 0; z < 9; z++)
					for (s = 0; s < 9; s++)
						fprintf(pDatei, "%*d\n", 3, feld[z][s]);
				fclose(pDatei);
			}		
		}
	if(aufgabe == 4)
	{
		while(!gefunden)
		{
			printf("Gib bitte Dateinamen ohne .str8ts-Endung an: ");
			scanf("%s", dateiname);
			sprintf(dateiname, "%s.str8ts", dateiname);
			pDatei = fopen(dateiname, "r");
			if(pDatei != NULL)
			{
				gefunden = true;
				z = 0;
				s = 0;
				do
				{
					fscanf(pDatei, "%d", &x);	
					feld[z][s] = x;
					s++;
					if(s == 9)
					{
						s = 0;
						z++;
					}
				}
				while(z < 9);	
				fclose(pDatei);			
			}
			else
				printf("Datei %s nicht vorhanden\n", dateiname);
		}
		zeichneFeld(feld);
	}
	while((ausgabe != 1) && (ausgabe != 2))
	{
		printf("1 - Ausfuehrliche Ausgabe \n2 - Nur Ergebnis Anzeigen \n");
		scanf("%d", &ausgabe);
	}
	if(ausgabe == 1)
	{
		time (&start);
		loesbar = str8ts(feld);
		time (&end);
		dif = difftime (end,start);
		if(loesbar)
			printf("Dieses Str8ts war loesbar in %.0lf Sekunden.\n%d Annahmen getroffen, wovon %d falsch waren.\n", dif, VERSUCH, FALSCH);
		else
			printf("Dieses Str8ts ist unloesbar.\n");
	}
	if(ausgabe == 2)
	{
		time (&start);
		loesbar = str8tsBlind(feld);
		time (&end);
		dif = difftime (end,start);
		zeichneFeld(feld);
		if(loesbar)
			printf("Dieses Str8ts war loesbar in %.0lf Sekunden.\n", dif);
		else
			printf("Dieses Str8ts ist unloesbar.\n");
	}	
}