Un Puzle de 2 millones de dólares

Figura II

Figura III

Figura IV

Figura V

En realidad el puzle Eternity II es una variante del juego lúdico de ordenador denominado Tetravex, incluido en el entorno de escritorio Gnome de las distribuciones GNU/Linux y Unix (ver www.gnome.org). La diferencia fundamental reside en que el primero ha sido especialmente diseñado para que sea un problema intratable, incluso con la ayuda de un ordenador. Según los diseñadores del mismo, ni el ordenador actual más potente podría encontrar una solución en todo el tiempo estimado de duración del universo.

Dificultad del problema

Resolver un puzle Eternity II de 4 colores y 9 piezas como el de la Figura 3 no debería requerir, en el peor de los casos, más de un minuto a una persona y unos pocos milisegundos a un ordenador. Sin embargo, 29 meses después de su lanzamiento, en diciembre de 2009, no se había encontrado una solución al puzle de 256 piezas y 23 colores, a pesar de tener asociado un premio de dos millones de dólares y de que se haya ido publicando la posición exacta de algunas piezas para reducir la complejidad del mismo. Esta búsqueda ha sido infructuosa debido a que la posición exacta de cada pieza en el tablero no se puede asegurar hasta tener completamente resuelto el puzle, y a medida que aumenta el tamaño del puzle existen muchas más posibilidades de tener que deshacer todo el trabajo realizado colocando piezas al llegar a un punto donde es imposible seguir. En la Figura 3 se muestra una posible solución, así como una situación en la que al intentar colocar la última pieza se descubre que no es posible completar el puzle correctamente.

Una manera sencilla de cuantificar cómo aumenta la difi cultad del puzle con el número de piezas consiste en calcular el porcentaje de piezas del interior con respecto a las del borde y esquinas (es decir, comparar el perímetro del tablero con su superfi cie).

Según la Figura 4 se puede afirmar que los puzles de menos de 49 piezas tienen más piezas en el contorno que en el interior. A partir de ese tamaño empieza a haber más piezas en el interior que en el contorno. Dado que las piezas del contorno tienen su orientación en la solución final totalmente fijada por el color negro del borde, se puede afirmar que cuantas más piezas haya que colocar en el centro más complejo será.

Por otro lado, el número de colores diferentes en el puzle está directamente relacionado con la difi cultad del mismo. Existen dos situaciones extremas donde el puzle no tiene ninguna difi cultad. Si únicamente hay dos colores (el del borde exterior y el del interior), entonces simplemente hay que distinguir entre las piezas de las esquinas, laterales y del centro para poder colocarlas sin mayor complicación ya que su posición es indiferente. El caso contrario sería cuando en el puzle aparece el número máximo posible de colores diferentes y también sería muy sencillo de resolver ya que colocada una de las esquinas, la posición del resto de piezas estaría determinada de forma unívoca (ver Figura 2d). Para un puzle de N piezas, el número máximo de colores diferentes es (ver [Martín2009]). Así, un puzle de 9 piezas sería trivial si consta de 2 ó 13 colores. Para un número de colores intermedio se pueden encontrar puzles de difi cultad variable.

Realmente la difi cultad del puzle depende de manera conjunta del número de piezas, del número de colores diferentes y de la distribución de los mismos en las piezas. En la Figura 5 se muestra una estimación de esta dificultad (obtenida a partir de varias simulaciones con diferente distribución de colores en las piezas), para cuatro tamaños de puzle y en función del número de colores [Martín2009]. Como se puede apreciar, el máximo de la curva se desplaza hacia la derecha y aumenta su valor a medida que crece el número de piezas del puzle.