An evolutionary-based hyper-heuristic approach for the Jawbreaker puzzle

摘要

In this paper a hyper-heuristic algorithm is designed and developed for its application to the Jawbreaker puzzle. Jawbreaker is an addictive game consisting in a matrix of colored balls, that must be cleared by popping sets of balls of the same color. This puzzle is perfect to be solved by applying hyper-heuristics algorithms, since many different low-level heuristics are available, and they can be applied in a sequential fashion to solve the puzzle. We detail a set of low-level heuristics and a global search procedure (evolutionary algorithm) that conforms to a robust hyper-heuristic, able to solve very difficult instances of the Jawbreaker puzzle. We test the proposed hyper-heuristic approach in Jawbreaker puzzles of different size and difficulty, with excellent results.