Experimental Programming of Genetic Algorithms for the “Casse-Tête” Problem

Sarab Almuhaideb, Shahad Alohaydib, Dana Aldossari, Ghaida Alfarraj, Shahad Musaibeeh, Atheer Alrosayes, Afnan Abouelwafa

OAI: oai:igi-global.com:292513 • DOI: 10.4018/IJAMC.292513

The Casse-tête board puzzle consists of an n×n grid covered with n^2 tokens. m<n^2 tokens are deleted from the grid so that each row and column of the grid contains an even number of remaining tokens. The size of the search space is exponential. This study used a genetic algorithm (GA) to design and implement solutions for the board puzzle. The chromosome representation is a matrix of binary permutations. Variants for two crossover operators and two mutation operators were presented. The study experimented with and compared four possible operator combinations. Additionally, it compared GA and simulated annealing (SA)-based solutions, finding a 100% success rate (SR) for both. However, the GA-based model was more effective in solving larger instances of the puzzle than the SA-based model. The GA-based model was found to be considerably more efficient than the SA-based model when measured by the number of fitness function evaluations (FEs). The Wilcoxon signed-rank test confirms a significant difference among FEs in the two models (p=0.038).

Algorithms Computer Science and Information Technology Artificial Intelligence