# How To Wiki

### Site Tools

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 between `1` and `9`. 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 between `1` and `9`. 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 into `9` submatrices of dimension `3×3`. Each of the `9` submatrices must contains all the number between `1` and `9`. For instance, the `3×3` matrix in the middle of the `9×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++;
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;
}``` 