title: Futoshiki C recursive solver
body: <p>So i have this program that should solve a futoshiki puzzle in C
  wich is loaded from a text file having this formatting :</p>
  
  <pre>
  5
  0 | 0 | 0 | 0 | 0
  - - - - v - - - - 
  0 &gt; 0 | 0 | 0 | 3
  - - - - - - - - - 
  0 | 0 &lt; 2 | 0 | 0
  - - - - v - - - - 
  0 | 0 | 0 | 0 | 4
  ^ - v - - - - - - 
  0 | 0 | 0 | 0 | 0
  </pre>
  
  <p>where 5 is the size of the matrix, and the numbers adjcent to the operators <code>&lt;</code>, <code>&gt;</code>, <code>^</code>, <code>v</code> must satisfy the condition imposed by them, from the file all the characters on rows are divided by spaces 
  eg <code>0 |</code>...
  So I've managed to load the file, to check if it satisfies the math operators conditions, but I'm stuck on the recursive function</p>
  
  <p>What I'd like to know:</p>
  
  <p>Did i choose the right way to store the matrix or I've should have divided the numbers from the logical operators ?</p>
  
  <p>How could I perform an recursive expansion on the matrix and how could I track the used number in a certain step(in case I would have to backtrack)?</p>
  
  <p>eg. let's say I arrive at <code>index[j][j]</code> where <code>j&lt;n</code> (size of matrix) , starting from there I would have to decrement <code>j</code> ("touching") only numbers and check if the sub-matrix satisfies the conditions </p>
  
  <p>Here's what I've managed to code so far.</p>
  
  <p>where :</p>
  
  <p><code>char **readmat(int *n);</code>     //reads the matrix from the file eliminating the spaces between chars</p>
  
  <p><code>void print(char **mat,int n);</code> //prints the stored matrix</p>
  
  <p><code>int check(char **mat,int n);</code>  //checks if items of a matrix of size n satisfies the math operators</p>
  
  <p><code>int expand (char **mat,int n,int i);</code> //this should be the recursive functions that gets an element at a time and checks if there's any condition to be satisfied, if so, increments it </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  
  char **readmat(int *n);
  void print(char **mat,int n);
  int check(char **mat,int n); 
  int expand (char **mat,int n,int i);
  
  int main(int argc, char *argv[])
    {
    char **mat;
    int n, j;
  
    mat=readmat(&amp;n);
  
    if(mat == NULL)
       return 1;
  
    if(check(mat,n)){
       print(mat,n);
    }
    else if(expand(mat,n,0)==1){
        print(mat,n);
    }
    else {
        printf("Nessuna soluzione trovata.\n");
    }
  
    for(j=0; j&lt;=n;j++)
         free(mat[j]);
    free(mat);
  
    system("PAUSE");  
    return 0;
  }
  
  char **readmat(int *n){
       FILE *fp;
       char *line,nome[100];
       int i,j,k;
       char **mat;
  
       printf("Inserire il nome del file: ");
       scanf("%s",nome);
       fp=fopen(nome,"r");
       if(fp==NULL){
       printf("Errore apertura file");
       return NULL;
   }
  
   if(fgets(nome,100,fp)==NULL){
       printf("Formato file non valido\n");
       fclose(fp);
       return NULL;
   }
   if(sscanf(nome,"%d",n)!=1){
       printf("Errore nei parametri del file\n");
       fclose(fp);
       return NULL;    
   }
  
   (*n)=(((*n)*2)-1);
  
  
   mat=(char**)malloc((*n)*sizeof(char*));
   for(i=0;i&lt;=(*n);i++)
      mat[i]=(char*)malloc((*n)*sizeof(char));
  
   line=(char*)malloc(2*(*n)*sizeof(char));
  
   i=0;
  
   while(i&lt;=2*(*n) &amp;&amp; fgets(line,2*(*n)+2,fp)!=NULL){
      j=0;
      k=0;
      while(j&lt;=2*(*n)){
          if(line[j]!=' '){
             mat[i][k]=line[j];
             k++;
          }  
          j++;
      }
      i++;
   }   
   return mat;
   //print(mat, (*n));  
  }
  
  void print(char **mat,int n){
      int i=0,j=0;
      for (i=0; i&lt;n; i++) {
       for (j=0; j&lt;n; j++) {
          printf("%c", mat[i][j]);
       }
       printf("\n");
      }
  }
  
  int check(char **mat,int n) {
  
      int i,j;
      int k=1;
  
      for(i=0;i&lt;n;i++){
          for(j=0;j&lt;n;j++){
              if(mat[i][j]=='&lt;'){
                  if(mat[i][j-1] &gt;= mat[i][j+1])
                      k=0;                               
              }
              else if(mat[i][j]=='&gt;'){
                  if(mat[i][j-1] &lt;= mat[i][j+1])
                      k=0;
              }   
              else if(mat[i][j]=='^'){
                  if(mat[i-1][j] &gt;= mat[i+1][j])
                      k=0;    
              }
              else if(mat[i][j]=='v'){
                  if(mat[i-1][j] &lt;= mat[i+1][j])
                      k=0;                      
              }                            
          }
      }
      return k;                                
  }
  int expand (char **mat,int n,int i){
  
      int j=i/n;
      int k=i%n;
      int p;
  
      if(i&gt;=n*n){
  
          return 1;
      }       
      else{
          if((mat[j][k]&gt;47)&amp;&amp;(mat[j][k]&lt;58)){
              if(mat[j][k]=='0'){     
                  expand(mat,n,i+2);
              }   
              for (p=(mat[j][k]-48); p&lt;(10-(mat[j][k]-48)); p++) {              
                  mat[j][k]=48+p;                        
                  if (check(mat,i)) {
                if (expand(mat, n, i+2)) {
                     return 1;
                      }
                  }
              }
              i-=2;
              mat[j][k]='0';
          }
      }           
      return 0;
  }
  </code></pre>
  
  <p>solution of the example : As you can see the logical conditions area clearly satisfied </p>
  
  <pre><code>0 | 0 | 1 | 0 | 0
  - - - - v - - - - 
  1 &gt; 0 | 0 | 0 | 3
  - - - - - - - - - 
  0 | 0 &lt; 2 | 0 | 0
  - - - - v - - - - 
  0 | 1 | 0 | 0 | 4
  ^ - v - - - - - - 
  1 | 0 | 0 | 0 | 0
  </code></pre>