/* Written by Georg Horn <horn@koblenz-net.de>

   Simple backtracking solution for solving sudoku puzzles.

   Reads a 9x9 matrix in the following form from standard input:

   0 0 0 8 0 0 0 6 0
   0 5 4 0 0 0 0 0 0
   0 0 0 0 0 0 0 1 9
   2 0 0 0 4 0 3 0 0
   0 0 9 3 0 0 0 7 0
   0 0 3 0 5 6 0 0 0
   0 3 0 0 0 4 0 0 1
   0 1 0 0 8 0 0 3 0
   4 0 7 9 1 0 0 8 0

   Does no error checking...
*/

#include <stdio.h>

typedef int feld[9][9];

void get_init_values(feld *f)
{
    int i, j;

    for (i = 0; i < 9; i++) {
	for (j = 0; j < 9; j++) {
	    (*f)[i][j] = 0;
	}
    }

    for (i = 0; i < 9; i++) {
	scanf("%d %d %d %d %d %d %d %d %d",
	    &(*f)[i][0], &(*f)[i][1], &(*f)[i][2], &(*f)[i][3], &(*f)[i][4],
	    &(*f)[i][5], &(*f)[i][6], &(*f)[i][7], &(*f)[i][8]);
    }
}

void print_feld(feld *f)
{
    int i, j;

    for (i = 0; i < 9; i++) {
	if (i > 0 && i % 3 == 0) {
	    printf("\n");
	}
	for (j = 0; j < 9; j++) {
	    if (j > 0 && j % 3 == 0) {
		printf(" ");
	    }
	    printf("%d ", (*f)[i][j]);
	}
	printf("\n");
    }
}

int check(feld *f, int i, int j)
{
    int k, l, i2, j2;

    for (k = 0; k < 9; k++) {
	if (k != j && (*f)[i][k] == (*f)[i][j]) {
	    return 0;
	}
    }

    for (k = 0; k < 9; k++) {
	if (k != i && (*f)[k][j] == (*f)[i][j]) {
	    return 0;
	}
    }

    i2 = (i / 3) * 3;
    j2 = (j / 3) * 3;

    for (k = i2; k < i2 + 3; k++) {
	for (l = j2; l < j2 + 3; l++) {
	    if (k != i && l != j && (*f)[k][l] == (*f)[i][j]) {
		return 0;
	    }
	}
    }

    return 1;
}

int get_loesung(feld *f, int i, int j)
{
    int wert;

    if ((*f)[i][j] != 0) {
	if (check(f, i, j)) {
	    if (i == 8 && j == 8) {
		return 1;
	    }
	} else {
	    return 0;
	}
	return get_loesung(f, (j < 8) ? i : i + 1, (j < 8) ? j + 1 : 0);
    }

    for (wert = 1; wert < 10; wert++) {
	(*f)[i][j] = wert;
	// printf("f[%d][%d]=%d\n", i, j, wert);
	if (check(f, i, j)) {
	    if (i == 8 && j == 8) {
		return 1;
	    }
	    if (get_loesung(f, (j < 8) ? i : i + 1, (j < 8) ? j + 1 : 0)) {
		return 1;
	    }
	}
    }

    (*f)[i][j] = 0;
    return 0;
}

int main(void)
{
    feld f;

    get_init_values(&f);
    printf("Input:\n");
    print_feld(&f);

    if (get_loesung(&f, 0, 0) > 0) {
	printf("\nSolution:\n");
	print_feld(&f);
    } else {
	printf("\nNo solution possible!\n");
    }

    return 0;
}