El juego del Aparcamiento Guasón.

Antonio Javier Serrano Mora.

Invierno de 2007.

1  Introducción.

Hace pocos días, me encontré una página web1 en la que se ofrecen multitud de juegos, programados en Flash, y clasificados por categorías. En la categoría llamada Estrategia elegí el juego llamado El Aparcamiento.
Figure 1: Tablero de juego nº 3 en su posición inicial
El tablero de juego consiste en seis plazas individuales de aparcamiento, representadas cada una de ellas mediante un círculo de un color diferente. Estas plazas de aparcamiento están interconectadas mediante carreteras, por las que sólo puede circular un coche cada vez. El número de carreteras que llegan o salen de cada plaza no es, en principio, el mismo en todas. Un ejemplo de tablero es el que aparece en la figura 1.
El juego está organizado en distintos tableros numerados, o pantallas, y ordenados, se supone, en orden de dificultad creciente. Un tablero sólo se diferencia de los demás en la red de carreteras que unen las seis plazas de aparcamiento.
Las fichas de este juego de tablero son cinco coches. Cada coche es de un color distinto, de manera que los colores de las plazas y los colores de los coches son los mismos, salvo el blanco, ya que hay una plaza de este color pero no un coche pintado de blanco. Al inicio de la partida, los coches están distribuidos de cualquier manera sobre el tablero, de forma que, en cada plaza de aparcamiento, hay un coche, salvo en una de ellas, que está vacía.
Un movimiento consiste en mover un coche desde la plaza donde esté colocado a otra plaza libre que esté conectada mediante un carretera con la primera2. El objetivo del juego es colocar cada coche en una plaza de aparcamiento de forma que, en todos los casos, coincidan los colores de la plaza y del coche. Una de las plazas, la de color blanco, ha de quedar vacía.
Este artículo centrará su atención en el tablero número 3 (figura 1), ya que, aunque de apariencia sencilla, presenta algunas cualidades dignas de ser estudiadas.

2  Análisis del juego del Aparcamiento.

Figure 2: Esquema del Tablero del Aparcamiento nº 3.
En primer lugar, reduciremos el tablero de juego número 3 a un esquema, en el que representamos cada plaza de aparcamiento mediante una circunferencia, cada carretera mediante un línea recta y cada color mediante un número romano.
Así, hemos identificado (figura 2) el color azul con el I, el amarillo con el II, el fucsia con el III, el verde con el IV, el blanco con el V y, finalmente, el rojo con el VI. La asignación de cada número a cada color no es arbitraria, como se verá, aunque se puede hacer también de otras formas.
Además, cada coche será designado también mediante un número según su color y según la misma convención empleada para las plazas, pero esta vez se usarán los números arábigos 1, 2, 3, 4 y 6 (recuérdese que no hay coche blanco, así que el número 5, en principio, no se usará).
Así las cosas, podemos escribir en cada uno de los círculos una expresión del tipo Z-x, donde Z representa el color de la plaza de aparcamiento correspondiente, es decir Z Î {I,II,III,IV,V,VI}, y x representa el color del coche que está aparcado en esta plaza, por tanto, x Î {1,2,3,4,6}. La posición inicial de la figura 1 se representa, entonces, mediante el esquema de la figura .
Figure 3: Posición inicial del juego.
El siguiente paso en nuestro análisis de este juego va a ser convertir cada círculo del esquema del tablero en un cuadrado y, después, colocaremos dos cuadrados de forma que sean adyacentes por uno de sus lados si los círculos correspondientes están conectados mediante una línea. El resultado de estas transformaciones se puede ver en la figura .
En efecto, el tablero presentado en la figura corresponde exactamente al tablero de las figuras 1 y 2. La plaza II, por ejemplo, está conectada con las plazas I, III y V; en la figura se observa que la casilla II es adyacente por un lado a las casillas I, III y V. La plaza VI en la figura 2 está conectada con las plazas III y V; la casilla VI de la figura es adyacente a las casillas III y V. Lo mismo podríamos decir para el resto de plazas de aparcamiento de la figura 2 y de casillas de la figura .
Figure 4: Forma del tablero tras ciertas transformaciones.
El tablero resultante de las transformaciones descritas anteriormente es, pues, completamente equivalente al tablero del juego. En realidad, se trata de una versión reducida del llamado Juego de los 15, como lo llama Miguel de Guzmán en su maravilloso Aventuras Matemáticas3 o, también, Juego del Guasón, como lo llama Édouard Lucas en sus Récréations Mathématiques4. Este juego, de origen estadounidense, tiene una íntima relación con el grupo de las permutaciones de 16 elementos. En nuestro caso, veremos la relación existente con las permutaciones de 6 elementos. De Guzmán atribuye el invento a Sam Loyd padre y lo data en 1878; Édouard Lucas, que da la misma fecha, atribuye el invento a un muchacho sordomudo que quiso ordenar, dentro de una caja y sin sacarlos, unos números que se encontraban descolocados; cita, como fuente a Sylvester, profesor de la Universidad J. Hopkins de Baltimore. Sea como sea, el juego se extendió rápidamente desde los Estados Unidos hasta Europa e hizo, por lo visto, furor. En el libro citado dice De Guzmán: <<Los niños en las escuelas a hurtadillas, las secretarias ante sus máquinas paradas y los ejecutivos a puerta cerrada, todos lo jugaban con fruición.>>
Figure 5: A la izquierda el Guasón, de la obra de Lucas. A la derecha, el Juego de los 14-15, tomada del libro Cyclopedia of Puzzles de Sam Loyd, 1914.
Para colocar los coches sobre nuestro nuevo tablero, confeccionaremos fichas cuadradas, del mismo tamaño que las casillas, y rotuladas con los números 1, 2, 3, 4 y 6. Colocada cada ficha en su casilla correspondiente, obtendremos la posición inicial del juego, como se muestra en la figura , donde hemos suprimido el rótulo de la casilla V para dar más claridad al esquema.
Figure 6: Posición inicial del Guasón chico.
Ahora, un movimiento consistirá en desplazar una ficha a una casilla libre adyacente a la que ocupa actualmente. La similitud de este juego con la del Guasón es tan evidente ahora, que lo llamaremos el Guasón chico.
El juego quedará completado cuando se llegue, tras sucesivos movimientos, a la posición final mostrada en la figura , es decir, cuando el número de cada ficha coincida con el número de su casilla correspondiente (salvo la casilla V, que ha de quedar vacía). Dicho de otra manera, si consideramos que la casilla vacía contiene una ficha invisible con el número 5, entonces el juego terminará cuando se coloquen en orden numérico todas las fichas, leídas de izquierda a derecha y de arriba abajo.
Figure 7: Posición final del Guasón chico.
Cualquier posición del tablero de juego puede ser representada mediante un número de seis cifras, tomadas de las fichas en el orden de las casillas y añadiendo el 5 en el lugar de la casilla vacía. Así, la posición inicial del juego (figura 6), puede ser representada mediante el número 236154; la posición final (figura 7) se representa mediante el número 123456. Un movimiento consiste entonces en intercambiar la cifra 5 con otra, estando sujeto este intercambio a las vecindades de las casillas.
El conjunto de todos los números formados por las seis primeras cifras se llama conjunto de las permutaciones ordinarias de seis elementos. Este conjunto tiene 1×2×3×4×5×6=6!=720 elementos distintos, lo que significa que el Guasón chico, y por tanto el juego del Aparcamiento, podría tener hasta 720 posiciones distintas. En general, el conjunto de todas las ordenaciones posibles de n elementos se llama conjunto de permutaciones ordinarias de n elementos y existen n! de ellas.
Diremos que una de las cifras de una permutación presenta m inversiones si a su derecha encontramos m cifras menores. Por ejemplo, en la permutación que representa la posición inicial, 236154, la primera cifra, 2, presenta una única inversión, dado que el 1 se encuentra a su derecha; la segunda cifra, 3, presenta también una única inversión debida también al 1; la siguiente cifra, 6, presenta tres inversiones, pues 1, 5, 4 son cifras menores y colocadas a su derecha; la cifra 1 no presenta ninguna inversión; finalmente, la cifra 5 presenta 1 inversión. En total, hay 6 inversiones en esta permutación; diremos, entonces, que esta permutación es par. En general, se dirá que una permutación es par si presenta, en total, un número par de inversiones; diremos que una permutación es impar si presenta, en total, un número impar de inversiones.
De las 720 permutaciones de seis elementos, la mitad son pares y la mitad son impares y, en general, podemos afirmar que en el conjunto de las permutaciones ordinarias de n elementos, existen [n!/2] permutaciones pares y el mismo número de permutaciones impares.
Ya hemos dicho más arriba que un movimiento en el juego del Aparcamiento equivale a mover una ficha en el Guasón chico hacia la casilla vacía y que esto, a su vez, es equivalente a intercambiar el número 5 con cualquier otra cifra en la permutación de seis elementos, siempre que lo permitan las reglas del juego. Estudiemos ahora cómo afecta cada movimiento a la paridad de una permutación. Para ello, consideraremos permutaciones de n elementos, en lugar de 6 elementos, para demostrar, de paso, que todas las afirmaciones siguientes son independientes del número de casillas del Guasón.
Supongamos que una posición dada del juego está representada mediante el número de n cifras x=a1a2a3¼akak+1¼an-1an donde ai Î {1,2,3,¼,n-1,n}. Supongamos ahora que se hace un movimiento consistente en intercambiar dos dígitos consecutivos, ak y ak+1, con lo que la nueva disposición del tablero estará representada por el número y=a1a2a3¼ak+1ak¼an-1an. Sea I(x) el número de inversiones de la posición x y calculemos I(y).
En primer lugar, se observará que el número de inversiones de ak y de ak+1 en relación a las otras cifras del número y no cambia, ya que las cifras que en x estaban a la derecha de estas dos siguen estándolo en y y las que estaban a su izquierda también. De manera que, si se produce alguna variación en el número de inversiones, ésta está referida sólo a los valores relativos de ak y de ak+1.
Si ak < ak+1, al invertir el orden de estas cifras, el número de inversiones de ak no cambia, pues hemos quitado de su derecha una cifra mayor que no producía, por tanto, inversión. Pero ahora, ak+1 tiene a su derecha una cifra menor que antes no tenía, ak, por lo que su número de inversiones, aumenta una unidad. Por tanto, se tiene que, en este caso, I(y)=I(x)+1.
Si ak > ak+1, al invertir el orden de estas cifras, estamos quitando de la derecha de ak un número menor, ak+1, y por tanto, su número de inversiones disminuye una unidad. La cifra ak+1, en cambio, tiene tras este movimiento, una cifra a su derecha que es mayor, lo que no produce ninguna nueva inversión. Por tanto, en este caso, I(y)=I(x)-1.
Así que, como se ha visto, al intercambiar dos cifras consecutivas de una permutación x para obtener la permutación y, se tiene que I(y)=I(x)±1, es decir, las paridades de I(x) y de I(y) son distintas, lo que nos permite afirmar que: <<El intercambio de dos cifras consecutivas en una permutación cambia la paridad de la permutación.>>
Ahora, supongamos que se intercambian las posiciones de dos cifras no consecutivas, es decir, que de la posición x=a1a2¼ak¼ak+h¼an-1an pasamos a la posición y=a1a2¼ak+h¼ak¼an-1an. Este intercambio puede dividirse en dos etapas. La primera consistirá en mover la cifra ak+h hasta colocarla justo delante de la cifra ak; ello exige h+1 intercambios de dos cifras consecutivas. La segunda etapa consiste en mover la cifra ak hasta el lugar que ocupaba ak+h, lo que exige otros h intercambios de dos cifras consecutivas. En total, intercambiar las posiciones de estas cifras necesita de 2h+1 intercambios de cifras consecutivas, es decir, un número impar, por lo que podemos afirmar que: <<El intercambio de dos cifras de una permutación cambia la paridad de la permutación.>>
Volvamos ahora a las posiciones inicial y final del Guasón chico (figuras 6 y 7). En ambas, la casilla vacía está en el mismo lugar; es decir, la cifra 5 de las permutaciones inicial y final ocupa la misma posición. Si nos imaginamos el tablero coloreado como un tablero de ajedrez, se verá que la casilla vacía, sucesivamente, pasa de blanca a negra y de negra a blanca, ya que los movimientos en diagonal no se pueden hacer. Por tanto, para que la casilla vacía, al principio y al final del juego, esté en la misma posición, el número total de movimientos ha de ser par. Así que se puede afirmar que: <<El juego propuesto sólo tendrá solución realizando un número par de movimientos.>>
Además, podemos afirmar que: <<Si la permutación inicial y la final tienen del mismo color la casilla vacía, entonces han de tener la misma paridad; y si tienen de distinto color la casilla vacía, entonces tienen distinta paridad>>, ya que, en el primer caso, para ir de la una a la otra, hay que realizar un número par de movimientos y, en el segundo, un número impar.
De forma que si la posición inicial es par, mediante un número par de movimientos podremos pasar a cualquier posición par y, mediante un número impar de movimientos, podremos pasar a cualquier posición impar. Y si la posición inicial es impar, entonces, mediante un número par de movimientos podremos pasar a cualquier posición impar y, mediante un número impar de movimientos podremos pasar a cualquier posición par.
Como ya se vio más arriba, en el juego propuesto, las posiciones inicial y final son ambas pares y tienen la casilla vacía en el mismo lugar, por tanto el juego tiene solución. En realidad, que las posiciones inicial y final sean de la misma paridad es tan solo una condición necesaria, pero en un tablero de dimensión 2×3, como el del Guasón chico, esta condición es también suficiente, como se verá más adelante.
Puede el lector entretenerse, antes de leer el siguiente párrafo, en averiguar si las posiciones iniciales x1=341652 y x2=465312 pueden ser transformadas o no en la posición final y=123456.
Para la posición x1, se observará que el 5 está colocado en penúltimo lugar, como en la posición final. Por tanto, si el juego tiene solución, requerirá de un número par de movimientos. Contemos ahora el número de inversiones de x1 y veremos que es 7, es decir, impar. Entonces, este juego es imposible.
Para la posición x2, se observará que el 5 ocupa la tercera posición. Para llegar a la quinta posición necesita un número par de movimientos, sea cual sea el camino que recorra. Para comprobar esta afirmación, supongamos que hay un camino, con un número impar de movimientos, que conecta las casillas III y V. Entonces, con dos movimientos más cerramos el camino llegando hasta III, pero con un número impar de movimientos, lo que es imposible. Por tanto, si el juego tiene solución, ésta consiste en realizar un número par de movimientos. Contando las inversiones de x2, nos daremos cuenta de que es par, de forma que este juego sí tiene solución.

3  Solución del juego del Aparcamiento.

Cuando las posiciones inicial y final, con el hueco en la casilla 5, cumplen la condición de paridad exigida más arriba, la solución siempre es posible y encontrarla no entraña ninguna dificultad.
Los primeros movimientos, por ejemplo, pueden ser destinados a colocar en su lugar correspondiente, en la primera columna del Guasón chico, las fichas 1 y 4. Consideraremos, por ejemplo, las casillas del Guasón chico en el mismo orden en el que están numeradas: I-II-III-IV-V-VI.
Figure 8: Solución al problema propuesto.
Se procede, en primer lugar, a colocar, mediante movimientos circulares de las fichas a lo largo de todas las casillas, el 4 en la casilla I, procurando que la ficha 1 no quede en la casilla IV. Entonces, mediante movimientos circulares con las fichas de las casillas II, III, V y VI se coloca el 1 en la casilla II. Finalmente, mediante movimientos circulares de las fichas a lo largo de todas las casillas del tablero, se colocan el 1 y el 4 en su lugar correspondiente, es decir, en las casillas I y IV, respectivamente.
Hecho esto, quedarán las fichas 2, 3 y 6 en las otras cuatro casillas y, mediante movimientos circulares, dentro de estas cuatro casillas, cada cifra se colocará en su lugar y el hueco irá a parar a la casilla V. Juego resuelto. En la figura 8, se muestra la secuencia de 12 movimientos para la posición inicial dada al principio de este artículo. Para solucionar el problema del Aparcamiento, por tanto, no hay más anotar el orden y las fichas movidas en el Guasón chico, traducir estos números a colores e ir pulsando, sucesivamente, con el botón del ratón, sobre el coche del color indicado.

4  El problema del Caballo Guasón.

Miguel de Guzmán, en el libro citado, propone, tras una serie de variaciones sobre el juego de los 15, un problema muy intesante del que afirma: <<El juego parece mucho más interesante y variado que los anteriores, y también más difícil. Yo no lo he visto propuesto antes en ningún sitio>>. De Guzmán confiesa también haber estudiado sólo los casos más sencillos y deja planteadas algunas preguntas sobre el mismo. En ésta y en muchas de sus otras obras de divulgación, Miguel de Guzmán se muestra como un verdadero maestro en el arte de insinuar, de invitar, siendo muchas veces más sugestivo en aquello que calla, que sólo pregunta, que en aquello que desarrolla en detalle.
En el Guasón ordinario, un número puede moverse a una casilla adyacente por un lado si ésta está vacía. Podríamos decir que la casilla vacía se mueve como una torre del ajedrez, pero sólo una casilla cada vez. Supongamos que se cambia esta regla. Entonces, el problema, al que llamaremos Caballo Guasón, es el siguiente:
Dado un tablero del juego del Guasón de cualquier dimensión, la casilla vacía se mueve como un caballo del ajedrez, es decir, dos casillas en dirección norte, sur, este u oeste, y una en dirección perpendicular, pero siempre dentro del tablero. ¿Cuáles son ahora las condiciones que han de cumplir las posiciones inicial y final para que el juego tenga solución? ¿Qué estrategia habría que seguir?
Hagamos primero un análisis de paridad, similar al anterior. Un movimiento de caballo puede descomponerse en un número impar de movimientos consecutivos del Guasón ordinario. En efecto, supongamos que queremos intercambiar la ficha x, situada en la casilla X, con el hueco, situado en la casilla Y, y supongamos, además, que el tablero de juego está coloreado como uno de ajedrez. El movimiento podemos dividirlo en dos fases: 1ª Llevar la ficha x a la casilla Y; 2ª Llevar el hueco a la casilla X. La casilla X es de un color distinto al de la casilla vacía Y, ya que las separa un salto de caballo, de manera que para llevar x al hueco se necesita un número impar, 2h+1, de movimientos. Tras colocar la ficha x en la casilla Y, el hueco queda en una casilla adyacente a ésta y, por tanto, de color diferente. Es decir, tras colocar la ficha x, el hueco queda en una casilla del mismo color que la casilla X y, por tanto, es necesario un número par, 2p, de movimientos para realizar esta segunda fase. En total, se requieren 2h+1+2p=2k+1 movimientos, es decir, un números impar, como queríamos demostrar.
Como se trata de un número impar, afirmaremos que: <<Sea cual sea la dimensión del tablero, si p y q son dos posiciones consecutivas del Caballo Guasón, entonces la paridad de p es distinta de la paridad de q.>>
Según se va jugando, la casilla vacía es, alternativamente, blanca y negra. Entonces, afirmamos que: <<Sea cual sea la dimensión del tablero, si la posición inicial y final tienen la misma paridad, pero sus huecos respectivos están en casillas de distinto color, entonces el juego es imposible. Y si las posiciones inicial y final tienen distinta paridad, pero sus huecos están en casillas del mismo color, el juego es también imposible>>.

4.1  El Caballo Guasón 3×3

Empezaremos analizando el juego del Caballo Guasón en un tablero de dimensión 3×3. En principio, existen 9!=362880 posiciones distintas del tablero. Pero, el hueco no puede alcanzar la casilla central del tablero de ninguna manera, así que se puede afirmar que: <<En un tablero de dimensión 3 ×3, si el 5 no ocupa la posición central del tablero, entonces el juego es imposible>>. Esta condición deja, de momento, las posiciones posibles de un juego con solución en 8!=40320.
Figure 9: Tablero del Caballo Guasón 3×3 y su transformación.
Ya que el movimiento del hueco no se hace ahora entre dos casillas adyacentes, dado el tipo de movimiento del caballo, transformemos el tablero de juego en otro que muestre, mediante líneas, las relaciones de vecindad de las casillas. Por ejemplo, la casilla I (figura 9 izquierda), en realidad, es vecina de las casillas VI y VIII; la casilla II es vecina de las casillas VII y IX; y algo parecido podríamos decir de las demás. Estas relaciones de vecindad están recogidas, mediante líneas, en la figura 9 derecha, en la que se ha obviado la casilla V, que no interviene en el juego. El uso de este esquema o tablero transformado es muy simple; podemos mover de una casilla a otra vacía si ambas están conectadas mediante una línea. Es decir, se ha transformado el movimiento de caballo de la casilla vacía en su movimiento ordinario entre casillas adyacentes, lo que permitirá un análisis mucho más sencillo.
Como se observa en esta última figura, sólo pueden realizarse movimientos circulares de los números de la posición inicial, ya que no existe posibilidad en el tablero de alterar este orden circular. De forma que, considerando que el hueco se rellena con la ficha número 9, se puede afirmar:
En un tablero de dimensión 3×3, y situado el 5 en el centro del tablero, para que el juego del Caballo Guasón tenga solución es necesario y suficiente que las posiciones inicial y final del resto de números tengan el mismo orden circular.
Dado que, sin contar la casilla V, que ha de contener al 5, sólo quedan ocho casillas, este juego sólo puede tener, aparte de la posición final 123456789 (donde el 9 representa al hueco), otras 7 posiciones, que son: 234657891, 346758912, 467859123, 678951234, 789152346, 891253467 y 912354678. Todas ellas tienen el 5 en el centro y, el resto de cifras, tienen el mismo orden circular. Cualquiera de ellas sirve como posición inicial y también como posición intermedia.

4.2  El Caballo Guasón 4×4.

Pasemos ahora a analizar el juego en un tablero 4×4. En principio, transformemos, como antes, el tablero de juego en otro que ponga de manifiesto las vecindades de las casillas, pero esta vez emplearemos los números arábigos para designar a las casillas (figura ).
Figure 10: Tablero del Caballo Guasón de dimensión 4×4 y su transformado.

4.2.1  El problema particular.

El problema particular consiste en suponer que la posición final es la sucesión de los números en su orden natural, con el hueco colocado en la casilla 16 (llamaremos a esta disposición posición canónica). Se supone, además, que, en la posición inicial, el hueco siempre está en la casilla 16. Estas suposiciones no van en menoscabo de la generalidad del problema tratado, como se verá más adelante con más detalle. En efecto, si la posición final fuera otra y el hueco de la posición inicial no estuviera en la casilla 16, entonces el problema se divide en cuatro fases: 1ª Llevar el hueco a la casilla 16. 2ª Encontrar la foma, si existe, de llevar la nueva posición inicial a la posición canónica. 2ª Encontrar la forma, si existe, de llevar la posición final a la posición canónica. 3ª Realizar los movimientos encontrados en la segunda fase y, luego, hacer los movimientos contrarios a los encontrados en la tercera fase y en orden inverso.
Figure 11: Tablero restringido del Caballo Guasón ordinario.
Dada una disposición inicial en el tablero ordinario de dimensión 4×4 del Caballo Guasón, se traslada esta disposición al tablero transformado del juego (figura 10). En primer lugar colocaremos las fichas 1, 4 y 13 en sus casillas correspondientes y la ficha 10 en la casilla 16. Hecho esto, suprimiremos, momentáneamente, estas casillas del tablero transformado, así como los caminos que llegan a ellas. También renunciaremos a la conexión entre las casillas 2 y 9 y a la conexión entre 8 y 15. La figura 11 muestra el resultado de esta operación, el tablero restringido, en la que, además, hemos cambiado la posición de algunas casillas, pero no sus relaciones de vecindad, con lo que ambos tableros, el transformado y el restringido, son totalmente equivalentes, salvo por las casillas y caminos suprimidos.
Para continuar ahora nuestra argumentación, necesitamos demostrar la siguiente afirmación: Sea a1,a2,¼,a8 una permutación cualquiera de los ocho primeros números naturales y supongamos que está permitido hacer que un número sobrepase, hacia la izquierda o hacia la derecha, a otros dos números. Entonces, mediante este tipo de movimientos, la permutación inicial puede llevarse siempre a la permutación 1,2,3,4,5,6,7,8 o bien a la permutación 1,2,3,4,5,6,8,7.
Para demostrarla, supongamos que ak=1. Si k=1 no hay nada que hacer, pero si k ¹ 1, entonces podemos desplazar hacia la izquierda el número ak de dos en dos posiciones, hasta llegar a la primera posición (si k es impar) o a la segunda posición (si k es par). Si se llega hasta la primera, entonces han acabado los desplazamientos de ak=1. Si se llega a la segunda posición, entonces trasladamos hacia la derecha, dos posiciones, el número a1, de manera que, en cualquier caso, la permutación resultante siempre empieza por el número 1. Consideramos ahora la permutación resultante sin el 1 y volvemos a hacer las operaciones necesarias para que el 2 sea el primero. Así, colocando luego el 3, el 4... en sus posiciones correspondientes, quedará, finalmente, una permutación de dos números, la 7,8 o bien la 8,7, como queríamos demostrar. Este resultado es fácilmente ampliable a permutaciones de n elementos.
A la demostración dada podemos añadir la siguiente observación. Desplazar una cifra dos posiciones hacia la derecha o hacia la izquierda equivale a hacer dos intercambios de cifras consecutivas, de manera que la paridad de la permutación resultante no cambia. Dado que la permutación 12345678 es par, llegaremos a ella si la permutación inicial es par; y como la permutación 12345687 es impar, se terminará en ella si la permutación inicial es impar.
Consideremos ahora, en el tablero restringido, la configuración formada por las casillas 5,3,12,6,15,9,7 y 14, a la que llamaremos parte superior de este tablero. Al circuito cerrado formado por las casillas 5,3,12,6,15,9,7,14, en este orden circular, lo llamaremos camino mayor. Al circuito formado por las casillas 12,6,15,9,7,14 lo llamaremos camino menor. Al circuito formado por las casillas 5,3,12,14 lo llamaremos garaje, tal como hace Édouard Lucas en la octava recreación del Volumen I de sus Recreaciones Matemáticas5. Demostraremos a continuación la siguiente afirmación: Suponiendo que todas las casillas, salvo una, de la parte superior estén ocupadas y moviendo las fichas desde una casilla a otra adyacente y vacía, es posible trasladar cualquiera de las fichas dos posiciones hacia la izquierda o hacia la derecha, consideradas las casillas en el orden circular del camino mayor, dejando al resto de fichas en el orden que tenían.
En efecto, supongamos que, en las casillas de la parte superior, se encuentran, respectivamente, los números a1,a2,¼,a8, con ai Î {0,1,2,3,4,5,6,7} y donde el 0 representa el hueco. Supongamos que queremos desplazar dos posiciones el número ak ¹ 0. En primer lugar, mediante movimientos circulares a lo largo del camino mayor, llevaremos el número ak a la casilla 14 y el hueco a la casilla 12. El orden circular es el mismo que antes. Ahora, deslizamos ak hasta la casilla 12. Tras este movimiento, ak ha avanzado dos posiciones hacia la derecha en el orden circular del camino mayor. Mediante el movimiento contrario, ak avanzaría dos posiciones hacia la izquierda. El resto de números mantienen su posición circular. Esto es lo que queríamos demostrar.
De lo dicho en los dos párrafos anteriores, se deduce fácilmente que, en la parte superior, podemos ordenar las fichas como se quiera salvo, quizás, las dos últimas. Otro tanto podríamos decir de la parte inferior del tablero restringido, formado por las casillas 12,14,5,11,2,8,10,3. Recorridas en este orden, forman el camino mayor de la parte inferior. El camino menor está formado por las casillas 3,5,11,2,8,10. El garaje está formado también por las casillas 12,14,5,3. Para avanzar una ficha dos posiciones hacia la derecha, hay que llevarla ahora a la casilla 3, con hueco en 5. Luego, se pasa la ficha de 3 a 5. Con el movimiento contrario, la ficha avanzaría dos posiciones hacia la izquierda.
Volvamos ahora, tras todo lo dicho, a la estrategia que nos llevará a la solución. Recuérdese que las fichas 1,4 y 13 están colocadas en sus casillas correspondientes y que la ficha 10 está en la casilla 16. El siguiente paso consiste en colocar correctamente las casillas 7, 9, 15 y 6, en la parte superior del tablero restringido. Esta operación es siempre posible, gracias al garaje. Si alguna de ellas estuviera colocada en la parte inferior, entonces los primeros movimientos irían destinados a subirla a la parte superior.
Una vez colocadas estas fichas, la permutación actual presentará un aspecto semejante a la siguiente tabla:
Casilla12345678910111213141516
Ficha1a1a24a367a49a5a6a713a81510
Ahora, trabajando en el camino mayor de la parte inferior y usando convenientemente el garaje, podemos establecer una de las siguientes disposiciones, donde las casillas han sido dispuestas según el orden de este camino mayor, empezando por la 8:
Posición I
Casilla821151412310
Ficha8211514123
Posición II
Casilla821151412310
Ficha8211514312
Sea cual sea la posición encontrada, añadiremos un último movimiento consistente en trasladar la ficha 10 desde la casilla 16 hasta la casilla 10, con lo que las dos posiciones finales a las que podríamos llegar serían las siguientes, donde la Posición Final I viene de la Posición I y la Posición Final II viene de la Posición II:
Posición Final I
Casilla12345678910111213141516
Ficha123456789101112131415
Posición Final II
Casilla12345678910111213141516
Ficha123125678910113131415
Para llegar a cualquiera de estas dos posiciones finales, se ha tenido que realizar un número par de movimientos, ya que el hueco empezó y terminó en la misma casilla. Además, la Posición Final I, que es la posición canónica y, por tanto, la solución buscada, es par, y la Posición Final II es impar. Esto demuestra que, si queremos llegar a la solución correcta hemos de partir de una disposición par y que, si la disposición inicial es impar, entonces el juego no tiene solución. Dicho de otra manera:
En un tablero de dimensión 4×4, el problema particular del juego del Caballo Guasón tiene solución si y sólo si la posición inicial es par. El juego requiere, entonces, de un número par de movimientos.

4.2.2  El problema general.

El problema general, en el que se considera cualquier posición inicial y cualquier posición final, es ahora bastante accesible. Consideremos cualquier posición inicial y llevemos el hueco a la casilla 16 del tablero, encontrando así una posición intermedia. Designaremos con N1 al número de movimientos necesarios para ir de la posición inicial a la intermedia. No importa demasiado el camino que siga el hueco en este paso, ya que, sea cual sea, la paridad de N1 es invariante y ésta es la propiedad que nos interesa de él. Para que exista solución, la posición intermedia ha de ser par, como ya se ha dicho en el problema particular, lo que condiciona, junto con la paridad de la posición inicial, la paridad de N1 y la propia existencia de la solución. En efecto, si la posición inicial y N1 tienen paridades distintas, entonces el juego no tiene solución.
Supuesto que la posición inicial y N1 tengan la misma paridad, encontremos ahora la forma de pasar de la posición intermedia a la posición canónica y sea N2 el número de movimientos necesario. Como la posición intermedia es par, forzosamente ha de cumplirse que N2 sea par. Este camino está, como se vio más arriba, asegurado en estas condiciones.
Finalmente, llamaremos N3 al número de movimientos necesario para pasar de la posición canónica a la posición final. La existencia de este camino viene condicionada por las paridades de N3 y de la posición final. Dado que partimos de una posición par (la posición canónica), N3 y la posición final han de tener la misma paridad.
En resumen, el problema general del Caballo Guasón en el tablero de dimensión 4×4 tiene solución si y sólo si N1 y la posición inicial tienen la misma paridad y N3 y la posición final también.

5  El Caballo Guasón 8×8

Si planteamos el problema del Caballo Guasón en un tablero usual de ajedrez, es decir, en un tablero de dimensión 8×8, lejos de complicarse, como parecería normal, el problema se simplifica enormemente. En efecto, es bastante conocido, al menos desde el siglo IX, el problema del recorrido de un caballo sobre un tablero de ajedrez, que puede enunciarse así:
Encontrar la sucesión de movimientos consecutivos que ha de hacer un caballo de ajedrez, siguiendo las reglas usuales, para que, saliendo desde cualquier casilla del tablero ordinario, pase una única vez por todas las casillas del tablero.
Cada solución de este problema se llama recorrido, paseo o peregrinación del caballo. Si, además, el recorrido cumple que desde la última casilla visitada por el caballo se puede acceder a la primera, con un único movimiento del caballo, entonces el recorrido se llama cerrado.
Figure 12: Recorrido mágico de Euler.
El gran Euler (1707-1783) aportó numerosas e ingeniosas soluciones a este problema y fue el primero que trató matemáticamente este problema. Si la casilla inicial se rotula con un 1, la siguiente del recorrido con un 2 y, así, sucesivamente, hasta la última casilla, que se rotula con un 64, pueden construirse, además, cuadrados casi mágicos, como lo hizo el propio Euler. Entonces, el recorrido se llama mágico. La figura 12 muestra un recorrido mágico de Euler, en el que cada columna y cada fila suman 260, no así las diagonales. Nótese que este recorrido no es cerrado.
Figure 13: Recorrido cerrado de Al-Adli.
Para nuestro propósito, vamos a usar un recorrido cerrado dado por Al-Adli ar-Rumi, en el año 840, que aparece comentado en un manuscrito árabe del siglo IX y cuyo autor es Abu Zakariya Yahya ben Ibrahim al-Hakim. Tal recorrido se muestra en la figura 13.
Figure 14: Tablero reducido del Caballo Guasón 8×8.
El camino cerrado constituye un circuito que el hueco del Caballo Guasón puede recorrer. Simplemente hay que encontrar cuatro casillas que formen un garaje. Para ello, buscaremos la casilla n tal que esté conectada, mediante un único salto de caballo con la casilla n+3 (restándole a este valor el número 64 si se diera el que caso de que n+3 > 64). Esta circunstancia ocurre, por ejemplo, con la casilla 3, conectada con la 6, de manera que las casillas 3, 4, 5, 6 pueden formar un garaje y el resto de casillas forman un circuito alrededor de este garaje, como muestra la figura 14.
Nótese que en la figura 14, prescindimos de muchas de las vecindades de las casillas, lo que nos hará perder eficacia a la hora de encontrar la solución, pero ganaremos, a cambio, mucha claridad y comprensión. Efectivamente, según lo dicho en apartados anteriores, usando de forma conveniente el garaje, podemos transformar cualquier posición inicial en la sucesión ordenada de los números 1, 2, ..., 62, tras la que vendrá la serie 63-64 o bien la serie 64-63, considerando que 64 es el hueco. De forma que, si el hueco está en la misma posición al principio y al final, una permutación par sólo podrá llevarse a otra posición par y una permutación impar sólo podrá llevarse a una permutación impar.

6  Anexo.

Tras publicar este artículo en la web, Rodolfo Valeiras me escribió un amable correo electrónico en el que aportaba una información muy interesante, además de hacerme una observación valiosa sobre un punto algo confuso del artículo original. Rodolfo Valeiras es coautor de un libro muy interesante sobre rompecabezas matemáticos llamado Orden en el Caos, Editorial Amuzara, 2006, además de mantener una muy buena página web con sus aficiones favoritas, matemáticas recreativas y puzles de ingenio (http://www.rodoval.com/heureka/index.html).
En el mensaje que me envió dice lo siguiente: <<Aparentemente, el juego <<Parking Zone>> está basado en <<Leapin Lizards>>, de ThinkFun (antes llamado <<Binary Arts>>). Han cambiado los colores, pero el mecanismo del juego es el mismo y también, al menos, los tres primeros niveles. Este juego fue inventado por Larry Nichols y los niveles están diseñados por Serhiy Grabarchuk. Se vendió en España hace años con el nombre de <<Lagarto, vuelve a casa>>. Creo que hoy ya no se fabrica (aunque aún se puede encontrar en algunas tiendas que venden por Internet)>>.
Figure 15: Tablero de Leaping Lizards. Nivel 1.
Además, Rodolfo Valeiras me añade el tablero transformado para el nivel 1 de este juego (figura 15). Este tablero puede presentarse en uno parecido al de la figura 4, pero en el que las casillas I y VI están conectadas y también las casillas III y IV, de manera que podría colocarse sobre una cinta de Moebius. Esta observación del Sr. Valeiras parece muy interesante y digna de ser estudiada.

Footnotes:

1www.pekegifs.com/juegos2/estrategia/aparcamiento.htm
2Jugando en línea en la web citada, esto se consigue pulsando el botón del ratón sobre el coche que se quiera mover.
3Miguel de Guzmán(1988): Aventuras Matemáticas, Editorial Labor, Barcelona. Capítulo 3.
4Édouard Lucas (1891): Récréations Mathématiques, Volumen I, 2ª edición, reeditada por Albert Blanchard en 1992. Es la octava recreación: Le Jeu du taquin.
5Libro, por cierto, y dicho sea de paso, que se publicará en castellano por la Editorial Nivola, traducido por el mismo autor de este artículo.


File translated from TEX by TTH, version 3.76.
On 03 Mar 2007, 18:59.