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

char sudoku[9][9];
char sudokuSolved[9][9];
int numberOfSolutions;

int loadSudoku(FILE *f) {
	int i = 0, j = 0;
	for (int k = 0; k < 81; k ++) {
		int ch = fgetc(f);
		if (ch == EOF) return 0;
		if ((ch < 48) || (ch > 57)) {
			fprintf(stderr, "spatne zadany vstupni udaj\n");
			exit(2);
		}
		sudoku[i][j] = ch - 48;
		i ++;
		if (i == 9) {i = 0; j++;}
	}
	return 1;
}

void writeSudoku(FILE *f) {
	int i = 0, j = 0;
	for (int k = 0; k < 81; k ++) {
		int ch = sudokuSolved[i][j] + 48;
		fputc(ch, f);
		i ++;
		if (i == 9) {i = 0; j++;}
	}
}

void copySudoku(void) {
	int i = 0, j = 0;
	for (int k = 0; k < 81; k ++) {
		sudokuSolved[i][j] = sudoku[i][j];
		i ++;
		if (i == 9) {i = 0; j++;}
	}
}

char getNextNumber(char *number, int row, int col) {
	for (; (*number) <= 9; (*number) ++) {
		int exists = 0;

		for (int i = 0; i < 9; i++) if (sudoku[i][col] == (*number)) {exists = 1;break;}
		if (exists) continue;
		for (int j = 0; j < 9; j++) if (sudoku[row][j] == (*number)) {exists = 1;break;}
		if (exists) continue;

		int mrow = ((row) / 3)*3, mcol = ((col) / 3)*3;
		for (int i = mrow; i < (mrow + 3); i++) {
			for (int j = mcol; j < (mcol + 3); j++) if (sudoku[i][j] == (*number)) {exists = 1;break;}
			if (exists) break;
		}
		if (exists) continue;
		
		return (*number);
	}
	(*number) = 0;
	return 0;
}

int nextGap(int *row, int *col) {
	while (1) {
		if (sudoku[*row][*col] == 0) return 0;
		(*col) ++;
		if ((*col) == 9) {
			(*col) = 0;
			(*row) ++;
			if ((*row) == 9) return 1;
		}
	}
}

int solve(int row, int col) {
	if (nextGap(&row, &col) == 1) {
		numberOfSolutions ++;
		if (numberOfSolutions == 1) copySudoku();
		return 0;
	}
	char lowestNumber = 1;
	while (1) {
		if ((sudoku[row][col] = getNextNumber(&lowestNumber, row, col)) == 0) return 0;
		if (solve(row, col) == 1) return 1;
	}
}