Sudoku Evolution: Solving Sudoku with AI-related Algorithm

Johannes Jilg, Jenny Carter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC
PublisherIEEE
Pages173-185
Number of pages13
ISBN (Print)9781424444601, 9781424444595
DOIs
Publication statusPublished - 23 Oct 2009
Externally publishedYes
Event1st International IEEE Consumer Electronic Society's Games Innovation Conference - London, United Kingdom
Duration: 25 Aug 200928 Aug 2009
Conference number: 1

Publication series

Name
ISSN (Print)2166-6741
ISSN (Electronic)2166-675X

Conference

Conference1st International IEEE Consumer Electronic Society's Games Innovation Conference
Abbreviated titleICE-GiC 09
CountryUnited Kingdom
CityLondon
Period25/08/0928/08/09

    Fingerprint

Cite this

Jilg, J., & Carter, J. (2009). Sudoku Evolution: Solving Sudoku with AI-related Algorithm. In 2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC (pp. 173-185). [5293614] IEEE. https://doi.org/10.1109/ICEGIC.2009.5293614