jueves, 11 de junio de 2015

( 179 ) Las matemáticas y el ajedrez 2

El problema del caballo
Como ya os advertimos en la anterior entrada de ajedrez, en esta  resolveremos el problema
del caballo, el cual os recordamos:

Problema del caballo. Recorrer con el caballo todas las casillas del tablero de ajedrez pasando por cada una de ellas solo una vez.


Para una primera solución daremos el Método de Munk y Collini (Cossino Collini  fue secretario del célebre filósofo Voltaire):

Primer paso
Segundo paso
Este consiste en dividir el tablero en dos partes: una interior de 16 casillas y una exterior de forma de marco de 48 casillas. En las casillas del cuadrado interior escribimos las letras A, B, C, D (mayúsculas) de modo que cada una de ellas se repita cuatro veces y forme un cuadrado o un rombo por cuyos lados puede moverse el caballo. Escribamos las letras minúsculas a, b, c, d en las casillas del marco exterior de modo que los movimientos del caballo por cada una de ellas formen polígonos cerrados que borden el cuadrado central. El caballo comienza su recorrido en cualquiera de las casillas del marco, pasa por las casillas de las letra elegida, por ejemplo la a, y las recorre en 11 movimientos(la última casilla no debe ser una esquina). Seguidamente, el caballo pasa al cuadro interior, pero no a la misma letra en que empezó, en nuestro caso la A no valdría, sino a cualquier otra letra. Después de recorrer todas las casillas del cuadrado interior marcadas con esa letra, el caballo regresa al marco a una letra en la que aun no ha estado y recorre todas las casillas del marco que contiene a esa letra. Debe proceder de manera análoga con las demás letras.


Una posible forma: a,C,d,A,b,D,c,B

Como se puede apreciar este método no es ni difícil de entender ni de reproducir. Ademas esta idea da pie a este otro Método de Polignac y Roget, mas simple que el anterior:

Recorrido del
caballo por las A
Organización de las letras
Con una cruz trazada por el centro del tablero lo dividimos en cuatro cuadrados iguales. Escribimos en cada uno de ellos las letras A, B, C, D del mismo modo que se hizo en el cuadrado interior del método previo. El caballo comienza su movimiento en cualquier letra, recorre todos los escaque del cuadrado elegido que contiene esa letra y pasa a la misma letra del cuadro siguiente y vuelve a recorrer todas las letras y así sucesivamente. Después de pasar por las 16 casillas de la letra elegida, el caballo cambia de letra y nuevamente se recorren sus 16 casillas correspondientes. Después de repetir cuatro veces esta operación todas las casillas habrán sido visitadas(como en el caso anterior, el recorrido de una letra no debe terminar en una esquina).

Como habéis visto no es difícil recorrer todas las casillas con el caballo con un método pues sin un algoritmo previo seguramente no salga a la primera, y si no intentarlo. Aparte de estos dos métodos hay muchos mas, como por ejemplo el de Euler-Valdermonde, el de Warnsdorff... 
Estos son igualmente validos aunque su explicación es un poco mas liosa. Para el lector que quiera experimentar por si mismo, o practicar estos métodos, os dejamos un enlace con el que jugando se adquiera mucha fluidez con el movimiento del caballo.


A modo informativo exponemos brevemente el otro problema mas famoso del ajedrez, el problema de las ocho damas (además aquí podéis ver un poco de la idea de la resolución). Este problema esta expuesto en casi todos los libros de matemática recreativa. Dicta así:

Problema de las 8 Damas:¿De cuantos modos diferentes se pueden colocar 8 damas en el tablero de modo que no se amenacen unas a otras?

Es claro que para que dos damas no se amenacen entre si no deben estar en una misma vertical,
Una posible solución
horizontal o diagonal.
Desde luego, es una terminología aceptada que dos piezas con el mismo nombre se amenazan si las piezas están conectadas entre si por el movimiento de ellas.

Si bien el problema del caballo atrajo la atención de Leonhard Euler, a mediados del siglo XIX el problema de las ocho damas fue objeto de estudio de Carl Gauss.

Evidentemente en el tablero es imposible de colocar mas de 8 damas sin que se amenacen( si se colocan mas de 8 damas, al menos en una columna o en una fila habrá más de una).

Hallar una u otra solución no es complicado. Mucho mas difícil es calcular el número total de soluciones que es lo que pide propiamente el problema. El problema fue planteado en 1848 por el ajedrecista Max Bezzel. Dos años después el doctor Franz Nauck hallo 60 soluciones y las publico en el periódico Illustrierte Zeitung. Sólo después el problema llamo la atención a Gauss, quien hallo 72 soluciones. El conjunto completo de soluciones, formado por 92 disposiciones distintas de las 8 damas, de las cuales solo 12 son esencialmente distintas, fue hallado

Las 12 soluciones esenciales


por Nauck y publicado por él en el mismo periódico el 21 de septiembre de 1850. Esta es la cronología de los hechos según el investigador matemático Wilhelm Ahrens.
La demostración rigurosa de que estas 92 disposiciones son las únicas posibles fue obtenida en 1874 por el matemático ingles Jamaes Glaisher (utilizando la teoría de los determinantes).Se conocen muchos métodos para la búsqueda eficaz  de las disposiciones de las damas (De la Nog, Glaisher, Laquière y otros).

Por último, os dejamos, para terminar la entrada, un par de enlaces que se salen un poco del tema:

El primero, un enlace a un blog-revista bastante interesante (de hecho ya hemos citado una entrada de ese blog cuando nosotros hablamos del Ministerio del tiempo) porque tiene bastantes artículos que mencionan el ajedrez, y desde diferentes puntos de vista:

 http://www.jotdown.es/category/ciencias/chess/

Y en segundo lugar un enlace que habla de otro juego distinto: el Hex. Que no es que tenga mucho que ver con el ajedrez (aparte de que en ingles el nombre de los dos tiene una sola silaba con una e) pero que, como se ve en el enlace que ponemos, es el juego matemático perfecto en opinión de alguien que sabía matemáticas (de alguien que tenía "Una mente maravillosa" como ya comentamos en este blog). Alguien que ha sido noticia recientemente, primero por motivos alegres, ya que  le han concedido (compartido con Louis Nirenberg) el muy importante Premio Abel, y después por motivos mucho más tristes, ya que ha fallecido en un accidente. Vaya, con la excusa de este juego, nuestro recuerdo y nuestro homenaje para John Forbes Nash.



Información sacada de: Matematica en el tablero de ajedrez, de Yevgueni Yàkovlievich Guik