Sudoku Evolution: Solving Sudoku with AI-related Algorithm

Sudoku Evolution is a program written for the comparison of metaheuristics. The main aim of the underlying project was to implement a program capable of comparing algorithms related to artificial intelligence. Four population-based approaches were chosen, genetic algorithms (GA), geometric particle swarm optimization (GPSO), Bee Colony Optimization (BCO), artificial immune system (AIS) with somatic hypermutation as well as two algorithms, simulated and quantum annealing (SA & QA), based on probabilistic local search. All of them were implemented based on the work of Alberto Moraglio. He provides a general geometric framework for evolutionary algorithms. Crossover and mutation operators are representation-independent and defined as functions of a metric distance in the search space. Sudoku was used as the testbed for comparison. It is especially interesting as it is a combinatorial and NP-complete problem where valid grids have only one solution. This makes them interesting for optimization algorithms. The algorithms were compared on nine Sudokus with 3 different difficulty ratings. Each of them was executed ten times with preliminary tuned parameters. They were compared based on the average fitness value achieved over all grids and the number of successful solving attempts. SA and GPSO were the best approaches followed by QA and BCO.