Un Puzle de 2 millones de dólares

Descargar este artículo en formato PDF

Palabras clave: Puzles, GRID, Problemas NP-Completo.

Key words:Puzzles, GRID, NPComplete Problems.

Resumen: Este artículo estudia un tipo de puzles matemáticos, cuyo exponente principal es el puzle comercial denominado Eternity II. Se analiza la elevada complejidad de este tipo de puzles, caracterizándola como función del número de piezas y colores diferentes. Para confirmar estos hallazgos teóricos se ha desarrollado una herramienta informática capaz de generar automáticamente este tipo de puzles y resolverlos utilizando varios equipos en un entorno grid. Los resultados prácticos coinciden con los deducidos teóricamente, mostrando que existe un rango de número de colores, dependiente del tamaño del puzle, donde las estrategias de búsqueda requieren más tiempo para alcanzar una solución.

Abstract: This paper studies a type of edgematching puzzle, whose main exponent is the commercial puzzle called Eternity II. The high complexity of this type of puzzles has been discussed, as well as characterized as a function of the number of pieces and the amount of different colors. In order to confirm these theoretical findings, a software tool has been developed for generating and solving this kind of puzzles using several computers in a grid computing environment. The practical results agree with those deduced from theor y, showing that there is a range in the number of colors, which depends on the puzzle size, where the search strategies require more time for achieving a solution.

Autores: Alberto Martín Goñi, Jesús María Latorre Canteli, Eugenio Fco. Sánchez Úbeda