A Genetic Algorithm for Solving Beehive Hidato Puzzles

Título: A Genetic Algorithm for Solving Beehive Hidato Puzzles

Autores: Silva, Matheus; Magalhães, Camila

Beehive Hidato puzzles are logic games, similar to Sudoku, in which the grid cells are hexagons. Some hexagons are prefilled with given numbers, and the objective of the game is to find a path of natural numbers, from 1 to the grid size n, in such a way that consecutive numbers stay connected by any hexagon side. Although the rules of the game are simple, find the solution for this problem can be quite challenging. In this work, we designed and implemented a genetic algorithm (GA) to solve Beehive Hidato problems. The proposed GA uses commonly used genetic operators and the RTS niching technique to preserve population diversity. A new strategy based on gene convergence rate is also implemented and tested. The proposed algorithm was evaluated in 21 instances of Beehive Hidato with different sizes and complexities. The results show that GAs are promising tools for solving Beehive Hidato problems.

Genetic Algorithm;Hidato Puzzles;Niching

Páginas: 11

Código DOI: 10.21528/CBIC2017-114

Artigo em pdf: cbic-paper-114.pdf

Arquivo BibTeX: cbic-paper-114.bib