Paper Info
Title
A Nested Two-steps Evolutionary Algorithm for the Light-up Puzzle
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 algorthms in a nested fashion: the first evolutionary algorthm 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.
Year
DOI
Venue
2009
10.3233/ICG-2009-32302
ICGA JOURNAL
Keywords
Field
DocType
evolutionary algorithm
Interactive evolutionary computation,Local consistency,Evolutionary algorithm,Human-based evolutionary computation,Web page,Computer science,Artificial intelligence,Cultural algorithm,Evolutionary programming,Grid
Journal
Volume
Issue
ISSN
32
3
1389-6911
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Sancho Salcedo-Sanz158071.21
Leopoldo Carro-Calvo2797.45
Emilio G. Ortíz-García3406.08
Ángel M. Pérez-Bellido413011.71
José Antonio Portilla-Figueras5488.53