Can Simple GAs Solve Beehive Hidato Logic Puzzles? The Influence of Diversity Preservation and Genetic Operators

摘要

Beehive Hidato is a fill-in logic puzzle, similar to Sudoku, with hexagonal grid cells. Some hexagons are pre-filled with fixed numbers, while the remaining has to be filled by the player such that consecutive numbers stay connected to form a “path”, from 1 to n, the largest number in the grid. Each Hidato problem has only one correct answer and, despite its simple rules, finding the solution for these problems can be quite challenging. In this work, we analyzed the importance of diversity preservation, as well as, the influence of commonly used permutation genetic operators in a simple genetic algorithm (GA) for solving Beehive Hidato problems. The algorithm was evaluated on 21 instances of Beehive Hidato problems, with different complexity levels, divided into two classes according to its size. We found PMX crossover and swap mutation as the best operators among the ones tested. Apart from that, the results indicate that the use of a diversity preservation technique has a significant role in GA performance, mainly for solving larger problem instances.