Historia de los puzles deslizantes: del 15 Puzzle a Rush Hour

La idea central de un puzle deslizante es un marco con piezas y espacio insuficiente: solo puedes mover una pieza al hueco. Esa idea ya estaba sobre el papel antes de la versión famosa. Una patente estadounidense concedida a Ernest Kinsey en 1878 describe bloques de puzle que se deslizan dentro de un marco con un hueco.

El puzle que la hizo famosa fue el 15 Puzzle: quince fichas numeradas en una bandeja de cuatro por cuatro con un hueco. La prolongada investigación de Jerry Slocum y Dic Sonneveld, recogida en su libro The 15 Puzzle de 2006, lo atribuye a Noyes Chapman, director de la oficina postal de Canastota, en el estado de Nueva York. A finales de 1879 ya se vendían versiones como Gem Puzzle.

Fuentes1Fuente 1Kinsey, E. U. (1878). Improvement in puzzle-blocks (U.S. Patent No. 207,124). U.S. Patent Office.2Fuente 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

En los primeros meses de 1880, el 15 Puzzle se convirtió en una fiebre. Se extendió por Estados Unidos en semanas y después por Europa, apareciendo en oficinas, salones y columnas de periódicos. Los relatos difieren sobre las semanas exactas, pero en primavera estaba por todas partes y en verano decaía. Chapman solicitó una patente que se rechazó; la razón no es segura, y una explicación probable es que patentes anteriores de bloques deslizantes ya cubrieran la idea.

Parte de la fascinación era que algunas posiciones parecían imposibles, y lo eran. En 1879, William Woolsey Johnson y William Story publicaron notas en el American Journal of Mathematics que mostraban que exactamente la mitad de las disposiciones nunca puede resolverse. El argumento se apoya en la paridad: cada deslizamiento cambia la disposición manteniendo fijo un recuento oculto par o impar, así que no puede alcanzarse una posición con el recuento equivocado, por mucho que se intente.

Ese resultado explica el truco más famoso de su historia. Intercambia solo el 14 y el 15 en una bandeja terminada y tendrás una posición que parece a un movimiento de la solución y en realidad es inalcanzable.

Fuentes3Fuente 3Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397–404.

Durante casi todo el siglo XX se atribuyó el 15 Puzzle a Sam Loyd, el autor de puzles más conocido de Estados Unidos. Loyd decía haberlo inventado y haber ofrecido un gran premio por resolver el imposible intercambio 14–15. Slocum y Sonneveld encontraron que lo afirmó por primera vez en 1891, más de una década después de la fiebre, y lo mantuvo hasta morir en 1911. No hay pruebas de que tuviera nada que ver con la invención ni de que el premio se ofreciera en 1880.

La afirmación perduró porque Loyd era famoso, sus libros se reimprimían mucho y otros autores la repetían. Recuerda que conviene comprobar la historia de los puzles, como cualquier historia, frente a los registros.

Fuentes2Fuente 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

La siguiente gran familia cambió el objetivo. En vez de ordenar fichas, había que mover un bloque grande hacia una salida entre otros pequeños. Una patente solicitada por Lewis W. Hardy en 1907 y concedida en 1912 describe diez bloques de distintos tamaños empaquetados en una caja que se mueven solo deslizándose. Un diseño muy relacionado se vendió como Pennant Puzzle.

Después aparecieron puzles similares con muchos nombres. La colección del Smithsonian conserva un Dad’s Puzzler, con derechos de autor de 1926, con un bloque cuadrado grande, varios rectángulos y dos cuadrados pequeños. En muchos países la familia se conoce hoy como Klotski, y en China una versión llamada Huarong Dao cuenta la historia de un general que escapa de una emboscada. Las soluciones mínimas de las disposiciones clásicas rondan los ochenta movimientos, según cómo se cuente uno.

En los años noventa la idea encontró su forma moderna más exitosa. El diseñador japonés Nob Yoshigahara creó un puzle de coches deslizantes llamado Tokyo Parking, y Binary Arts, luego ThinkFun, lo publicó en Estados Unidos en 1996 como Rush Hour. Coches y camiones bloquean una cuadrícula pequeña; los deslizas adelante y atrás hasta que tu coche puede salir. Las tarjetas de desafío graduadas lo convirtieron de un solo puzle en una serie, habitual en aulas y mesas familiares.

Fuentes4Fuente 4Hardy, L. W. (1912). Puzzle (U.S. Patent No. 1,017,752). U.S. Patent Office.5Fuente 5Smithsonian National Museum of American History. (n.d.). Dad’s Puzzler, once owned by Olive C. Hazlett [Object 2015.0027.04].6Fuente 6Contreras, M. (2018, February 1). The evolution of ThinkFun’s Rush Hour. ThinkFun. Archived by the Internet Archive, 25 December 2022.

Los puzles deslizantes parecen juguetes, pero son objetos serios de la informática. Hasta 1999 no se estableció que cualquier posición resoluble del 15 Puzzle puede terminarse en un máximo de ochenta movimientos de una sola ficha; Korf y Schultze lo confirmaron después con una búsqueda de veintiocho días que encontró exactamente diecisiete posiciones que necesitan los ochenta.

En 2002, Gary Flake y Eric Baum demostraron que la forma general de Rush Hour, en un tablero de cualquier tamaño, es PSPACE-completa, una clase que se cree aún más difícil que los famosos problemas NP-completos. Robert Hearn y Erik Demaine demostraron después, en 2005, que los puzles deslizantes generales también lo son, incluso si cada bloque es el mismo dominó pequeño. En términos sencillos, no hay ningún atajo conocido que resuelva rápidamente todos los tableros, justo lo que mantiene interesante un buen puzle deslizante.

Fuentes7Fuente 7Korf, R. E., & Schultze, P. (2005). Large-scale parallel breadth-first search. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05) (pp. 1380–1385). AAAI Press.8Fuente 8Flake, G. W., & Baum, E. B. (2002). Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theoretical Computer Science, 270(1–2), 895–911.9Fuente 9Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2), 72–96.

OutBrick pertenece a la rama de sacar un bloque, con un giro propio: cada ladrillo tiene un destino. Solo sale por la puerta de su color, y hoy también puede intercambiarse con un vecino para que tres de un color se alineen y desaparezcan. Despejar un tablero consiste en averiguar el orden, como con los bloques de Hardy y los coches de Yoshigahara.

Las herramientas modernas ayudan de maneras que los jugadores de 1880 habrían envidiado. Un solucionador despejó cada uno de los 2000 tableros de OutBrick antes de publicarlos, así que nadie se encuentra con un intercambio 14–15. Si quieres la parte práctica de esta historia, nuestra guía de cómo resolver rompecabezas de bloques deslizantes expone estrategias y puedes probar un tablero en el navegador.

• Finales de la década de 1870: aparecen bloques deslizantes en marcos en patentes estadounidenses.
• Finales de 1879: se vende el 15 Puzzle; Johnson y Story demuestran que la mitad de las posiciones es irresoluble.
• 1880: la fiebre del 15 Puzzle se extiende por Estados Unidos y Europa.
• 1891: Sam Loyd afirma por primera vez haberlo inventado.
• 1907–1912: se patenta el puzle de Hardy para sacar un bloque.
• 1996: se publica Rush Hour en Estados Unidos.
• 2002–2005: se demuestra que Rush Hour y los puzles deslizantes son PSPACE-completos.