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 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.