Article Preview
TopIntroduction
Puzzles are among the most popular ways in which to measure computers’ abilities to tackle problems that require intelligence. They have well-defined rules and a performance that can be objectively quantified via numeric scores or win-lose outcomes.
The present research is aimed at solving the Casse-tête problem (Talbi, 2009), which is a one-player board puzzle that consists of a two-dimensional grid with a size of covered with 
tokens (see Figure 1a). The idea of this puzzle is to delete 
tokens from the grid, with the number of remaining tokens being even in each row and column of the grid (see Figure 1b). The configuration in Figure 1(c) is considered an incorrect solution because there is an odd number of tokens in each of row 2, row 3, column 2, and column 4. The search space size of this problem is given by:
which is exponential in size. As far as the authors’ are concerned, this problem has not been approached in the previous literature.
Figure 1. (a) Grid with 
covered by 16 tokens (b) Example of the correct solution of the problem (c) Example of an incorrect solution of the problem, where n=4 and m=6
Figure 2. Example of matrix encoding for the board configuration in Figure 1(b)
A genetic algorithm (GA) (Holland, 1992) is a search and optimization metaheuristic inspired by the Darwinian principle of evolution through genetic selection and variation. A GA uses a decidedly abstract version of development operations to include solutions for a given problem (McCall, 2005). GAs have shown good performance in various NP-hard problems (Katoch et al., 2020), including puzzles that are similar in nature to Casse-tête, such as the 
-queens and 
-puzzle.
This study involved designing a GA to solve the Casse-tête problem. Despite the abundance of available crossover and mutation operators, no operators were found that were suitable for this problem. Thus, the work involved proposing two new crossover methods to fit the problem: binary partially mapped crossover (BPMX) and binary modified order crossover (BMOC). Moreover, two mutation methods (binary swap [BSwap] and binary inversion [BInversion]) were used to commensurate with the chromosome representation. The fitness evaluation acted as a cost function, penalizing the individual with each row/column with an odd number of tokens. Additionally, the study involved evaluating the proposed model against a simulated annealing (SA)-based solution to the problem.
This article is organized as follows. First, it introduces the background of the problem. Second, a review of similar board puzzles, such as the 
-queens problem and the 
-puzzle problem, is presented. Third, the methodology for solving the Casse-tête problem is defined based on the requirements and algorithm design. Fourth, the dataset and experimental methodology are explained. Fifth, the experimental results are reported and discussed before conclusions are drawn.