Un Puzle de 2 millones de dólares

Figura VI

Un puzle matemático como el Eternity II es extremadamente difícil de resolver. El número de piezas y de colores, así como su distribución espacial ha sido elegido cuidadosamente para que su solución no pueda ser encontrada en un tiempo razonable, ni utilizando la potencia de cálculo de los ordenadores actuales. La razón fundamental para ello es que no es posible diseñar un algoritmo capaz de encontrar la solución en un tiempo de ejecución que crezca de forma polinómica con el tamaño del problema. Si el tamaño es sufi cientemente grande, el tiempo de ejecución del algoritmo será inmenso. Más formalmente, en el campo de la complejidad computacional, a un problema de estas características se le denomina NP-Completo (del inglés Non-Polynomial [Garey1979]).

Existen muchos problemas NPCompletos, como el aparentemente sencillo problema de determinar si en un conjunto de M números enteros (positivos y negativos) existe un subconjunto no vacío de suma nula. Aunque es fácil verifi car si una posible respuesta es correcta, el algoritmo de búsqueda requiere explorar todos los 2^M-1 subconjuntos posibles hasta encontrar uno que cumpla la condición. Esta dependencia exponencial con el tamaño del problema hace que el problema sea intratable en la práctica, incluso con valores de M pequeños.

El crecimiento exponencial de la complejidad escapa fácilmente a la intuición, por lo que conviene aclarar la magnitud del problema con cifras concretas. Según una conocida leyenda, si en cada una de las 64 casillas de un tablero de ajedrez se coloca el doble de los granos de arroz que en la casilla anterior (comenzando con un grano en la primera casilla), en el tablero habría un total de granos de arroz. Exactamente 18.446.744.073.709.551.615 granos de arroz, el número más grande que se puede almacenar en un entero sin signo con una representación de 64 bits de los nuevos ordenadores personales. Suponiendo que un grano de arroz pesa 20 miligramos, (una tonelada tendrá 50 millones de granos) y teniendo en cuenta que la producción mundial de arroz en 2008 fue aproximadamente de 700 millones de toneladas, en el tablero de ajedrez tendría que estar todo el arroz producido en la Tierra durante los próximos 527 años, suponiendo una producción anual constante igual a la de 2008.

Al igual que en el caso del tablero de ajedrez, una excesiva ingenuidad puede llevar a infravalorar el crecimiento de la complejidad de un puzle Eternity II con el tamaño del mismo, albergando expectativas de resolución cuestionables. En [Takenaga2006] se demuestra teóricamente que, en general, la búsqueda de una solución de un puzle matemático como el Eternity II también es un problema NP-Completo, es decir, irresoluble a día de hoy.

La dificultad de este tipo de puzles radica en el tamaño del espacio de búsqueda y en el número de soluciones posibles. Cuando el espacio de búsqueda es inmenso y el número de soluciones posibles es muy pequeño, como en el caso del Eternity II, se trata de encontrar una aguja muy pequeña en un pajar muy grande. Si se intentara resolver dicho puzle simplemente colocando las piezas totalmente al azar y comprobando a continuación si es la solución válida o no, el espacio de búsqueda a explorar sería de 4^NN!, que para N=256 resulta en un tamaño aproximado de 210⁶⁶⁰, un número astronómico de combinaciones. Encontrar una solución con este método de búsqueda de fuerza bruta sería al menos tan difícil como encontrar un átomo concreto en todo el universo observable.

Si se utiliza una estrategia de búsqueda un poco más inteligente, en la que las piezas se clasifican previamente en sus tres tipos básicos (esquinas, bordes y centro) y luego se colocan al azar en la zona correspondiente teniendo en cuenta el color del borde para evitar explorar soluciones que son infactibles a priori, el espacio de búsqueda se reduce significativamente, pero sigue siendo inmenso, del orden de 10⁵⁶⁰ para 256 piezas (ver [Martín2009], [Owen2007]).

Los algoritmos sofisticados especialmente diseñados para encontrar una solución a este problema se basan en ir colocando piezas de forma lógica y ordenada hasta llegar al final o encontrar una infactibilidad, en cuyo caso es necesario deshacer el camino recorrido y emprender uno nuevo. Determinar el espacio de búsqueda de estos algoritmos no es sencillo, pero según [Owen2007] podría ser del orden de 10⁴⁷ para el Eternity II.