cs:c_language:sudoku
Return to Home page
If you found any error, or if you want to partecipate to the editing of this wiki, please contact: admin [at] skenz.it
You can reuse, distribute or modify the content of this page, but you must cite in any document (or webpage) this url: https://www.skenz.it/cs/c_language/sudoku
Sudoku
Concepts:
Matrices, function, algorithms of medium complexity
Text:
Solve the sudoku game, given a 9×9
matrix containing numbers between 0
and 9
. The numbers 0
represents the unknown numbers and the must be replaced by the program providing a solution to the sudoku.
For instance, given the following matrix, with 6
unknown numbers:
2 | 3 | 5 | 6 | 0 | 9 | 4 | 7 | 1 |
4 | 0 | 1 | 5 | 7 | 2 | 8 | 6 | 3 |
7 | 6 | 8 | 1 | 3 | 4 | 5 | 2 | 9 |
1 | 5 | 9 | 7 | 2 | 0 | 6 | 4 | 8 |
3 | 2 | 6 | 8 | 4 | 1 | 7 | 9 | 5 |
8 | 4 | 7 | 0 | 5 | 6 | 3 | 1 | 2 |
6 | 8 | 2 | 3 | 9 | 0 | 1 | 5 | 4 |
5 | 7 | 4 | 2 | 1 | 8 | 0 | 3 | 6 |
9 | 1 | 3 | 4 | 6 | 5 | 2 | 8 | 7 |
the solution is:
2 | 3 | 5 | 6 | 8 | 9 | 4 | 7 | 1 |
4 | 9 | 1 | 5 | 7 | 2 | 8 | 6 | 3 |
7 | 6 | 8 | 1 | 3 | 4 | 5 | 2 | 9 |
1 | 5 | 9 | 7 | 2 | 3 | 6 | 4 | 8 |
3 | 2 | 6 | 8 | 4 | 1 | 7 | 9 | 5 |
8 | 4 | 7 | 9 | 5 | 6 | 3 | 1 | 2 |
6 | 8 | 2 | 3 | 9 | 7 | 1 | 5 | 4 |
5 | 7 | 4 | 2 | 1 | 8 | 9 | 3 | 6 |
9 | 1 | 3 | 4 | 6 | 5 | 2 | 8 | 7 |
Remember that the following three rules must be verified by a 9×9
matrix, to be a solution of the sudoku game:
- Each row (composed of
9
elements) must contains all the number between1
and9
. For instance, the last row verifies this rule:
9 | 1 | 3 | 4 | 6 | 5 | 2 | 8 | 7 |
- Each column (composed of
9
elements) must contains all the number between1
and9
. For instance, the first column on the left verifies this rule:
2 |
4 |
7 |
1 |
3 |
8 |
6 |
5 |
9 |
- The
9×9
matrix can be subdivided into9
submatrices of dimension3×3
. Each of the9
submatrices must contains all the number between1
and9
. For instance, the3×3
matrix in the middle of the9×9
matrix verifies this rule:
7 | 2 | 3 |
8 | 4 | 1 |
9 | 5 | 6 |
Solution:
- sudoku.c
/* Solve the sudoku game, given a ''9x9'' matrix containing numbers between ''0'' and ''9''. The numbers ''0'' represents the unknown numbers and the must be replaced by the program providing a solution to the sudoku. */ #include <stdio.h> /* Dimension of a square sudoku matrix */ #define D 9 /* Print the sudoku matrix */ void print_matr(int m[][D], int nr, int nc){ int r, c; for (r=0; r<nr; r++) { for (c=0; c<nc-1; c++) printf("%d ", m[r][c]); printf("%d\n", m[r][nc-1]); } } /* Verify if the sudoku matrix m is a valid sudoku solution, in this case the function returns 1, otherwise the function returns 0 */ int sudoku_matrix_verify(int m[][D], int dim) { int r, c, n, found, r_sm, c_sm; /* Analyze if all rows contains the numbers between 1 and 9 */ for (r=0; r<dim; r++) { /* Fix the row */ for (n=1; n<=9; n++) { /* Verify all the numbers from 1 to 9 */ found = 0; for (c=0; c<dim && !found; c++) { if (m[r][c] == n) found = 1; } if (found == 0) return 0; } } /* Do the same for all the columns */ for (c=0; c<dim; c++) { for (n=1; n<=9; n++) { found = 0; for (r=0; r<dim && !found; r++) { if (m[r][c] == n) found = 1; } if (found == 0) return 0; } } /* Analyze all the 9 submatrices of dimension 3x3 */ /* Select a specific submatrix */ for (r_sm=0; r_sm<dim; r_sm+=3) { for (c_sm=0; c_sm<dim; c_sm+=3) { for (n=1; n<=9; n++) { /* Verify all the numbers from 1 to 9 */ /* ...checking if the number is contained in the submatrix */ found = 0; for (r=r_sm; r<r_sm+3 && !found; r++) { for (c=c_sm; c<c_sm+3 && !found; c++) { if (m[r][c] == n) found = 1; } } if (found == 0) return 0; } } } return 1; } int main() { /* The input matrix with unknown numbers */ int m[D][D] = { {2,3,5,6,0,9,4,7,1}, {4,0,1,5,7,2,8,6,3}, {7,6,8,1,3,4,5,2,9}, {1,5,9,7,2,0,6,4,8}, {3,2,6,8,4,1,7,9,5}, {8,4,7,0,5,6,3,1,2}, {6,8,2,3,9,0,1,5,4}, {5,7,4,2,1,8,0,3,6}, {9,1,3,4,6,5,2,8,7} }; /* The correct solution of the sudoku is... */ /* int m[D][D] = { */ /* {2,3,5,6,8,9,4,7,1}, */ /* {4,9,1,5,7,2,8,6,3}, */ /* {7,6,8,1,3,4,5,2,9}, */ /* {1,5,9,7,2,3,6,4,8}, */ /* {3,2,6,8,4,1,7,9,5}, */ /* {8,4,7,9,5,6,3,1,2}, */ /* {6,8,2,3,9,7,1,5,4}, */ /* {5,7,4,2,1,8,9,3,6}, */ /* {9,1,3,4,6,5,2,8,7} */ /* }; */ int unknown_r[D*D], unknown_c[D*D], n_i=0; int comb[D]; int r, c, i; int res; print_matr(m, D, D); /* Found the position of the 0s (i.e., unknown numbers) and store their lines and columns */ for (r=0; r<D; r++) { for (c=0; c<D; c++) { if (m[r][c] == 0) { unknown_r[n_i] = r; unknown_c[n_i] = c; n_i++; } } } printf("\nUnknown numbers: %d\n", n_i); /* The algorithm tries all the possible combinations of numbers, substituting the numbers 0 of the sudoku matrix with the number contained in the vector comb, which is initialized with all 1. The program then verify if a given combination is a correct solution */ for (i=0; i<n_i; i++) comb[i] = 1; do { /* Insert a specific combination into the sudoku matrix */ for(i=0; i<n_i; i++) { m[unknown_r[i]][unknown_c[i]] = comb[i]; } /* Verify if the solution is correct */ res = sudoku_matrix_verify(m, D); /* Generate a new possible combination */ comb[0]++; for(i=0; i<n_i-1; i++) if (comb[i]>9){ comb[i] = 1; comb[i+1]++; } if (res==1){ printf("\nSolution:\n"); print_matr(m, D, D); } /* }while(res==0 && comb[n_i-1]!=10); */ }while(comb[n_i-1]!=10); return 0; }
If you found any error, or if you want to partecipate to the editing of this wiki, please contact: admin [at] skenz.it
You can reuse, distribute or modify the content of this page, but you must cite in any document (or webpage) this url: https://www.skenz.it/cs/c_language/sudoku
/web/htdocs/www.skenz.it/home/data/pages/cs/c_language/sudoku.txt · Last modified: 2024/04/08 22:35 by 127.0.0.1