Un Puzle de 2 millones de dólares

Tabla I

Modelado del problema

El primer paso para poder tratar automáticamente este problema consiste en encontrar una manera adecuada de expresarlo. Una forma compacta de representarlo que facilita los cálculos es la matriz. En dicha matriz cada fila representa una pieza del puzle, y para una misma fila las diferentes columnas almacenan el color de cada uno de los lados de la pieza representada. Este enfoque es extensible a piezas con mayor número de lados. Por ejemplo, también es posible cubrir una superficie con un patrón de piezas regulares empleando triángulos equiláteros y hexágonos, que con este esquema se representarían como matrices de tres o seis columnas, respectivamente. Por el contrario, si se considerasen patrones con piezas irregulares como las que se pueden encontrar en La Alhambra de Granada (Figura 6), debería encontrarse otra manera de representar las piezas que se ajustase mejor a esos perfiles.

Para identificar el color de un lado de una pieza, se emplea un número entero que lo representa de manera unívoca en todo el puzle. Por tanto, ese entero aparecerá en la matriz que representa el puzle en tantas ocasiones como veces se emplee ese color en las piezas del puzle. En la Tabla 1 se presenta la codificación de las piezas del ejemplo de puzle, que se muestra en la Figura 3(a) como si estuviesen colocadas en el tablero. Nótese que esta codificación permite representar piezas con bordes complejos, como los que aparecen en los puzles actuales con entrantes y salientes. Simplemente es necesario realizar la transformación de cada borde diferente al código de color correspondiente.

La comprobación del ajuste de las piezas utilizando esta representación se reduce a comparar los valores de las diferentes piezas entre sí. Por ejemplo, para comprobar si el lado izquierdo de la pieza 1 encaja con el lado derecho de la pieza 2 hay que comprobar si coincide el valor de la fila 1 y columna 4 con el valor de la fila 2 y columna 2. De forma similar, cuando se gira una pieza eso se refleja en un desplazamiento circular de los valores dentro de su fila, según el sentido de giro.

Con esta codificación matricial de las piezas y el tablero del puzle se tiene una representación muy eficaz, donde la comprobación de encaje de dos piezas supone la comparación de dos valores numéricos, y el giro de una pieza, un desplazamiento de valores dentro de una misma fila. Todas estas operaciones de tipo matricial son gestionadas de forma eficiente por los ordenadores, y por ello el algoritmo de resolución puede dedicar el tiempo a la búsqueda de la solución.

Algoritmos de resolución

Para plantear la búsqueda de la solución es necesario saber con qué información se cuenta para guiar esa búsqueda. De manera local es posible conocer qué piezas encajan con las que ya están colocadas. Sin embargo, no es posible contar con una información global que indique la idoneidad de una pieza candidata frente a otra, ya que, como se ha comentado anteriormente, no se tiene una imagen que haya que reconstruir con los colores de las piezas.

Para garantizar que una pieza está correctamente colocada en el tablero debe obtenerse la solución completa, ya que hasta que todas las piezas estén colocadas no se puede asegurar que se ha encontrado la solución. Incluso tener más piezas encajadas en el puzle no supone más certeza de tener su solución, simplemente se está más próximo de saber si es solución o no. De hecho, el proceso de solución bien podría llegar a un tablero completo salvo por una pieza, y que la secuencia de colores en la pieza que falta por colocar no coincida con la secuencia de colores del hueco que queda en el puzle. Un ejemplo de esto último se puede ver en la Figura 3(c), donde la pieza que falta contiene los colores del último hueco, pero en orden incorrecto, y por ello no encaja. Como contraste, obsérvese que en la Figura 3(b) una recolocación de las piezas conduce a una situación final distinta, en la que la pieza central sí encaja, y por tanto supone una solución del puzle.