#include <stdio.h>

// compute the classical knight tour

int legal_kmove(int *i, int *j, int dim_i, int dim_j, int isM)
{
  // returns 1 if (i,j) is a valid move, 0 elsewhere
  // if (i,j) is a valid move, compute new cohordinates - if necessary -
  // according to the Moebius shape of the chessboard
  
  int app=0,cnt, esito=0;
  if (*i>=1 && *i<= dim_i)
  {
     if (isM == 1) // is a Moebius chessboard 
     {
        /* new i j accordingly */
        if ((*j == dim_j+1) || (*j == dim_j+2))
		{
          *j=*j-dim_j;
          *i=(dim_i+1)-*i;
        }
        if ((*j == 0) || (*j == -1)) 
		{
          *j=*j+dim_j;
          *i=(dim_i+1)-*i;
        }  
        esito = 1;
     } // end if is a Moebius chessboard
     else // classical chessboard //
     if (*j>=1 && *j<= dim_j) 
     { 
        esito = 1; /* (i,j) ok */
     }
     else
     { 
        esito = 0; /* (i,j) not ok */
     }
  }
  else
  {
     esito = 0;	/* (i,j) not ok */
  } 
  return esito;
} /* end legal_kmove */

int compute_next_kmoves(int i, int j, int dim_i, int dim_j, int isM, int cboard[][9][9][2])
	{ 
	  int c,ip,jp,k,schemaij[9][2];  
	  // compute all next moves from (i,j)
	  // the following array defines all next relative cohordinates for each next move
	  // (max 8)
	  schemaij[1][0] = -2; schemaij[1][1] = 1;
  	  schemaij[2][0] = -1; schemaij[2][1] = 2;
  	  schemaij[3][0] = 1;  schemaij[3][1] = 2;
  	  schemaij[4][0] = 2;  schemaij[4][1] = 1;
	  schemaij[5][0] = 2;  schemaij[5][1] = -1;
  	  schemaij[6][0] = 1;  schemaij[6][1] = -2;
  	  schemaij[7][0] = -1; schemaij[7][1] = -2;
  	  schemaij[8][0] = -2; schemaij[8][1] = -1;
	  k=0;
	  for(c=1;c<=8;c++)
	  {
	  	// next move //
	  	ip=i+schemaij[c][0];	jp=j+schemaij[c][1];

	    // if it's a valid move, it's been stored 
	  	if(legal_kmove(&ip,&jp, dim_i, dim_j, isM) == 1)
	  	{
	  	  k++;
	  	  cboard[i][j][k][0]=ip; cboard[i][j][k][1]=jp; 
          //printf("%d. (%d, %d) -> (%d, %d)\n",k,i,j,cboard[i][j][k][0],cboard[i][j][k][1]);
	  	}

	  }
      cboard[i][j][0][0]=0;  /* (i,j,0,0) represents the knight number along the tour */ 
	  cboard[i][j][0][1]=k;  /* (i,j,0,1) represents the max number of next moves from (i,j) */ 
	  return 0;
	} // End compute_next_kmoves

int init_chessboard (int dim_r, int dim_c, int isM, int cboard[][9][9][2])
{ 
  int r,c,a;

   cboard[0][0][0][0] = dim_r;
   cboard[0][0][0][1] = dim_c;
   
   for(r=1;r<=dim_r;r++)
   {
      for(c=1;c<=dim_c;c++)
      {
         a=compute_next_kmoves(r,c,dim_r,dim_c,isM, cboard);
      }	
   }
} /* end init_chessboard */

int main(void) 
{ 
	int board[9][9][9][2];
	int pos_i, pos_j =0;
	int isMoe=0;
	int a,x1,y1,dim_x,dim_y,num_solutions=0;
	
    int Kmove(int i, int j, int prog)
    {
       int r1,c1,k1,ip1,jp1,prog1,dim_r, dim_c,a;
       int esito = 0;
       
       dim_r = board[0][0][0][0];
       dim_c = board[0][0][0][1];
        
       board[i][j][0][0] = prog;
       if (prog == dim_r*dim_c)
       {  // success, print the sequence
          esito = 1;
          num_solutions++;

           for(r1=1;r1<=dim_r;r1++)
          {
             for(c1=1;c1<=dim_c;c1++)
             {
                printf("(%d, %d) -> %d\n",r1,c1,board[r1][c1][0][0]);
             }
          }
          scanf("%d",&a);
       }
       else
       {
       	  // for each next move from (i,j)
       	  for(k1=1;k1<=board[i][j][0][1];k1++)
       	  {
       	  	// compute next move
       	  	ip1= board[i][j][k1][0];
       	  	jp1= board[i][j][k1][1];
       	  	
       	  	// if next cell in the chessboard has not yet been visited
       	  	if(board[ip1][jp1][0][0] == 0) 
       	  	{
       	  		prog1=prog+1;
       	        Kmove(ip1, jp1, prog1);
       	  	}
       	  }	  
       	  
       }
       board[i][j][0][0] = 0;
       return esito;
     } // end Kmove
     

isMoe=1;
dim_x = 4;
dim_y = 7;

a=init_chessboard(dim_x,dim_y,isMoe, board);

for(pos_i=1;pos_i<=dim_x;pos_i++)
   {
      for(pos_j=1;pos_j<=dim_y;pos_j++)
      {
         printf("Knight initial position is (%d,%d)\n", pos_i,pos_j);
         a=Kmove(pos_i,pos_j,1);
         printf("Found %d different solutions\n",num_solutions);
         num_solutions=0;
      }	
      
   }

printf("The end !!! ");

scanf("%d",&a);

return 0;
}