User Tools

Site Tools


cs:c_language:sudoku
Return to Home page

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cs:c_language:sudoku [2019/02/26 14:35]
cs:c_language:sudoku [2020/11/26 23:18] (current)
Line 1: Line 1:
 +====== Sudoku ======
 +**Concepts:**\\ 
 +Matrices, function, algorithms of medium complexity
 +
 +**Text:**\\
 +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.
 +
 +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 ''9x9'' 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 ''9x9'' matrix can be subdivided into ''9'' submatrices of dimension ''3x3''. Each of the ''9'' submatrices must contains all the number between ''1'' and ''9''. For instance, the ''3x3'' matrix in the middle of the ''9x9'' matrix verifies this rule:
 +
 +|7|2|3|
 +|8|4|1|
 +|9|5|6|
 +
 +
 +**Solution:**\\
 +
 +<file C 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;
 +}
 +</file>
  

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?rev=1551188114&do=diff