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 theory, 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.
Palabras Clave: Puzles, GRID, Problemas NP-Completo
Referencia DOI: ANALES
Publicado en papel: Agosto 2010.
A. Martín, J.M. Latorre, E.F. Sánchez-Úbeda. Un puzle de 2 millones de dólares. Anales de Mecánica y Electricidad. Vol. LXXXVII, nº. IV, pp. 28 - 35 Agosto 2010.