An evolutionary approach to sudoku puzzles with filtered mutations

Sudoku puzzles are logical number placement puzzle games. They are classified as combinatorial optimization problems and are NP-complete. To solve problems in this complexity class, metaheuristic approaches, such as genetic algorithms (GAs), are often adopted. However, conventional GAs with random swap mutations suffer from slow convergence, especially in extremely difficult sudoku puzzles, in which only a few given numbers are provided. This paper proposes a GA with sophisticated genetic mutations that mitigate the worsening of fitness values. The comparisons between the conventional method and the proposed method are conducted mainly from the viewpoints of success rate.