/* 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;
}