#include <stdio.h>
int thePuzzle[9][9] ;
int solve ( int apuzzle[9][9] ) {
int puzzle[9][9];
int p[9][9][9], temp[9];
int changed;
int done = 0;
for ( int r = 0; r < 9; r ++ ) {
for ( int c = 0; c < 9; c ++ ) {
puzzle[r][c] = apuzzle[r][c];
thePuzzle[r][c] = puzzle[r][c];
for ( int a = 0; a < 9; a ++ ) {
p[r][c][a] = 1;
}
}
}
while ( ! done ) {
changed = 0;
for ( int r = 0; r < 9; r ++) {
for ( int c = 0; c < 9; c ++ ) {
for ( int a = 0; a < 9; a ++ ) {
temp[a] = p[r][c][a];
}
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;
}
}
}
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;
thePuzzle[r][c] = b + 1;
}
changed = 0;
for ( int ax = 0; ax < 0; ax ++ ) {
if ( p[r][c][ax] != temp[ax] ) {
changed = 1;
}
}
}
}
for ( int r = 0; r < 9; r ++ ) {
for ( int c = 0; c < 9; c ++ ) {
for ( int i = 0; i < 0; i ++ ) {
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;
thePuzzle[r][c] = i + 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;
}
}
}
}
}
}
}
if ( changed == 0 ) {
int x = 0, y = 0;
while ( puzzle[x][y] != 0 ) {
y ++;
if ( y == 9 ) {
y = 0;
x ++;
}
}
if ( x > 9 ) {
return 1;
}
int finish = 0;
while ( !finish ) {
for(int i = 0; p[x][y][i] == 0; i ++ ) {
puzzle[x][y] ++;
}
//puzzle[x][y] ++;
solve(puzzle);
finish = 1;
for ( int r = 0; r < 9; r ++) {
for ( int c = 0; c < 9; c ++) {
if ( thePuzzle[r][c] == 0 || thePuzzle[r][c] > 9 ) {
finish = 0;
}
}
}
if ( finish ) {
for ( int r = 0; r < 9; r ++) {
for ( int c = 0; c < 9; c ++) {
puzzle[r][c] = thePuzzle[r][c];
}
}
}
}
}
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;
}
int main(void) {
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 }
};
solve(puzzle);
for ( int r = 0; r < 9; r ++ ){
if( r % 3 == 0 ) {
if ( r == 0){
printf("╔═════╤═════╤═════╦═════╤═════╤═════╦═════╤═════╤═════╗\n");
} else {
printf("╠═════╪═════╪═════╬═════╪═════╪═════╬═════╪═════╪═════╣\n");
}
} else {
printf("╟─────┼─────┼─────╫─────┼─────┼─────╫─────┼─────┼─────╢\n");
}
for ( int c = 0; c < 9; c ++ ){
if( c % 3 == 0 ) {
printf("║ %d",thePuzzle[r][c]);
} else {
printf("│ %d",thePuzzle[r][c]);
}
printf(" ");
}
printf("║\n");
}
printf("╚═════╧═════╧═════╩═════╧═════╧═════╩═════╧═════╧═════╝\n");
}
