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)

…