A Nested Two-steps Evolutionary Algorithm for the Light-up Puzzle

Article type: Research Article

Authors: Salcedo-Sanz, S.¹ | Carro-Calvo, L. | Ortiz-García, E. G. | Pérez-Bellido, Á. M. | Portilla-Figueras, J. A.

Affiliations: Madrid, Spain

Note: [1] Department of Signal Theory and Communications, Universidad de Alcalá. 28871 Alcalá de Henares, email: sancho.salcedo@uah.es

Abstract: The Light-up puzzle is a logic grid-based puzzle, really popular as pastime on the Internet. In this article we present a nested two-steps evolutionary algorithm to solve it. The proposed approach exploits the constraints structure of the puzzle by running two different evolutionary algorithms in a nested fashion: the first evolutionary algorithm looks for feasible individuals in terms of a puzzle constraint, and only these feasible individuals are passed to a second evolutionary algorithm which completes the puzzle. The proposed algorithm is enhanced by introducing a preprocessing step based on constraint propagation, which improves the performance particularly in the rather large Light-up instances. The proposed approach is fully described in the article, its main properties are detailed, and its performance is shown by Light-up instances of different size, obtained from popular web pages devoted to this puzzle.

DOI: 10.3233/ICG-2009-32302

Journal: ICGA Journal, vol. 32, no. 3, pp. 131-139, 2009