Un solver para el juego "unblockme"

Una noche muy lejana, mi manager se encontraba frente a la TV esperando que terminaran los comerciales para continuar perdiendo el tiempo con un programa no crocante. Dicho programa, cuyo nombre es irrelevante y en el que una vieja fashion y escuálida tras pronunciar tres expresiones para nada especiales da la orden a equipos que representan regiones de nuestro país para que inicien la competencia, ha venido sin duda alguna llenándome de escozor por muchos años de manera continua.

En esa oportunidad le dije a mi manager que además de realizar su tradicional y religioso crucigrama y Sudoku del periódico, podía intentar en su teléfono celular juegos que no sólo la entretendrían y le ayudarían a matar el tiempo, sino que también le permitiría ejercitar su cerebro de una manera seguramente más sana que ver a seres humanos discutir porque alguien se comió el arroz ajeno. 

El juego que le compartí a mi representante y que hasta el momento después de algo más de un año aún juega casi todos los días, se trata de unblockme, una aplicación móvil donde el reto en resumen es mover una serie de bloques de madera en direccón horizontal y vertical para permitirle a un bloque en particular llegar a su destino.

Sin embargo, el propósito de este post no es guarusear al programa de TV, ni compartirles el agrado y empatía que mi mamá muestra por ese juego. Por el contrario, la verdadera motivación apenas empieza a ser revelada, se trata de algo en lo que trabajé un día que estaba en casa y en los que estando de vacaciones, mi mente sediente de ciencia necesitaba ocuparse en algo. Salí del cuarto de la ciencia, en busca de un vaso con agua en la nevera y de regreso cuando vi a mi manager jugándolo, tenía entonces un objetivo de ciencia que calmaría mi necesidad. Me había dado cuenta que podía ser interesante utilizar inteligencia artificial para hacer un solver de dicho puzzle, me imaginé a priori que podría necesitar pensar en heurísticas y estrategias complejas. Sin embargo, para mi decepción finalmente sólo bastó utilizar algoritmos tradicionales de búsqueda en un espacio de búsqueda finito. Prefiero pensar que quizás lo único que necesitaba ese día era sentarme en el PC y hacer un poco de ciencia crocante.

De una me senté frente al PC, modelé el problema, implementé un par de algoritmos sencillos de búsqueda ---realmente más por comparación que por otra cosa, teniendo a la búsqueda BFS (Breadth First Search) como la más óptima para este problema--- y desarrollé mecanismos para interactuar con las soluciones obtenidas por el solver.

El solver implementado tiene los siguientes features:

• Permite aplicar los algoritmos BFS o DFS para obtener la solución.
• Visualización paso a paso de la solución obtenida. Permitiendo avanzar y retroceder con las flechas de de derecha e izquierda del teclado respectivamente.
• Visualización automática de la solución obtenida, ideal para aquellas soluciones que tomen una enorme cantidad de acciones como las que puede encontrarse con DFS.
• Lectura de cualquier acertijo a través de un archivo de texto con formato definido. 

Aquí les comparto un video del solver tras resolver con el número óptimo de movimientos el acertijo sugerido por la aplicación unblockme que está presentado en la figura anterior.

Finalmente, les dejo el enlace del repositorio bien documentado para que lo puedan clonar y echarle un vistazo si les interesa.

https://github.com/jtuburon/unblockme