Solution: Below is the code to solve a sudoku.
/*
Input Matrix:
7 0 0 1 0 0 0 0 0
0 2 0 0 0 0 0 1 5
0 0 0 0 0 6 3 9 0
2 0 0 0 1 8 0 0 0
0 4 0 0 9 0 0 7 0
0 0 0 7 5 0 0 0 3
0 7 8 5 0 0 0 0 0
5 6 0 0 0 0 0 4 0
0 0 0 0 0 1 0 0 2
*/
#define TRUE 1
#define FALSE 0
#define N 9
int S[N+1][N+1] = {0,};
void printMat(int S[][N+1])
{
int i = 0;
int j = 0;
for(i=1; i<=N; i++) {
for(j=1; j<=N; j++) {
printf("%2d ", S[i][j]);
}
printf("\n");
}
}
void initMat(int S[][N+1])
{
S[1][1] = 7;
S[1][4] = 1;
S[2][2] = 2;
S[2][8] = 1;
S[2][9] = 5;
S[3][6] = 6;
S[3][7] = 3;
S[3][8] = 9;
S[4][1] = 2;
S[4][5] = 1;
S[4][6] = 8;
S[5][2] = 4;
S[5][5] = 9;
S[5][8] = 7;
S[6][4] = 7;
S[6][5] = 5;
S[6][9] = 3;
S[7][2] = 7;
S[7][3] = 8;
S[7][4] = 5;
S[8][1] = 5;
S[8][2] = 6;
S[8][8] = 4;
S[9][6] = 1;
S[9][9] = 2;
}
int permitted(int S[][N+1], int i, int j, int a)
{
int x;
for(x=1; x<=N; x++) {
if(S[i][x] == a) {
return FALSE;
}
}
for(x=1; x<=N; x++) {
if(S[x][j] == a) {
return FALSE;
}
}
return TRUE;
}
void solve(int S[][N+1], int i, int j)
{
int a = 0;
/*
* this row is filled, jump to next row
*/
if(j > N) {
j = 0;
i++;
}
/*
* all rows are filled, print sol. and exit
*/
if(i > N) {
printMat(S);
printf("\n");
exit(0);
}
/*
* each cell can take a value belonging to [1,9]
*/
for(a=1; a<=N; a++) {
/*
* cell is already occupied, move to next cell
*/
if (S[i][j]) {
solve(S, i, j+1);
return;
}
else if (permitted(S, i, j, a)) {
S[i][j] = a;
solve(S, i, j+1);
S[i][j] = 0;
} else {
continue;
}
}
}
int main()
{
initMat(S);
printMat(S);
printf("\n");
solve(S, 1, 1);
}
1 comment:
Why do we do x[i][j] = 0; after the solve call?
Post a Comment