UNIVERSIDAD DE COSTA RICA                CI-0202 Principios de Informática
ESCUELA DE CIENCIAS DE LA
COMPUTACION E INFORMATICA                       I semestre del 2000
                                 Tarea Nº4
                    EL RECORRIDO DEL CABALLO DE AJEDREZ

              (Para entregar el lunes 15 ó martes 16 de mayo)
           (En esta tarea no se utilizarán vectores y matrices)

Este problema fue analizado por primera vez por el matemático Euler. 
Consiste en simular el recorrido del caballo en el tablero de ajedrez. 
Considerando el tablero vacío, se inicia el caballo en cualquier posición y 
se marca con un número, luego se dirige a otra posición y se coloca otro 
número y así sucesivamente hasta completar los 64 cuadros del ajedrez. 
Trátelo de hacer manualmente, colocando granitos de arroz por donde va 
colocando el caballo y verá que para los humanos no es tan fácil resolver 
el problema. Sin embargo, para el computador puede ser muy sencillo.

Para ello utilizaremos un algoritmo heurístico, i.e. un procedimiento que 
nos parece el más adecuado para alcanzar el objetivo de todas las 
posiciones del tablero. Hacemos la siguiente reflexión: dada una posición 
dada del caballo en el tablero, analizar todas las casillas posibles para 
moverse desde esa posición; luego ver para cada posición, cuantas movidas 
posibles tiene el caballo; escoger la posición cuya movida tenga menos 
posibilidades.

La lógica de este algoritmo heurístico se resume en la siguiente: ir a la 
posición más dificil, o sea escoger la posición con menos posibilidades y 
dejar las posiciones más fáciles para el final. Recuerde que el número 
máximo de posibilidades de mover un caballo del ajedrez es de ocho.

Al final el tablero deberá aparecer lleno con una secuencia de números de 1 
a 64. Imprima la matriz del tablero con esa secuencia. Ello nos mostrará la 
posición inicial 1 y las diferentes movidas de 1 a 64.

Utilice un procedimiento que calcule las posibles movidas, un procedimiento 
que calcule el vector de movidas posibles en cada movida, y una función que 
escoja la mejor movida.

Recuerde que si el caballo se encuentra en la posición i,j las posibles 
ocho movidas son las siguientes:

                   i-2,j-1        i-2,j+1
              i-1,j-2                 i-1,j+2
                            i,j
              i+1,j-2                 i+1,j+2
                   i+2,j-1        i+2,j+1

Cada una de esas posiciones tiene a su vez hasta ocho posibles movidas, 
según se encuentren estas movidas dentro del tablero, fuera del tablero o 
ya ocupada anteriormente por el caballo.

La salida deberá ser similar a la siguiente:

Escriba la posición inicial del caballo (i, j) 0, 0 para parar: 1, 1

     Las movidas son:

          1  4 23 20 57  6 51 44
         22 19  2  5 50 43 58  7
          3 24 21 56 27 60 45 52 ...