/*
	Novacreations.net
	http://www.novacreations.net
	Cris Vil
	Febrero 2006


*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define N 8
#define n (N+1)

void saltoCaballo(int i, int x,int y, int* exito);
void escribeTablero();
int tablero[n][n];
int d[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

int main()
{
    int x,y;
    int solucion;
    int i, j;
  do {
      printf("Coordenadas iniciales del caballo: ");
      scanf("%d %d", &x, &y);
      }while((x<1) || (x>N) || (y<1) || (y>N));
/*  Valores iniciales del tablero */
    for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
        tablero[i][j]=0;
    tablero[x][y]=1;

/* Llamada con coordenadas iniciales y primer salto */

   solucion=0;
   saltoCaballo(2, x, y, &solucion);
   if(solucion)
   {
       puts("\n\tEL problema tiene solucion:\n");
       escribeTablero();
   }
   else
       puts("No se ha encontrado solucion al problema!!");

   getch();
   return 0;

  //system("PAUSE");
  //return 0;
}
void saltoCaballo(int i, int x, int y, int* exito)
{
     int nx, ny;
     int k;
     *exito=0;
     k=0; //Inicializa el conjunto posible de movimientos
     do{
          k++;
          nx=x+d[k-1][0];
          ny=y+d[k-1][1];
                         //Determina si nuevas coordenadas son aceptables
          if((nx >=1) && (nx <=N) && (ny>=1) && (ny<=N) && (tablero[nx][ny]==0))
          {
                 tablero[nx][ny]=i; //anota movimiento
                 if(i < N*N)
                 {
                      saltoCaballo(i+1, nx, ny, exito);
                      //Se analiza si se ha completado la solución
                      if(!(*exito))
                      {
                                   tablero[nx][ny]=0; //No se alcanzó la solución, se borra la anotación
                      }
          }
          else
               *exito=1; //caballo ha cubierto el tablero

          }
     }while((k<8) && !(*exito));
}
void escribeTablero()
{
     int i,j;
     for(i=1; i<=N; i++)
     {
              for(j=1; j<=N;j++)
                       printf("%d %c", tablero[i][j],(j < N ? ' ': '\n'));
     }

}