Una de las posiciones iniciales más difíciles de Rush Hour.
Requiere 51 movimientos
Durante varias semanas Michael Fogleman ha estado contando en su Twitter cómo iba creando un programa para resolver los puzles de Rush Hour («Hora punta»).
Este puzle que inventó Nob Yoshigahara en los años 70 es muy popular como juego infantil por su simplicidad, pero todo un reto también para los mayores. Consiste en una retícula de 6×6 sobre la que hay unos cuantos coches y camiones de 2×1 y 3×1 y una única salida. Se copia la posición inicial de una de las tarjetas de la baraja y el objetivo es mover los coches, sólo «adelante-atrás» hasta que el coche rojo pueda salir.
Es un juego de habilidades lógicas que estimula mucho el cacumen. Como además incluye muchas tarjetas (40) resulta bastante entretenido, y quien más quien menos acaba echándole un ratillo. Incluso existen segundas partes de Rush Hour con más tarjetas y alguna versión «clonada» con piezas extra en forma de pared fija para complicar el asunto.
Lo más interesante del artículo no es tanto ver cómo el algoritmo resuelve los problemas sino que puede usarse para generar configuraciones iniciales «interesantes» o «difíciles». Por «interesantes» se puede definir aquellas que requieren un mayor número de movimientos para resolverse y sin pasos demasiado obvios.
Análisis gráfico de cómo desde unas posiciones de los coches en el tablero se puede llegar a otras y el camino de la solución óptima (azul) hasta llegar a la salida (verde, abajo)
Como es fácil imaginar las combinaciones de movimientos tras movimientos crecen y crecen exponencialmente. Para el tablero original hay unos 287.000 millones de posiciones iniciales distintas. Fogleman utilizó la técnica de los bitboard para representar cada estado y un poco de fuerza bruta para organizar todos los movimientos, agruparlos en clústeres y ver luego si se podía acceder a la solución desde cada clúster (si no, era imposible), anotando el número de movimientos necesarios al pasar de una posición a otra.
Técnicamente pasó de un código en Go a otro en C++ para arañar toda la velocidad posible. Todas las posiciones del tablero de 6×6 se pueden resolver en unas 3 horas en un iMac, pero para la versión que añade un bloque de 1×1 tuvo que contratar un EC2 con 72 cores durante 14 horas (que con algunas mejoras se quedan en la mitad).
En Github está todo el código de Rush Hour del autor, además de los ficheros de varios MB con millones de posiciones «interesantes» (muchos movimientos para resolverlas) que son 1,5 millones más o menos. Bastante más que las tarjetas originales del juego, así que quien se haya quedado con ganas de más este verano ya sabe…
