Un Puzle de 2 millones de dólares

Figura VII

De esta manera, para garantizar que la decisión tomada en cada paso es correcta, debe comprobarse si el espacio de búsqueda que esas piezas determinan contiene la solución. Como se ha visto anteriormente, el número total de combinaciones de piezas (o posibles soluciones a comprobar) crece de forma exponencial con el número de piezas y no es posible explorarlo de forma exhaustiva en un tiempo razonable. En consecuencia, es necesario recurrir a criterios heurísticos que sirvan de guía aproximada, cuyas decisiones son posteriormente comprobadas durante el proceso de búsqueda. El resultado de estas comprobaciones puede indicar que hasta el momento se ha podido avanzar sin problemas, o que con las piezas colocadas hasta ese momento no se puede encontrar una pieza libre que encaje. En este último caso, alguna de las decisiones anteriormente tomadas no es correcta, y por tanto hay que revisarlas y escoger una alternativa distinta.

En las pruebas que se van a presentar en este artículo se ha empleado como criterio heurístico el colocar en cada momento una pieza en la posición en la que menos piezas encajen. Como en esa posición hay menos alternativas, cada una de ellas cuenta con mayores probabilidades de pertenecer a la solución. En cierto sentido, con esto se deja el camino más abierto para las futuras decisiones y es más probable que por ese camino se encuentre una solución.

Considerando todo lo anterior, el algoritmo de búsqueda de la solución que se ha diseñado incorpora los siguientes factores:

• En primer lugar, se utiliza un algoritmo voraz, es decir, al escoger qué pieza colocar y en qué posición, se toma una decisión óptima localmente. Es preciso escoger las piezas que encajen con las ya colocadas, evaluando la bondad de las posibles alternativas empleando el heurístico mencionado anteriormente: se selecciona la posición en la que menos piezas encajan, y por tanto, la posición en la que una pieza colocada tiene más posibilidades de ser la correcta.
• En segundo lugar, como puede ocurrir que alguna de las decisiones tomadas previamente sea incorrecta, el algoritmo debe permitir la vuelta atrás para considerar otras alternativas diferentes a las ya consideradas.

En la Figura 7 se muestra un ejemplo de este proceso de búsqueda para el puzle de la Figura 3(a), indicado por las flechas (de arriba a abajo y de izquierda a derecha). En el primer tablero se coloca la primera pieza, en la esquina superior izquierda. Posteriormente se escoge colocar la pieza que está debajo de la anterior, descendiendo por la rama de la izquierda en el diagrama que representa el proceso de búsqueda. En ese momento existen otras alternativas que se han señalado con una línea de trazos que se extiende hacia la derecha. Al seguir por la rama de la izquierda y colocar la tercera pieza del puzle a la derecha de la pieza de esquina, se llega a una vía muerta en que ya no es posible colocar la pieza central. Por ello, se deben reconsiderar las decisiones tomadas anteriormente. En concreto, se toma una alternativa a la última pieza que se decidió poner colocando, a la derecha de la que ocupa la esquina, otra posible como tercera pieza. Siguiendo este proceso de búsqueda por ese camino, se llega finalmente a una solución del puzle.