El recorrido mágico del caballo

En el ajedrez el caballo se mueve en forma de L. Supongamos que tenemos un tablero ${n\times{n}}$ vacío y queremos hacer que un caballo pase por cada posición del tablero. Si el caballo pasara por cada posición una sola vez, decimos que hicimos un recorrido de caballo (knight’s tour). Este recorrido es una forma particular de lo que se conoce en teoría de gráficas como camino de Hamilton (una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez).

Imagen (recarga la página)

Bien, pidamos más que eso, pidamos que el recorrido de caballo sea mágico. Asignémosle al recorrido una sucesión de números ordenados que corresponda a cada posición del caballo, es decir, asignémosle a la posición inicial el número 1, a la siguiente el número 2 y así sucesivamente. Al finalizar el recorrido obtenemos una cuadrícula numerada; bien, pues diremos que esa cuadrícula es mágica si la suma de cada elemento de las columnas, filas y ambas diagonales es constante, por ejemplo:

Imagen (recarga la página)

Desde hace tiempo se sabe que no existen recorridos mágicos de caballo para cuadrículas ${n\times{n}}$ con n impar y hace poco, después de 61.4 días máquina de cálculos, se ha descartado la existencia de recorridos mágicos de caballo mediante la recolección de todos los posibles recorridos con ayuda del ordenador [2].

Imagen (recarga la página)

Sin embargo es posible formar recorridos semi-mágicos de caballo, esto es, que la cuadrícula formada cumpla que la suma de cada elemento de columnas y filas sea constante.El siguiente cuadro semi-mágico al parecer fue ingeniado por William Beverley, aunque constantemente se le atribuya a Leonhard Euler [1]. Cada columna y fila suman 260 y la mitad de cada columna y fila suman 160 (es decir, podemos obtener pequeños cuadros semi-mágicos), además de cumplir el ser recorrido de caballo.

Imagen (recarga la página)

Existen otro tipo de recorridos sin embargo, que tienen lo necesario para ser recorridos mágicos, como el recorrido del Rey, por ejemplo el siguiente de ${8\times{8}}$:

Imagen (recarga la página)

Existen muchos recorridos de Rey posibles y éstos se pueden clasificar respecto a simetría bi-axial [4] como vemos por ejemplo en el diagrama del siguiente recorrido ${16\times{16}}$:

Imagen (recarga la página)

Referencias y más información:

No comments:

Post a Comment