A finales de febrero o primeros de marzo de 2020 me encontré por casualidad con un juego para ordenadores Atari de 8 bits llamado Mandarinov Hlavolam o, en español, El rompecabezas del mandarín.
Lo probé con un emulador y a pesar de la barrera lingüística (todos los textos estaban en eslovaco) me percaté de que se trataba de un rompecabezas similar al juego del 15, aunque con un tablero de forma extraña y movimiento tipo caballo de ajedrez. La idea me resultó atractiva y novedosa, aunque no debería haberlo sido tanto (tan novedosa), ya que hacía tiempo que había leído un artículo de Antonio Javier Serrano Mora donde la analizaba en relación con tableros cuadrados después de mencionar que era una propuesta de Miguel de Guzmán. (¡Esa memoria!)
Antonio Javier Serrano analiza las posiciones resolubles para tableros 3×3, 4×4 y 8×8, y aunque no es su asunto principal, de sus explicaciones pueden extraerse métodos de resolución.
El rompecabezas del mandarín presenta tres variantes de juego, las tres con el mismo tablero: una con posición inicial fija, otra con posición inicial aleatoria y otra en la cual las piezas no contienen números sino líneas rectas y curvas que una vez ordenadas forman un diseño que parece una red de tuberías o de metro. En las tres variantes el hueco libre debe quedar al final en la posición inferior.
Después de intentar resolverlo con el emulador y comprobar que a su dificultad intrínseca se sumaba la incomodidad de la interfaz (ya que había que seleccionar las piezas a mover desplazando un cursor con el mando de juegos) decidí hacer rápidamente un simulador sencillo que se pudiera manejar con el ratón. Casi dos años después ese simulador estuvo (más o menos) terminado: se llama Manhla.
He llamado Manda a la primera variante de El rompecabezas del mandarín y a la segunda Manda aleatorio (aunque en lo sucesivo omitiré normalmente la palabra «aleatorio»). Por si no ha quedado claro, se trata de un juego similar al Juego del 15, con un tablero que es un subconjunto de una cuadrícula 7×7, con todas sus casillas menos una ocupadas por piezas que se pueden mover sucesivamente de una en una. Pero si en el Juego del 15 se trata de deslizar una pieza adyacente al hueco, en este caso el movimiento hacia el hueco es como el de un caballo de ajedrez. El objetivo es disponer las piezas en orden normal, de arriba abajo y de izquierda a derecha, con el hueco abajo del todo.
Lo primero que podemos plantearnos es si cualquier posición inicial de las 24 piezas numéricas puede conducir a la posición final. Obviamente, ni el juego original ni mi programa Manhla van a cometer el pecado de ofrecer una posición inicial irresoluble, pero supongamos que tenemos una versión física del juego tal que las piezas se pueden sacar y recolocarlas de cualquier manera. ¿Tendremos la seguridad de que siempre va a ser posible resolver el juego? Hace más de 140 años muchas personas se enfrentaron a un problema similar con el Juego del 15. Hoy es conocido que en ese caso la probabilidad de que la posición inicial aleatoria sea resoluble es 1/2. Lo mismo sucede en el caso de Manda. Vamos a demostrar ambos casos. Empecemos con el Juego del 15
Considerando el hueco una pieza especial invisible con el número 16, una posición cualquiera puede hacerse corresponder con un elemento de S16, el conjunto de todas las permutaciones de los números 1, 2, 3,..., 16. Pero hagamos una pequeña incursión en el terreno general de las permutaciones, empezando con un ejemplo más manejable.
Llamaremos S5 al conjunto de todas las permutaciones de los números 1, 2, 3, 4 y 5. Una permutación es simplemente una ordenación de esos cinco números, de modo que 12345 es un elemento de S5 y 42153 es otro. En total hay 5! = 120 elementos en S5. Fijémonos en 42153. Vemos que el 4 aparece antes que el 2, siendo 4 mayor que 2. Esto es una inversión. Contemos todas las inversiones de 42153: 4-2, 4-1, 4-3; 2-1; 5-3. Hay en total 5 inversiones. Como 5 es un número impar decimos que la permutación 42153 es impar. Obviamente, la permutación 12345 tiene 0 inversiones y es par. Para cualquier n, Sn tiene n! permutaciones y (a partir de n = 2) la mitad de ellas son pares y la otra mitad impares. Lo primero es fácil de demostrar por inducción:
Si en una permutación intercambiamos dos números cambia la paridad de la nueva permutación con respecto a la original. Un intercambio (más técnicamente una trasposición) consiste en cambiar las posiciones de dos de los números que forman la permutación. Por ejemplo una trasposición convierte 42153 en 45123, ya que ha llevado el 2 donde estaba el 5, el 5 donde estaba el 2 y ha dejado inalterados los demás números. Vamos a analizar cómo afecta a las inversiones una trasposición. (The reader no interested en demostraciones puede saltarse los siguientes párrafos.)
Supongamos que la trasposición intercambia las cifras a y b, de forma que antes de la trasposición a estaba a la izquierda de b y después está a su derecha. Las demás cifras pueden dividirse en tres grupos: las que están a la izquierda de a y b, que llamaremos i, las que están a la derecha de a y b, que llamaremos d, y las que están entre a y b (antes de la permutación están a la derecha de a y a la izquierda de b y después al revés), que llamaremos m. La trasposición transforma
i1i2...iαam1m2...mβbd1d2...dγ
en
i1i2...iαbm1m2...mβad1d2...dγ
Obviamente solo hay que considerar las inversiones en las que intervienen a o b, ya que las demás cifras permanecen estáticas. Vemos que las posiciones relativas de las cifras del grupo i y del grupo d no varían ni con respecto a a ni con respecto a b, de modo que las inversiones en las que intervienen estas con a o con b también serán las mismas. Fijémonos pues en las cifras del grupo m. Si una de estas cifras formaba una inversión con a antes de la trasposición (porque es menor que a), dejará de hacerlo después; y si no la formaba antes (porque es mayor que a) lo hará después. Si antes de la trasposición había s cifras del grupo m formando inversión con a (s ≤ β), después habrá β − s. Podemos razonar con b de la misma forma y concluir que si antes de la trasposición había t inversiones (t ≤ β) después habrá β − t. El número de inversiones de las cifras del grupo m con a y con b era antes s + t y después β−s + β−t = 2 × β − (s + t). Si a un número par (como 2 × β) le restamos un número par, el resultado es par; si le restamos un número impar, el resultado es impar. El número de inversiones con a y b de las cifras del conjunto m puede variar, pero su paridad no.
Queda por tener en cuenta el par a-b, que se transforma en b-a. Si a < b, la trasposición hace que haya una inversión más. Si a > b, la trasposición hace que haya una inversión menos. En ambos casos la paridad del número de inversiones cambiará.
Podemos demostrar que en Sn (n > 2) hay el mismo número de permutaciones pares que de impares así. A cada permutación par le hacemos corresponder la que resulta de intercambiar sus dos primeros elementos. Esta segunda permutación será impar. Si tomamos dos permutaciones pares distintas, sus correspondientes por la operación descrita serán también distintas. Esto implica que hay al menos tantas permutaciones impares como pares. Si tomamos una permutación impar podemos obtener la permutación par que le corresponde. Esto implica que no hay más permutaciones impares que pares. Es decir, que hay la misma cantidad de ambos tipos.
Volviendo al Juego del 15, la disposición de las casillas permite colorearlas usando dos colores, digamos blanco y negro, de forma que dos casillas contiguas sean de distinto color (como un tablero de ajedrez). Si en determinado momento el hueco está en una casilla negra, después de un movimiento estará en una blanca y viceversa. Partamos de la posición final, con los números por orden y el hueco abajo a la derecha, digamos que en una casilla blanca. En todo momento, después de haber hecho una serie de movimientos legales tendremos que si la casilla del hueco es blanca habremos realizado un número par de movimientos y si es negra, ese número será impar. Se tiene también que, considerando la posición como una permutación de S16, cada movimiento es un intercambio del número 16 con otro número. Por tanto cada movimiento cambia la paridad de dicha permutación. Sabemos que la posición final es par, así que las posiciones pares con el hueco en una casilla negra y las posiciones impares con el hueco en una casilla blanca serán irresolubles. En particular, la posición con todas las piezas por orden menos las dos últimas y el hueco abajo a la derecha es irresoluble. Si en cualquier momento, después de una serie de movimientos legales a partir de la posición final, intercambiamos dos piezas cualesquiera, la posición obtenida será irresoluble.
Los razonamientos aplicados al Juego del 15 se pueden aplicar también a Manda (en cualquiera de sus variantes), ya que el caballo de ajedrez también va de una casilla blanca a una negra y viceversa. Así que tenemos, en ambos casos, dos tipos de posiciones posibles:
Hemos demostrado que todas las posiciones de tipo 2 son irresolubles. Falta demostrar que todas las de tipo 1 sí son resolubles.
Como antes, empezaremos con el Juego del 15 antes de pasar a Manda, pero antes aún nos fijaremos en otro juego del mismo tipo.
Consideremos el juego cuya posición final está representada en la siguiente imagen.
Como el Juego del 15 y Manda, se trata de un juego en el que hay n casillas (16 en este caso) y n − 1 (15) piezas numeradas, consistiendo cada movimiento en cambiar la posición de una pieza llevándola a la casilla libre siempre que haya una conexión entre dicha casilla libre y aquella donde estaba la pieza. En el caso del Juego del 15 las conexiones están determinadas por el hecho de que las casillas compartan un lado. En el caso de Manda dos casillas están conectadas si se puede ir de una a otra de acuerdo con el movimiento del caballo de ajedrez. En este juego nuevo las conexiones se marcan explícitamente con líneas al modo de los grafos. El objetivo es, desde una posición aleatoria, alcanzar la que se muestra en la imagen. Esta posición final nos sirve para numerar las casillas, de modo que el objetivo es llevar cada pieza a la casilla con su número. A la casilla que debe quedar libre le adjudicaremos el número 16.
En este juego hay dos tipos de conexiones y movimientos asociados a ellas. Llamaremos conexiones regulares a las que se corresponden con lados del hexadecágono, es decir, las que conectan las casillas n y n + 1, con n = 1...15, además de la 16-1. Llamaremos conexión especial a la 1-4.
Como en los casos anteriores, en este Hexadecágono con salto-2 se pueden colorear las casillas de blanco y negro de forma que no haya dos conectadas del mismo color. Usando los mismos razonamientos del apartado anterior podemos concluir que las posiciones correspondientes a una permutación de S16 par con la casilla vacía de distinto color que en la posición final y las posiciones correspondientes a una permutación de S16 impar con la casilla vacía del mismo color que en la posición final (posiciones de tipo 2) son irresolubles. Vamos a demostrar que las demás (las de tipo 1) sí son resolubles.
Vamos a llamar cadena correspondiente a una posición a la serie de las 15 piezas empezando por la 1 y siguiendo el orden de las agujas del reloj a través del hexadecágono, sin tener en cuenta el hueco. Una cadena es un elemento de S15 que empieza por 1. Por ejemplo, en la posición de la siguiente imagen la cadena es 1-13-5-3-6-9-14-2-15-12-7-11-8-4-10.
Un movimiento regular no modifica la cadena (dicho con más precisión: la cadena de una posición cualquiera es la misma que la de la posición que resulta de hacer un movimiento regular). Por tanto, los movimientos regulares no afectan a la paridad de la cadena (más aún: no afectan a la cadena en absoluto). Veamos qué consecuencias tienen los movimientos asociados a la conexión 1-4.
El movimiento 1 → 4 equivale a realizar sucesivamente las siguientes operaciones (suponemos que partimos de la situación de la figura 4):
El primer intercambio cambia la paridad de la cadena, pero el segundo vuelve a dejarla como estaba. Los movimientos regulares no afectan a su paridad, como vimos antes.
Es obvio que con el movimiento 4 → 1 se puede razonar igual, así que los movimientos especiales asociados con la conexión 1-4 tampoco afectan a la paridad de la cadena.
Así pues ningún movimiento del juego afecta a la paridad de la cadena. La cadena de la posición final es 1-2-3-...-15-16, que tiene 0 inversiones y por tanto es par. Las posiciones con cadena impar son irresolubles. Veamos que todas las de cadena par sí son resolubles.
A partir de cualquier posición podemos hacer movimientos para llegar a otra de forma que la pieza que ocupaba el lugar r dentro de la cadena ocupe ahora el lugar r − 1, siendo r cualquier número entre 3 y 14, y sin afectar a las piezas 1...r − 2. Si r = 3 se trata de adelantar la tercera pieza de la cadena a la segunda posición sin afectar a la pieza 1. Si r = 4 se trata de adelantar la cuarta pieza de la cadena a la tercera posición sin afectar a las piezas 1 y 2. Si r = 14 se trata de adelantar la pieza que ocupaba la posición 14 a la posición 13 sin afectar a las piezas 1,2,3...11.
En todo momento es posible hacer dos movimientos regulares, uno en el sentido de las agujas del reloj, que llamaremos positivo, y otro en el sentido contrario, que llamaremos negativo. Siempre es posible hacer 15 movimientos positivos consecutivos, con la consecuencia de que el conjunto de todas las piezas (e incluso el hueco) se habrá trasladado una posición en el sentido de las agujas del reloj. Análogamente es posible hacer 15 movimientos negativos consecutivos, provocando una traslación global de una posición, ahora en el sentido contrario al de las agujas del reloj. Llamaremos a estas maniobras giro global positivo o negativo. Ninguna de las dos cambia la cadena. Mediante giros globales sucesivos es posible llevar cualquier pieza a cualquier casilla sin cambiar la cadena. Pues bien, podemos adelantar la pieza de la posición r a la r − 1 así:
Y ya está: la pieza que ocupaba la posición r de la cadena ahora ocupa la posición r − 1; las piezas 1...r − 2 no se han visto afectadas. Lo que hemos hecho es atrasar la pieza r − 1 dos lugares, con el efecto secundario de adelantar la r y la r + 1.
Repitiendo este procedimiento podemos llevar la pieza 2 a la posición 2 de la cadena, después la pieza 3 a la 3, etc. hasta llevar la pieza 13 a la posición 13. En ese momento faltarán solo las piezas 14 y 15, que ya deben estar en el orden correcto, puesto que de lo contrario la cadena sería impar.
Partiendo de cualquier posición con cadena par podemos hacer movimientos de forma que la cadena se vaya transformando hasta convertirse en 1-2-3-...-14-15. Una vez hecho esto podemos hacer giros globales hasta que la pieza 1 esté en la casilla 1. Después podemos hacer movimientos regulares sin tocar la pieza 1 para que la casilla libre sea la 16 y el juego estará resuelto.
Las posiciones de tipo 1 son las de cadena par y las de tipo 2 las de cadena impar.
Sea una posición de tipo 1 con la permutación de S16 par y la casilla libre del mismo color que en la posición final. Podemos hacer movimientos regulares, que no cambian la cadena, hasta dejar el hueco en la casilla 16. El número de movimientos que hemos hecho tiene que ser par y la paridad de la permutación de S16 es par. Tomando los primeros quince elementos de esa permutación tenemos una permutación de S15 que también tiene que ser par. Así que la cadena es par.
Sea una posición de tipo 1 con la permutación de S16 impar y la casilla libre de color distinto que en la posición final. Podemos hacer movimientos regulares, que no cambian la cadena, hasta dejar el hueco en la casilla 16. El número de movimientos que hemos hecho tiene que ser impar y la paridad de la permutación de S16 es par. Tomando los primeros quince elementos de esa permutación tenemos una permutación de S15 que también tiene que ser par. Así que la cadena es par.
Hemos demostrado que todas las posiciones de tipo 1 tienen cadena par. Y ya demostramos antes que todas las posiciones con cadena par se pueden resolver, así que pertenecen al tipo 1. Si las posiciones de tipo 1 son las de cadena par, las de tipo 2 tienen que ser las de cadena impar.
Aunque Hexadecágono con salto-2 sea un juego interesante, hemos de confesar que su estudio ha sido un paso previo para aplicarlo al de las posiciones resolubles del Juego del 15 y Manda. Considérese el juego incluido en Manhla llamado «4x4 con paredes - 15» y cuya posición final se muestra en la imagen:
Se trata de una modificación del Juego del 15 en la que se han insertado paredes entre algunas casillas, eliminando así varias conexiones. El grafo correspondiente al Juego del 15 es este:
Eliminando las conexiones que anulan las paredes queda así:
Este grafo es equivalente al de Hexadecágono con salto-2 pero con los nodos numerados de otra forma. Podemos resolver el juego igual que antes pero formando la cadena 15-11-10-14-13-9-5-1-2-6-7-3-4-8-12. Siguiendo el método antes descrito, después de colocar la pieza 4 quedarán por colocar la 8 y la 12. Si después de llevar a su posición definitiva (el 15 en la casilla 15, la casilla 16 vacía) tuviéramos las piezas 8 y 12 invertidas estaríamos ante una posición de tipo 2 y habríamos partido también de una posición de tipo 2.
Es obvio que también en El juego del 15 podríamos resolver cualquier posición de tipo 1, simplemente limitándonos a las conexiones de «4x4 con paredes - 15».
Esta demostración está basada en la de Édouard Lucas que figura en su libro «Recreaciones matemáticas 1» (Editorial Nivola, 2007, páginas 178-180). Antonio Javier Serrano aplica la misma idea al Guasón 8×8 (o Manda 8×8). Lo que aquí hemos llamado salto-2 es llamado por Lucas (y Serrano) garaje.
Uno de los problemas más antiguos de las matemáticas recreativas es el de los recorridos del caballo de ajedrez. Se trata de llevar un caballo por todos los escaques de un tablero, sin omitir ninguno ni visitar ninguno dos veces. Si, además, es posible volver a la casilla de partida desde la última del recorrido se dice que es cerrado. Si lo pensamos un poco, un recorrido cerrado en el que haya un salto-2 o garaje es lo único que necesitamos para demostrar que todas las posiciones de tipo 1 son resolubles (ya sabíamos que las de tipo 2 no lo son). Antonio Javier Serrano ya encontró uno: el que descubrió en el siglo IX al-Adli ar-Rumi:
Se pueden encontrar varios saltos-2 a lo largo del recorrido; el primero es el marcado con una línea roja, que une las casillas visitadas en tercer y sexto lugar. Se podría hacer un juego parecido al Hexadecágono con salto-2 de antes pero con 64 vértices (figura llamada, según acabo de aprender, hexacontakaihexágono) y razonar igual que antes, ya que el número 16 no tenía nada de especial aparte de ser par. Y esto sí es importante, ya que en cierto momento de la discusión adelantábamos o atrasábamos un número 12 posiciones (ahora serían 60; en general, n − 4) y era esencial que este número fuera par. De hecho, si n no hubiera sido par (por ejemplo, si hubiéramos partido de un tablero sin una de las casillas de las esquinas) hubiera sido imposible encontrar un recorrido de caballo cerrado.
En el caso de Manda (con el tablero original del juego) tenemos 25 casillas y es imposible que haya un recorrido cerrado. Recordemos que el salto de caballo siempre va de una casilla blanca a una negra y viceversa. Si el caballo empieza su peregrinación en una casilla blanca, la siguiente será negra, la tercera otra vez blanca, etc. La casilla número 24 será negra y la 25 blanca, siendo imposible que esta esté conectada con la primera, que también era blanca.
Si pintamos de blanco la casilla 1, las otras tres «puntas» del tablero (10, 16 y 25) también serán blancas y habrá 13 casillas blancas y 12 negras.
Podemos intentar encontrar un recorrido cerrado eliminando una casilla blanca. Intentaremos, además añadir a ese circuito cerrado un salto-2. Javier Santos hizo ya este trabajo, encontrando el circuito representado en la imagen (el puente-2 de rojo) tras eliminar la casilla 16:
Javier lo representó de forma mucho más artística y adecuada al caso:
Una vez colocada la pieza 16 (siempre posible, obviamente) podemos razonar como antes, demostrando que se puede ordenar la serie completa de números hasta que queden dos que ya deben estar ordenados. Esto prueba que también en la versión original de Manda, todas las posiciones de tipo 1 son resolubles.
Como se dijo antes en el caso del tablero 8×8, este método de resolución es extremadamente ineficaz. Veremos después otro mejor.
Antonio Javier Serrano demuestra la resolubilidad del Guasón 4×4 de otra forma (que nos será útil más adelante), pero el método aprendido con Manda puede servirnos también para las versiones 4×4 y 5×5. Recordemos que no se trata de encontrar sistemas de resolución prácticos, sino de analizar la resolubilidad de las posiciones de tipo 1.
En el caso del 4×4, aunque el número de casillas blancas y negras es el mismo, está demostrado que no hay un recorrido cerrado. Tampoco puede haberlo si eliminamos una casilla (ya que queda un número impar de ellas), pero sí si eliminamos dos (de distinto color):
Como se ve en la imagen, hemos eliminado del grafo las casillas 1 y 4 así como las conexiones en las que intervienen y (con ayuda del sitio web Graph Online) hemos encontrado un circuito cerrado (también conocido como ciclo hamiltoniano: marcado de naranja en la imagen) que además tiene (por ejemplo) el salto-2 5-14 (hay otros cinco, todos marcados de azul). Habría que demostrar (parece obvio, pero no vamos a hacerlo explícitamente) que es posible, a partir de cualquier posición de tipo 1, llevar la pieza 1 a la casilla 1 y después, sin mover la pieza 1, la pieza 4 a la casilla 4. Lo que queda es una posición que se puede resolver con el mismo método que hemos usado ya antes.
La siguiente imagen representa un ciclo hamiltoniano obtenido en el sitio antes citado tras suprimir del grafo de Manda 5×5 la casilla 21 y sus conexiones. Hay un salto-2 (por ejemplo) en 18-15.
Aparentemente el mismo método podría emplearse para demostrar la resolubilidad de todas las posiciones de tipo 1 en (entre otras) todas las variantes cuadradas (con lado mayor que 3) de Manda.
En todos los casos estudiados, el conjunto de todas las posiciones posibles se divide en dos subconjuntos que hemos llamado de tipo 1 y de tipo 2, siendo las de tipo 1 resolubles y las de tipo 2 irresolubles. Es imposible pasar de una posición de un tipo a una posición del otro mediante movimientos legales. Se puede pasar de una posición de un tipo a una posición del otro intercambiando dos piezas.
Aunque no era ese el objetivo, al demostrar la resolubilidad de las posiciones de tipo 1 hemos expuesto métodos de resolución, aunque muy ineficientes. A continuación veremos métodos más prácticos.