#include <stdio.h>
#include <stdlib.h>
int puzzle[9][9] =
{
{ 0, 0, 6, 0, 0, 0, 0, 0, 4 },
{ 0, 0, 0, 8, 6, 0, 7, 3, 0 },
{ 0, 4, 0, 3, 5, 0, 0, 0, 2 },
{ 1, 7, 0, 4, 0, 0, 6, 0, 0 },
{ 0, 9, 0, 0, 0, 0, 0, 8, 0 },
{ 0, 0, 8, 0, 0, 6, 0, 1, 7 },
{ 2, 0, 0, 0, 8, 1, 0, 4, 0 },
{ 0, 6, 7, 0, 4, 3, 0, 0, 0 },
{ 8, 0, 0, 0, 0, 0, 3, 0, 0 }
};
int ogPuzzle[9][9];
int function () {
for ( int x = 0; x < 9; x ++ ) {
for ( int y = 0; y < 9; y ++ ) {
ogPuzzle[x][y] = puzzle[x][y];
}
}
int zeroes = 0;
int done = 0;
for ( int r = 0; r < 9; r ++ ) {
for ( int c = 0; c < 9; c ++ ) {
if ( puzzle[r][c] == 0 ) {
zeroes ++;
}
}
}
int fill[52];
for ( int i = 0; i < 52; i ++ ) {
fill[i] = 1;
}
int a = 0;
while ( puzzle[8][8] < 2 ) {
fill[0] ++;
for ( int i = 0; i < 52; i ++ ) {
if ( fill[i] > 9 ) {
fill[i] = 0;
fill[i+1] ++;
}
}
/*for ( int i = 0; i < 52; i ++ ) {
fill[i] = rand() % 10;
}*/
int count = 0;
for ( int r = 0; r < 9; r ++ ) {
for ( int c = 0; c < 9; c ++) {
if( ogPuzzle[r][c] == 0 ) {
puzzle[r][c] = fill[count];
count ++;
}
}
}
done = 1;
for ( int r = 0; r < 9; r ++ ) {
int check[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for ( int c = 0; c < 9; c ++ ) {
check[puzzle[r][c]-1] ++;
}
for ( int i = 0; i < 9; i ++ ) {
if (check[i] != 1) {
done = 0;
}
}
}
for ( int c = 0; c < 9; c ++ ) {
int check[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for ( int r = 0; r < 9; r ++ ) {
check[puzzle[r][c]-1] ++;
}
for ( int i = 0; i < 9; i ++ ) {
if (check[i] != 1) {
done = 0;
}
}
}
for ( int r = 0; r < 9; r += 3 ) {
for ( int c = 0; c < 9; c += 3 ) {
int check[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for ( int rx = r; rx < r + 3; rx ++ ) {
for ( int cx = c; cx < c + 3; cx ++ ) {
check[puzzle[rx][cx]-1] ++;
}
}
for ( int i = 0; i < 9; i ++ ) {
if (check[i] != 1) {
done = 0;
}
}
}
}
a ++;
}
printf("%d\n",fill[0]);
return 1;
}
int main(void) {
//int p[9][9][9];
//for( int i = 0; i < 9; i ++ ) {
// scanf("%1d %1d %1d %1d %1d %1d %1d %1d %1d", &puzzle[i][0], &puzzle[i][1], &puzzle[i][2], &puzzle[i][3], &puzzle[i][4], &puzzle[i][5], &puzzle[i][6], &puzzle[i][7], &puzzle[i][8]);
//}
function();
/* for ( int r = 0; r < 9; r ++ ) {
for ( int c = 0; c < 9; c ++ ) {
for ( int a = 0; a < 9; a ++ ) {
p[r][c][a] = 0;
}
}
}
int changed = 0, done = 0;
while ( ! done ) {
changed = 0;
for ( int r = 0; r < 9 ; r ++ ) {
for ( int c = 0; c < 9; c ++ ) {
int temp[9];
for ( int a = 0; a < 9; a ++){
temp[a] = p[r][c][a];
p[r][c][a] = 1;
}
for ( int x = 0; x < 9; x ++ ) {
if ( puzzle[r][x] != 0 && x != c ) {
p[r][c][ (puzzle[r][x]-1) ] = 0;
}
}
for ( int y = 0; y < 9; y ++ ) {
if ( puzzle[y][c] != 0 && y != r ) {
p[r][c][ (puzzle[y][c])-1 ] = 0;
}
}
for ( int r1 = (r/3)*3 ; r1 < (r/3)*3 + 3; r1 ++) {
for ( int c1 = (c/3)*3 ; c1 < (c/3)*3 + 3; c1 ++) {
if ( puzzle[r1][c1] != 0 && !( r1 == r && c1 == c ) ) {
p[r][c][ (puzzle[r1][c1])-1 ] = 0;
}
}
}
for ( int a = 0; a < 9; a ++ ) {
if ( p[r][c][a] != temp[a] ) {
changed = 1;
}
}
int sum = 0;
for ( int a = 0; a < 9;a ++){
sum += p[r][c][a];
}
if ( sum == 1 ) {
int b = 0;
while ( p[r][c][b] == 0 ) {
b ++;
}
puzzle[r][c] = b + 1;
}
}
}
for ( int r = 0; r < 9; r ++ ) {
for( int c = 0; c < 9; c ++ ) {
for ( int i = 0; i < 9; i ++ ) {
if ( p[r][c][i] == 1 ) {
int yes = 0;
for ( int x = 0; x < 9; x ++ ) {
if ( p[r][x][i] == 1 && x != c ) {
yes = 1;
}
}
for ( int y = 0; y < 9; y ++ ) {
if ( p[y][c][i] == 1 && y != r ) {
yes = 1;
}
}
for ( int r1 = (r/3)*3 ; r1 < (r/3)*3 + 3; r1 ++) {
for ( int c1 = (c/3)*3 ; c1 < (c/3)*3 + 3; c1 ++) {
if ( p[r1][c1][i] == 1 && !( r1 == r && c1 == c ) ) {
yes = 1;
}
}
}
if ( yes == 0 ) {
puzzle[r][c] = i+1;
}
}
}
}
}
if ( changed == 0 ) {
int r = 0, c = 0, a = -1;
while ( c < 9 && puzzle[r][c] != 0 ) {
r ++;
if ( r = 9 ) {
r = 0;
c ++;
}
}
if ( c == 9 ) {
return 0;
}
while ( function() == 0 ) {
a ++;
while ( p[r][c][a] = 0 ) {
a ++;
}
puzzle[r][c] = a + 1;
}
}
done = 1;
for ( int r = 0; r < 9; r ++ ) {
for ( int c = 0; c < 9; c ++) {
if ( puzzle[r][c] == 0 ) {
done = 0;
return 1;
}
}
}
} */
for ( int r = 0; r < sizeof puzzle / sizeof *puzzle; r ++ ){
if( r % 3 == 0 ) {
if ( r == 0){
printf("╔═════╤═════╤═════╦═════╤═════╤═════╦═════╤═════╤═════╗\n");
} else {
printf("╠═════╪═════╪═════╬═════╪═════╪═════╬═════╪═════╪═════╣\n");
}
} else {
printf("╟─────┼─────┼─────╫─────┼─────┼─────╫─────┼─────┼─────╢\n");
}
for ( int c = 0; c < sizeof puzzle[0] / sizeof *puzzle[0]; c ++ ){
if( c % 3 == 0 ) {
printf("║ %d",puzzle[r][c]);
} else {
printf("│ %d",puzzle[r][c]);
}
printf(" ");
}
printf("║\n");
}
printf("╚═════╧═════╧═════╩═════╧═════╧═════╩═════╧═════╧═════╝\n");
}
