21 feb. 2015

PUZLE: algo más complejo de lo que parecía

Cuando un compañero de trabajo vio por primera vez la App PUZLE me preguntó "¿Y cómo sábes que tiene solución?" y le contesté "Porque si uno de 3x3 siempre la tiene, uno de más también", y PUZLE tiene un mínimo de 3x3.

Pero mi afirmación era más una intuición, que una verdad. En un puzle de 3x3 se pueden mover piezas dentro de un bloque de 2x2 de forma que se puede ubicar cualquier pieza en cualquier parte del tablero. Hasta ahí es correcto, y es el movimiento que yo había estado utilizando para resolver puzles, pero en lo que me equivocaba era en que una vez colocada una pieza, el resto no pueden moverse a cualquiera de las otras posiciones restantes: está ligada a una o varias, pero a ciertas otras definitivamente no.

¿Qué provocaba esto? Cuando PUZLE mezclaba las piezas de un nuevo puzle, las ubicaba aleatoriamente. Esto creaba puzles que podían no tener solución.

Probando la App me ocurrió en varias ocasiones que casi terminaba el puzle, pero había dos piezas que estaban la una en el lugar de la otra y no había forma de colocarlas en su sitio sin mover las de alrededor, y de bastante alrededor llegué a mover, pero no lo conseguía. Lo atribuí a que sería un puzle más difícil, para el que, si "siempre había una solución para un puzle de 3x3", siempre tendría que haberla para uno de 5x8, aunque fuese más compleja la solución de las cosas que yo había probado. Pero no había solución.

Para llegar a esa conclusión, decidí buscar si existía alguna demostración matemática de si cualquier disposición de piezas de un puzle se podía resolver.

Buscaba si las personas que estaban delante de PUZLE podrían estar intentando resolver un puzle sin solución, algo que le parecería irritante a un usuario para puzles de 8x13 pero inaceptable para niños con puzles de 3x4.

Encontré una web que hablaba de una demostración de que uno de 3x3 y uno de 4x4 no siempre tenían solución. Al leerlo por encima entendí que, además, dada una disposición de piezas, intercambiando dos, podrían convertirlo en irresoluble, y viceversa.

De hecho contaban la historia de una publicación que ofreció durante años un premio a quien resolviera unos puzles dispuestos de una forma concreta, algo que el autor ya sospechaba que no tenía solución: nunca dio ningún premio.

Además, para saber si tenía o no solución, sólo uno de dos de los algoritmos podía utilizarse sin problemas de rendimiento, lo que hacía sospechar que el cálculo iba a ser costoso y lento.

Finalmente resultó más sencillo. Al iniciar un nuevo puzle se mezclan las piezas haciendo movimientos aleatorios, pero con movimientos válidos de piezas.

Concretamente se realizan tantos movimientos como el número de piezas del puzle multiplicado por cinco.

PUZLE en Google Play