User Tools

Site Tools


cs:c_language:sudoku
Return to Home page

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:

235609471
401572863
768134529
159720648
326841795
847056312
682390154
574218036
913465287

the solution is:

235689471
491572863
768134529
159723648
326841795
847956312
682397154
574218936
913465287

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:
913465287
  • 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:
723
841
956

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: http://wiki.altervista.org/cs/c_language/sudoku
/membri/wiki/data/pages/cs/c_language/sudoku.txt · Last modified: 2015/11/03 15:26 by Z


Policy sui Cookie