/* | |
* | |
* | |
*/ | |
#include <stdio.h> | |
#include <stdlib.h> | |
#define MAXSOLUTIONS 5 | |
//--------------------------------------------- | |
int grid[9][9], solutions; | |
//--------------------------------------------- | |
static void reset_grid() | |
{ | |
int i, j; | |
for (i = 0; i < 9; i++) | |
for (j = 0; j < 9; j++) | |
{ | |
grid[i][j] = 0; | |
} | |
} | |
//----------------------------------------------- | |
static int CheckValueInGrid(int i,int j, int val) | |
{ | |
int k, m; | |
//check in row | |
for (k=0; k<9; k++) | |
{ | |
if (k!=j) | |
if (grid[i][k]==val) | |
return 0; | |
} | |
// check in column | |
for (m=0; m<9; m++) | |
{ | |
if (m!=i) | |
if (grid[m][j]==val) | |
return 0; | |
} | |
//check in subgrid | |
for (k=(i/3)*3; k<(i/3)*3+3; k++) | |
for (m=(j/3)*3; m<(j/3)*3+3; m++) | |
{ | |
if ((k!=i) || (m!=j)) | |
if (grid[k][m]==val) | |
return 0; | |
} | |
return 1; | |
} | |
//-------------------------------------------------- | |
//read soulotion from file | |
static int read_grid() | |
{ | |
int i, j, ch; | |
reset_grid(); | |
for (i = 0; i < 9; i++) | |
for (j = 0; j < 9; j++) | |
for (;;) | |
{ | |
ch = getchar(); | |
if (ch == EOF) | |
return -1; | |
if (ch == '.') | |
break; | |
if ('1' <= ch && ch <= '9') | |
{ | |
if (CheckValueInGrid(i, j, 1+ch-'1')) | |
{ | |
grid[i][j] = 1+ch-'1'; | |
break; | |
} | |
else | |
{ | |
return -1; | |
} | |
} | |
if (!isspace(ch) && ch != '|' && ch != '-' && ch != '+') | |
return -1; | |
} | |
for (;;) | |
{ | |
int ch = getchar(); | |
if (ch == EOF) | |
return 0; | |
if (!isspace(ch) && ch != '|' && ch != '-' && ch != '+') | |
return -1; | |
} | |
} | |
//--------------------------------------------------- | |
//print grid[][] in standard output | |
static void print_grid() | |
{ | |
int i, j; | |
for (i = 0; i < 9; i++) | |
{ | |
if (i%3 == 0) | |
printf("+---+---+---+\n"); | |
for (j = 0; j < 9; j++) | |
{ | |
if (j%3 == 0) | |
printf("|"); | |
printf("%d", grid[i][j]); | |
} | |
printf("|\n"); | |
} | |
printf("+---+---+---+\n\n"); | |
} | |
//----------------------------------------------------- | |
static int SearchSolution(int i, int j) | |
{ | |
int value; | |
if (j==9) | |
{ | |
j=0; | |
i++; | |
} | |
if (i==9) | |
{ //solution | |
print_grid(); | |
solutions++; | |
fprintf(stderr," %d solution(s) found !\n", solutions); | |
return solutions >= MAXSOLUTIONS; | |
} | |
if (grid[i][j]!=0) | |
{ | |
if (SearchSolution(i, j+1)) | |
return 1; | |
} | |
else | |
{ | |
for (value = 1; value < 10; value++) /* Try possible values. */ | |
if (CheckValueInGrid(i, j, value)) | |
{ | |
grid[i][j]=value; //new test value | |
if (SearchSolution(i, j+1)) | |
return 1; | |
} | |
grid[i][j]=0; //unrecord try | |
} | |
return 0; | |
} | |
//------------------------------------------------- | |
static int solution() | |
{ | |
if (read_grid()==-1) | |
{ | |
fprintf(stderr, "Invalid input matrix\n"); | |
return 1; | |
} | |
solutions = 0; | |
printf("Starting Matrix\n"); | |
print_grid(); | |
printf("\n\nSolving...\n\n"); | |
SearchSolution(0,0); | |
if (solutions == 0) | |
{ | |
fprintf(stderr, "No solution found\n"); | |
return 1; | |
} | |
return 0; | |
} | |
//------------------------------------------------------ | |
int main(int argc, char **argv) | |
{ | |
char *output = 0; | |
if (!freopen("SUDOKU.TXT" , "r", stdin)) | |
{ | |
fprintf(stderr,"input file SUDOKU.TXT does not exist.\n"); | |
return 1; | |
} | |
if (output && !freopen(output, "w", stdout)) | |
{ | |
perror(output); | |
return 1; | |
} | |
return solution(); | |
} | |
/* test input: | |
9 . . 7 . . . . 1 | |
1 . 6 . 4 . . . . | |
. . . 9 6 . 7 . 4 | |
2 . . . . . 5 9 . | |
. . 5 2 . 7 . . . | |
. 1 . . . 5 . 7 . | |
. 3 . . . . 1 . 6 | |
. . . . 3 . . 8 7 | |
. 2 8 . . . . . . | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment