#include <stdio.h>

void oku(void);
void yaz(char mod);
void coz(void);
void ihtimal_bul(void);
void tek_bul(void);
int tabloyu_doldur(void);
void dene(int sira);
void kopyala(char hedef[9][9], char kaynak[9][9]);
int kontrol(void);
void sifirla(char dizi[9]);

char tablo[9][9] = {0};
char olasi[9][9][9] = {0};

int main(void)
{
	char tmp;
	int i, j;
	oku();
	printf("\nSudokuSolver by Can Guler\n\n");
	yaz(0);
	coz();
	tmp = kontrol();
	if (tmp == 1)
		printf("----Sudoku is solved----\n\n");
	else
		printf("--Sudoku isn't solved---\n\n");		
	yaz(1);
	yaz(0);
	return 0;
}
/* Sudoku tablosunu dosyadan okuyor */
void oku(void)
{
	FILE *fin = fopen("sudoku.in","r");
	int satir, sutun;
	char tmp;
	for (satir=0; satir<9; ++satir) {
		for (sutun=0; sutun<9; ++sutun) {
			fscanf(fin,"%c",&tmp);
			tablo[satir][sutun] = tmp-'0';
		}
		fscanf(fin,"\n");
	}
	fclose(fin);
	return;
}

/* Sudoku tablosunu dosyaya(mod=1) / ekrana(mod=0) yazıyor */
void yaz(char mod)
{
	int satir, sutun;
	if (mod == 0) {
		for (satir=0; satir<9; ++satir) {
			if (satir%3 == 0)
				printf("+-------+-------+-------+\n");
			for (sutun=0; sutun<9; ++sutun) {
				if (sutun%3 == 0)
					printf("| ");
				if (tablo[satir][sutun] == 0)
					printf("- ");
				else
					printf("%d ",tablo[satir][sutun]);
			}
			printf("|\n");
		}
		printf("+-------+-------+-------+\n\n");
	} else if (mod == 1) {
		FILE *fout = fopen("sudoku.out","w");
		for (satir=0; satir<9; ++satir) {
			for (sutun=0; sutun<9; ++sutun)
				fprintf(fout,"%d",tablo[satir][sutun]);
			fprintf(fout,"\n");
		}
		fclose(fout);
	}
	return;
}

/* Sudokuyu çözmek için sırayla gerekli fonksiyonları çağırıyor */
void coz(void)
{
	int tmp;
	while (1) {
		ihtimal_bul();
		tek_bul();
		tmp = tabloyu_doldur();
		if (tmp == 0) {
			dene(0);
			break;
		}
	}
	return;
}

/* Önceden yerleştirilmiş sayılara göre her kutucuğa gelebilecek ihtimalleri buluyor */
void ihtimal_bul(void)
{
	int satir, sutun, deger, dsatir, dsutun;
	for (satir=0; satir<9; ++satir)
		for (sutun=0; sutun<9; ++sutun)
			for (deger=0; deger<9; ++deger)
				olasi[satir][sutun][deger] = 0;
	for (satir=0; satir<9; ++satir) {
		for (sutun=0; sutun<9; ++sutun) {
			if (tablo[satir][sutun] != 0)
				continue;
			/* Satırı kontrol ediyor */
			for (dsutun=0; dsutun<9; ++dsutun) {
				if (tablo[satir][dsutun] == 0)
					continue;
				deger = tablo[satir][dsutun]-1;
				olasi[satir][sutun][deger] = 1;
			}
			/* Sütunu kontrol ediyor */
			for (dsatir=0; dsatir<9; ++dsatir) {
				if (tablo[dsatir][sutun] == 0)
					continue;
				deger = tablo[dsatir][sutun]-1;
				olasi[satir][sutun][deger] = 1;
			}
			/* 3x3'lük kareyi kontrol ediyor */
			for (dsatir=satir/3*3; dsatir<satir/3*3+3; ++dsatir) {
				for (dsutun=sutun/3*3; dsutun<sutun/3*3+3; ++dsutun) {
					if (tablo[dsatir][dsutun] == 0)
						continue;
					deger = tablo[dsatir][dsutun]-1;
					olasi[satir][sutun][deger] = 1;
				}
			}
		}
	}
	return;
}

/*
** Bir satır, sütun veya 3x3'lük karede bir sayı yalnızca bir kutucuğa
** gelebiliyorsa o kutucuğa gelebilecek diğer ihtimalleri yok ediyor
*/
void tek_bul(void)
{
	char say, uygun_sutun, uygun_satir;
	int satir, sutun, deger, ddeger, kare, kutu;
	/*
	** Bir satırda yalnızca tek bir yere gelebilecek değerleri arıyor, 
	** bulduğunda diğer olasılıkları yok ediyor
	*/
	for (deger=0; deger<9; ++deger) {
		for (satir=0; satir<9; ++satir) {
			say = 0;
			for (sutun=0; sutun<9; ++sutun) {
				if (tablo[satir][sutun] != 0)
					continue;				
				if (olasi[satir][sutun][deger] == 0) {
					say++;
					uygun_sutun = sutun;
				}
			}
			if (say == 1) {
				for (ddeger=0; ddeger<9; ++ddeger)
					olasi[satir][uygun_sutun][ddeger] = 1;
				olasi[satir][uygun_sutun][deger] = 0;
			}
		}
	}
	/*
	** Bir sütunda yalnızca tek bir yere gelebilecek değerleri arıyor, 
	** bulduğunda diğer olasılıkları yok ediyor
	*/
	for (deger=0; deger<9; ++deger) {
		for (sutun=0; sutun<9; ++sutun) {
			say = 0;
			for (satir=0; satir<9; ++satir) {
				if (tablo[satir][sutun] != 0)
					continue;
				if (olasi[satir][sutun][deger] == 0) {
					say++;
					uygun_satir = satir;
				}
			}
			if (say == 1) {
				for (ddeger=0; ddeger<9; ++ddeger)
					olasi[uygun_satir][sutun][ddeger] = 1;
				olasi[uygun_satir][sutun][deger] = 0;
			}
		}
	}
	/*
	** Bir 3x3'lük karede yalnızca tek bir yere gelebilecek değerleri arıyor, 
	** bulduğunda diğer olasılıkları yok ediyor
	*/
	for (deger=0; deger<9; ++deger) {
		for (kare=0; kare<9; ++kare) {
			say = 0;
			for (kutu=0; kutu<9; ++kutu) {
				satir = kare/3*3+kutu/3;
				sutun = kare%3*3+kutu%3;
				if (tablo[satir][sutun] != 0)
					continue;
				if (olasi[satir][sutun][deger] == 0) {
					say++;
					uygun_satir = satir;
					uygun_sutun = sutun;                            
				}
			}
			if (say == 1) {
				for (ddeger=0; ddeger<9; ++ddeger)
					olasi[uygun_satir][uygun_sutun][ddeger] = 1;
				olasi[uygun_satir][uygun_sutun][deger] = 0;
			}
		}
	}
	return;
}

/* Yalnızca tek bir sayı gelebilecek kutucukları doldurur */
int tabloyu_doldur(void)
{
	int satir, sutun, deger;
	int say, uygun_deger, tabloda_degisim;
	tabloda_degisim = 0;
	for (satir=0; satir<9; ++satir) {
		for (sutun=0; sutun<9; ++sutun) {
			if (tablo[satir][sutun] != 0)
				continue;
			say = 0;
			for (deger=0; deger<9; ++deger) {
				if (olasi[satir][sutun][deger] == 0) {
					say++;
					uygun_deger = deger+1;
				}
			}
			if (say == 1) {
				tablo[satir][sutun] = uygun_deger;
				tabloda_degisim = 1;
			}                
		}
	}
	return tabloda_degisim;
}

/*
** Program diğer yaptıklarına rağmen çözüm üretemezse sırayla kutucuklara
** gelebilecek ihtimalleri deniyor
*/
void dene(int sira)
{
	char yedek[9][9];
	int satir, sutun, deger;
	int tmp, say = 0;
	/*
	** Tablonun yedeği alınıp belirtilen sıradaki olasılık deneniyor, hatlysa 
	** tablo yedeğinden kurtarılıp bir sonraki sıradaki olasılık için deneniyor. 
	*/
	kopyala(yedek,tablo);
	for (satir=0; satir<9; ++satir) {
		for (sutun=0; sutun<9; ++sutun) {
			if (tablo[satir][sutun] != 0)
				continue;
			for (deger=0; deger<9; ++deger) {
				if (olasi[satir][sutun][deger] != 0)
					continue;
				if (say != sira) {
					say++;
					continue;
				}
				tablo[satir][sutun] = deger+1;
				coz();
				tmp = kontrol();
				if (tmp == 1)
					return;
				kopyala(tablo,yedek);
				dene(sira+1);
				return;
			}
		}
	}
	return;

}

/* Bir diziyi diğerine kopyalıyor */
void kopyala(char hedef[9][9], char kaynak[9][9])
{
	int satir, sutun;
	for (satir=0; satir<9; ++satir)
		for (sutun=0; sutun<9; ++sutun)
			hedef[satir][sutun] = kaynak[satir][sutun];
	return;
}

/* Sudokunun çözülüp çözülmediğini kontrol ediyor */
int kontrol(void)
{
	int satir, sutun, kare, kutu;
	char deger;
	char kon[9] = { 0 };
	/* Her satırıda her rakamdan yalnızca bir tane olmasını denetliyor */
	for (satir=0; satir<9; ++satir) {
		for (sutun=0; sutun<9; ++sutun) {
			if (tablo[satir][sutun] > 9 || tablo[satir][sutun] < 1)
				return 0;
			deger = tablo[satir][sutun]-1;
			if (kon[deger] != 0)
				return 0;
			else
				kon[deger] = 1;
		}
		sifirla(kon);
	}
	/* Her sütunda her rakamdan yalnızca bir tane olmasını denetliyor */
	for (sutun=0; sutun<9; ++sutun) {
		for (satir=0; satir<9; ++satir) {
			deger = tablo[satir][sutun]-1;
			if (kon[deger] != 0)
				return 0;
			kon[deger] = 1;
		}
		sifirla(kon);
	}
	/* Her 3x3'lük karede her rakamdan yalnızca bir tane olmasını denetliyor */
	for (kare=0; kare<9; ++kare) {
		for (kutu=0; kutu<9; ++kutu) {
			satir = kare/3*3+kutu/3;
			sutun = kare%3*3+kutu%3;
			deger = tablo[satir][sutun]-1;
			if (kon[deger] != 0)
				return 0;
			kon[deger] = 1;
		}
		sifirla(kon);
	}
	return 1;
}
/* Parametresindeki diziyi sıfırlıyor */
void sifirla(char dizi[9])
{
	int deger;
	for (deger=0; deger<9; ++deger)
		dizi[deger] = 0;
	return;
}