#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int teste(int** t,int x , int y); 
void recursive( int** t,int x,int y);
void affichage( int** t);
 
 int main()
{
 
 
  int** t;
  int x,y,i,j,k,m=1,e=0,v,f=2,w,z,g,c;
    t = (int**) malloc(9 * sizeof(int));   
	for (i = 1; i <9 ; i++)
	    t[i] = (int*) malloc(9 * sizeof(int));
    for(i=1;i<9;i++)
    { for(j=1;j<9;j++)
      {
                   t[i][j]=0;
      }
      printf("\n\n");
    }
 x=1;y=1;  
 printf("1\n\n");
 recursive(t,x,y);
 affichage(t); 
    v=8;
    w=1;
      while(v>0) 
      {  
           while(w<9) 
           {                         
                         if(t[v][w]==7)     {                                                                                                                                                                                       
                                               t[v][w]=0;                                               
                                               w=w+1; 
                                               printf("%d \n\n",f);
                                               recursive(t,v,w);f++; 
                                               affichage(t);break;                                                                                               
                                            }   
              w++;                                                                      
            }
            for(w=1;w<9;w++)
               { if( t[v][w]==7) break; }               
      if(f==93) {printf("bye bye..."); break;}
      }       
getch();       
}
 
void recursive( int** t,int x,int y)
{     
int B,i,j,k,r=0;
    B=0;     
  if(x<9)
  {   
         while(t[x][y]!=7&&y<9) { 
                                           if( teste(t,x,y)==0) 
                                                            {                                                              
                                                                  t[x][y]=7;
                                                                  B=1; break;                                              
                                                            }
                                           if (B==0) y++;                                 
                                 }     
         if(B==0)       { 
                                  k=1;
                             do  {                                            
                                             if(t[x-1][k]==7)     {t[x-1][k]=0;r=1;break;}
                                             k++;                       
                                  } while(r==0);                                                                                                  
                                  recursive(t,x-1,k+1);
                        }                                                              
  x=x+1;
 if(B==1) {y=1;recursive(t,x,y);}                         
 }         
}
 
 
int teste(int** t,int x , int y )
{ int i,j,w;
w=0;
 for(i=y+1;i<9;i++)
    {
      if(t[x][i]==7) w=1;            
    }
 for(i=y-1;i>0;i--)
    {
      if(t[x][i]==7) w=1;          
    }
 
 for(i=x+1;i<9;i++)
     {
      if(t[i][y]==7) w=1;                                
     } 
 for(i=x-1;i>0;i--)
     {
      if(t[i][y]==7) w=1;                                
     } 
 
 for(i=x+1,j=y+1;i<9&&j<9;i++,j++)
     {
      if(t[i][j]==7) w=1;                                
     } 
 
 
 
   i=x-1;j=y-1;                 
    while  (i>0 && j>0)
   { 
        if(t[i][j]==7)  w=1;
         i--;j--;
 
   }   
   i=x-1;j=y+1;                                            
    while ( j<9&&i>0)
   {
          if(t[i][j]==7) w=1;
          i--;j++;
    }
     i=x+1;j=y-1;                                            
    while ( j>0&&i<9)
   {
          if(t[i][j]==7) w=1;
          i++;j--;
    }
   return w;   
}
 
void affichage( int** t)
{  int i,j;
      for(i=1;i<9;i++)
         { for(j=1;j<9;j++)
           {
                     printf("%d | ",t[i][j]);
           }
           printf("\n");
         }
   printf("\n\n\n\n");
   getch();
}