A Hybrid Evolutionary Approach with Adaptive Local Search For Solving Constraint-Based Sudoku Puzzles

Abstract

Sudoku is a constraint satisfaction problem that can be solved using an algorithm that fills a 9×9 grid in which each column, row, and sub-grid has the numbers from 1 to 9 once. As a combinatorial problem, Sudoku can also be modelled as an NP-Hard Optimization Problem. There are several genetic algorithms (GAs) that have been used with considerable success; however, most GAs converge slowly and often converge prematurely to local optimums. This paper describes a new Adaptive Hybrid Local Search Genetic Algorithm (AH-LSGA). An AH-LSGA is a combination of a Genetic Algorithm, Constraint Propagation, and Adaptive Local Search. The adaptive aspect of this algorithm allows a local search to be performed only when stagnation occurs, thereby saving computation time and increasing the speed of convergence. A comparison between the AH-LSGA and the traditional Genetic Algorithm and Local Search Genetic Algorithm will be made based on a number of performance metrics, such as fitness value, execution time, number of generations, and effective generations. The results of the experiment indicate that the proposed hybrid algorithm consolidates the speed of convergence, and reduces execution time, while maintaining a high quality solution.