Pequeña Historia del Problema
El "recorrido del caballo" es un problema clásico de la teoría de grafos, que se planteó por primera vez hace más de 1.000 años y sobre el que reflexionaron matemáticos legendarios como Leonhard Euler antes de ser resuelto finalmente en 1823.
Utilizaremos el problema del recorrido del caballo para ilustrar un segundo algoritmo de grafos común llamado búsqueda de profundidad. El problema del recorrido del caballo se juega en un tablero de ajedrez con una sola pieza, el caballo. El objetivo del rompecabezas es encontrar una secuencia de movimientos que permita al caballo visitar cada casilla del tablero una vez, así:
1Aparicion del problema
Los primeros estudios del problema del caballo se encuentran en un manuscrito del siglo IX, que recoge soluciones de dos grandes ajedrecistas árabes. Hacia mediados del siglo XVIII entre los círculos matemáticos europeos, este enigma tuvo un gran auge, principalmente por el enorme número de soluciones posibles.
2El gran aporte de Euler
El trabajo más importante en relación a este problema, se atribuye
al genial Leonhard Euler, que destacó por sus ingeniosas y
fantásticas soluciones. Una de las soluciones que dio este genio
matemático asombró por su belleza.
Euler construyó un cuadrado
mágico donde las filas y las columnas sumaban 260. El caballo se
desplaza desde la casilla 1 hasta la 64 en orden numérico. Puedes
comprobarlo en la siguiente imagen. Si ya de por sí, el desarrollo
de la marcha del caballo por todo el tablero es muy difícil de
conseguir, añádele además conseguir un cuadrado mágico.
Impresionante!
Video Explicativo
Cómo resolver el problema del caballo
En Resumidas cuentas, el problema consiste en recorrer las 64 casillas del tablero con un caballo, en 64 movimientos y sin pasar dos veces por la misma casilla
- Empezar y terminar en la misma casilla (circuito cerrado). Más complicado.
- Empezar en una casilla y terminar en otra (circuito abierto). Más “sencillo”
Encontrar una solución simplemente moviendo el caballo "a través de prueba y error" es imposible. Son pocos los que han ideado un método que facilite el proceso.
Siempre ayuda dividir un problema en pequeños pedazos. Una buena estrategia inicial sería dividir el tablero en pequeñas porciones. Debes tener claro qué rutas son posibles y vincularlas hasta completar el tablero.
Aunque Euler propuso principalmente caminos cerrados, que son más elegantes y además permiten resolver el problema desde cualquier cuadro inicial, ha proporcionado algunas pautas para resolver este problema en general con el fin de obtener el cuadrado mágico.
Con este desconcertante problema, Euler “dividió” el tablero en cuatro partes, en cuadrados de 16 celdas (4 × 4) y pudo resolver el problema con su búsqueda de patrones, simetría y su enorme genio.
Aplicando matematicas discretas, resolveremos el problema utilizando dos pasos principales:
1. Representar los movimientos legales de un caballo en un tablero de ajedrez como un grafo.
2. Utilizar un algoritmo de grafos para encontrar un camino en el que cada vértice del grafo sea visitado exactamente una vez.
¿Cuantas soluciones hay?
Se han encontrado muchas soluciones para este problema y de hecho no se sabe con seguridad de cuántas maneras diferentes es posible solucionarlo.
Pero gracias a la ayuda de los ordenadores, en 1995 Löbbing y Wegener pusieron a trabajar a 20 ordenadores para calcular posibles variantes para el paseo del caballo sin repetir ninguna casilla y llegaron a la conclusion que el problema del caballo puede tener más de 33 billones de soluciones
