#include <stdio.h>
void coz(void);
int coz1(void);
void tekBul(void);
void dene(int say);
void ihtimalBul(void);
int kontrol(void);
void bas(void);
int tablo[9][9] = {0};
int olasi[9][9][9] = {0};

int main(void)
{
	FILE *fin = fopen("sudoku.in","r");
	FILE *fout;
	char c;
	int i, j;
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) {
			fscanf(fin,"%c",&c);
			tablo[i][j] = c-'0';
		}
		fscanf(fin,"\n");
	}
	fclose(fin);
	printf("\n--Sudoku solver by Can Guler---\n\n");
	bas();
	coz();
	c = kontrol();
	if (c == 1)
		printf("-------Sudoku was solved-------\n\n");
	else
		printf("-----Sudoku wasn't solved------\n\n");		
	bas();
	fout = fopen("sudoku.out","w");
	for (i=0; i<9; ++i) {
	for (j=0; j<9; ++j) {
		fprintf(fout,"%d",tablo[i][j]);
	}
	fprintf(fout,"\n");
	}
	fclose(fout);
	return 0;
}
void coz(void)
{
	int c;
	while (1) {
		ihtimalBul();
		tekBul();
		c = coz1();
		if (c == 0) {
			dene(0);
			break;
		}
	}
}
int coz1(void)
{
	int i, j, k;
	int say, dogru, sonuc;
	sonuc = 0;
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) {
			if (tablo[i][j] != 0)
				continue;
			say = 0;
			for (k=0; k<9; ++k) {
				if (olasi[i][j][k] == 0) {
					say++;
					dogru = k;
				}
			}
			if (say == 1) {
				tablo[i][j] = dogru+1;
				sonuc = 1;
			}                
		}
	}
	return sonuc;
}
void tekBul(void)
{
	char say, sonuc, dogru, dogru1;
	int i, j, k, l, m;
	sonuc = 0;
	for (k=0; k<9; ++k) {
		for (i=0; i<9; ++i) {
			say = 0;
			for (j=0; j<9; ++j) {
				if (tablo[i][j] == 0)
					if (olasi[i][j][k] == 0) {
					say++;
					dogru = j;
					}
				}
			if (say == 1) {
				for (l=0; l<9; ++l) {
					olasi[i][dogru][l] = 1;
				}
				olasi[i][dogru][k] = 0;
				sonuc = 1;
			}
		}
	}   
	for (k=0; k<9; ++k) {
		for (i=0; i<9; ++i) {
			say = 0;
			for (j=0; j<9; ++j) {
				if (tablo[j][i] == 0)
					if (olasi[j][i][k] == 0) {
					say++;
					dogru = j;
					}
			}
			if (say == 1) {
				for (j=0; j<9; ++j) {
					olasi[dogru][i][j] = 1;
				}
				olasi[dogru][i][k] = 0;
				sonuc = 1;
			}
		}
	}   
	for (k=0; k<9; ++k) {
		for (i=0; i<3; ++i) {
			for (j=0; j<3; ++j) {
				say = 0;
				for (l=0; l<3; ++l) {
					for (m=0; m<3; ++m) {
						if (tablo[3*i+l][3*j+m] == 0)
							if (olasi[3*i+l][3*j+m][k] == 0) {
								say++;
								dogru = l;
								dogru1 = m;                            
							}
					}
				}
				if (say == 1) {
					for (l=0; l<9; ++l) {
						olasi[3*i+dogru][3*j+dogru1][l] = 1;
					}
					olasi[3*i+dogru][3*j+dogru1][k] = 0;
					sonuc = 1;
				}
			}
		}
	}
	return;
}



void dene(int say)
{
	int yedek[9][9];
	int i, j, k, l, m, c;
	int cnt = 0;
	for (i=0; i<9; ++i)
		for (j=0; j<9; ++j)
			yedek[i][j] = tablo[i][j];
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) {
			if (tablo[i][j] == 0) {
				for (k=0; k<9; ++k) {
					if (olasi[i][j][k] == 0) {
						if (say == cnt) {
							tablo[i][j] = k+1;
							coz();
							c = kontrol();
							if (c == 0) {
								for (l=0; l<9; ++l)
									for (m=0; m<9; ++m)
										tablo[l][m] = yedek[l][m];
								dene(say+1);
								return;
							} else {
								return;
							}
						} else {
							cnt++;
						}
					}
				}
			}
		}
	}
	return;
}
void ihtimalBul(void)
{
	int i, j, k, l;
	for (i=0; i<9; ++i)
		for (j=0; j<9; ++j)
			for (k=0; k<9; ++k)
				olasi[i][j][k] = 0;
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) {
			if (tablo[i][j] != 0)
				continue;
			for (k=0; k<9; ++k) {
				if (tablo[i][k] != 0)
					olasi[i][j][tablo[i][k]-1] = 1;
				if (tablo[k][j] != 0)
					olasi[i][j][tablo[k][j]-1] = 1;
			}
			for (k=(i/3)*3; k<(i/3)*3+3; ++k) {
				for (l=(j/3)*3; l<(j/3)*3+3; ++l) {
					if (tablo[k][l] != 0)
						olasi[i][j][tablo[k][l]-1] = 1;
				}
			}
		}
	}
	return;
}

int kontrol(void)
{
	int i, j;
	char kon[9] = {0};
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) {
			if (tablo[i][j] > 9 || tablo[i][j] < 1)
				return 0;
			if (kon[tablo[i][j]-1] != 0)
				return 0;
			else
				kon[tablo[i][j]-1] = 1;
		}
		for (j=0; j<9; ++j)
			kon[j] = 0;
		for (j=0; j<9; ++j)
			if (kon[tablo[j][i]-1] != 0)
				return 0;
			else
				kon[tablo[j][i]-1] = 1;
		for (j=0; j<9; ++j)
			kon[j] = 0;
		for (j=0; j<9; ++j)
			if (kon[tablo[i/3*3+j/3][i%3*3+j%3]-1] != 0)
				return 0;
			else
				kon[tablo[i/3*3+j/3][i%3*3+j%3]-1] = 1;
		for (j=0; j<9; ++j)
			kon[j] = 0;
	}
	return 1;
}

void bas(void)
{
	int i, j;
	printf("+---------+---------+---------+\n");
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) {
			if (j%3 == 0)
				printf("|");
			if (tablo[i][j] == 0)
				printf(" - ");
			else
				printf(" %d ",tablo[i][j]);
		}
		printf("|\n");
		if (i%3 == 2)
			printf("+---------+---------+---------+\n");
	}
	printf("\n");
	return;
}