Código [Seleccionar]
/* 4_24
(Circuito del caballo) Uno de los problemas mas interesantes para los aficionados al ajedrez es el circuito
del caballo, propuesto inicialmente por el matematico Euler. La pregunta es la siguiente: ¿puede el caballo del aje-
drez moverse por un tablero vacio y tocar los 64 cuadros una sola vez? Estudiaremos profundamente este intere-
sante problema.
El caballo hace movimientos en forma de L (dos casillas en una direccion y una en sentido perpendicu-
lar). Por lo tanto, desde una casilla del centro de un tablero vacio, el caballo puede hacer ocho movimientos dis-
tintos (0 a 7), como se muestra en la figura 4.25.
a) Dibuje en una hoja de papel un tablero de 8 por 8 e intente el circuito del caballo a mano. Ponga un
1 en el primer cuadro al que se mueva, un 2 en el segundo, un 3 en el tercero, etc. Antes de iniciar el
circuito, estime hasta donde piensa que llegara, recordando que un circuito completo consiste de 64
movimientos. ¿Que tan lejos llego? ¿Cerca de su estimacion?
b) Ahorra desarrollemos un programa que mueva el caballo por el tablero. El tablero se representa por
medio de un arreglo board, de doble subindice de 8 por 8. Cada uno de los cuadros se inicializa a
cero. Describimos cada uno de los ocho movimientos en terminos de sus componentes horizontales y
verticales. Por ejemplo, un movimiento del tipo 0, como el indicado en la figura 4.25, consiste del
movimiento horizontal de dos cuadros a la derecha y de un cuadro vertical, hacia arriba. El movimien-
to 2 consiste del movimiento horizontal de un cuadro a la izquierda y de dos cuadro verticales, hacia
arriba. Los movimientos horizontales a la izquierda y los moviemitnos verticales hacia arriba se indi-
can mediante numeros negativos. Los ocho movimientos se pueden describir por medio de dos arre-
glos de un solo subindice, horizontal y vertical:
horizontal[0] = 2
horizontal[1] = 1
horizontal[2] = -1
horizontal[3] = -2
horizontal[4] = -2
horizontal[5] = -1
horizontal[6] = 1
horizontal[7] = 2
vertical[0] = -1
vertical[1] = -2
vertical[2] = -2
vertical[3] = -1
vertical[4] = 1
vertical[5] = 2
vertical[6] = 2
vertical[7] = 1
Haga que las variables currentRow y currentColumn indiquen la fila y la columna de la posi-
cion actual del caballo, respectivamente. Para hacer un movimiento del tipo numMov
(numero de movimiento), donde numMov esta entre 0 y 7, el programa se vale de las instruc-
ciones
currentRow += vertical[numMov];
currentColumn += horizontal[numMov];
Lleve un contador que cuente del 1 al 64. Registre la ultima cuenta en cada cuadro al que mueva el
caballo y, claro esta, pruebe cada movimiento potencial para asegurarse de que el caballo no cae fuera
del tablero. Ahora escriba un programa para mover el caballo por todo el tablero. Ejecute dicho progra-
ma. ¿Cuantos movimientos hizo el caballo?
c) Tras su intento por escribir y ejecutar el programa del circuito del caballo, probablemente habra de-
sarrollado algunas habilidades valiosas. Nos valdremos de ellas para desarrollar una heuristica (o
estrategia) de movimientos del caballo. Esta no garantiza el exito. Tal vez haya observado que los
cuadros exteriores son mas problematicos que los que estan mas cerca del centro del tablero. De
hecho, los cuadros mas dificiles o inaccesibles son los que estan en las esquinas.
La intuicion podria sugerir que lo que se debe hacer es mover primero el caballo a los pun-
tos mas complicados y dejar abiertos los de mas facil acceso, de modo que cuando se congestione el
tablero hacia el final del circuito haya mayor posibilidad de exito.
Podemos desarrollar una heuristica de accesibilidad clasificando cada uno de los cuadros
de acuerdo con su accesibilidad y luego moviendo el caballo al cuadro (dentro de sus movimien-
tos en forma de L, claro esta) que sea mas inaccesible. Se etiqueta un arreglo de doble subindice
accessibility con numeros que indiquen la cantidad de cuadro accesibles a partir de cada
cuadro. En un tablero en blanco, cada cuadro central tiene una calificacion de 8 y cada cuadro de
esquina una calificacion de 2; los demas cuadros tienen de 3, 4 o 6, segun la siguiente
tabla:
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
Ahora escriba una version del programa del circuito del caballo aplicando la heuristica de accesi-
bilidad. En cualquier momento el caballo debe moverse al cuadro con la menor calificacion de
acceso. En caso de empate, se podra mover a cualquiera de los cuadros empatados. Por lo tanto, el
circuito puede comenzar en cualquiera de las 4 esquinas. (Nota: a medida que el caballo se
mueva por el tablero, el programa debera reducir las calificaciones de accesibilidad, dado que mas y
mas cuadro quedan ocupados. De esta manera, en cualquier momento dado durante el circuito, las
cifras de accesibilidad a los cadros permaneceran iguales a la cantidad de cuadros desde donde se
puede llegar a ellos.) Ejecute esta version del programa. ¿Hizo el circuito completo? Modifiquelo
ahora para que ejecute 64 circuitos, comenzando desde cada cuadro del tablero. ¿Cuantos circuitos
completos logro?
d) Escriba una version del programa del circuito del caballo que, al tener un empate entre dos o mas
cuadros, decida el cuadro a seleccionar analizando hacia adelante los cuadros a los que se podra llegar
desde los cuadros "empatados". El programa debera moverse al cuadro en el que el siguiente movi-
miento llevara al cuadro con la menor calificacion de accesibilidad.
*/Yo tengo hasta el C, pero en el D ya me hice bolas, alguien me ayuda