cs:c_language: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[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: wiki [at] altervista.org

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

/membri/wiki/data/pages/cs/c_language/sudoku.txt · Last modified: 2015/11/03 15:26 by Z