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.

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

Particle swarm optimization (PSO)
Immune system
Testbeds
Evolutionary algorithms
Artificial intelligence
Mathematical operators
Computational complexity
Genetic algorithms
Annealing

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
Jilg, Johannes ; Carter, Jenny. / Sudoku Evolution : Solving Sudoku with AI-related Algorithm. 2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC. IEEE, 2009. pp. 173-185
@inproceedings{0d766da01583415d8486481fc689177e,
title = "Sudoku Evolution: Solving Sudoku with AI-related Algorithm",
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.",
keywords = "Algorithms, Artificial immune system, Artificial intelligence, Bee colony optimization, Geometric particle swarm optimization, Quantum annealing, Sudoku",
author = "Johannes Jilg and Jenny Carter",
year = "2009",
month = "10",
day = "23",
doi = "10.1109/ICEGIC.2009.5293614",
language = "English",
isbn = "9781424444601",
publisher = "IEEE",
pages = "173--185",
booktitle = "2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC",

}

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., 5293614, IEEE, pp. 173-185, 1st International IEEE Consumer Electronic Society's Games Innovation Conference, London, United Kingdom, 25/08/09. https://doi.org/10.1109/ICEGIC.2009.5293614

Sudoku Evolution : Solving Sudoku with AI-related Algorithm. / Jilg, Johannes; Carter, Jenny.

2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC. IEEE, 2009. p. 173-185 5293614.

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

TY - GEN

T1 - Sudoku Evolution

T2 - Solving Sudoku with AI-related Algorithm

AU - Jilg, Johannes

AU - Carter, Jenny

PY - 2009/10/23

Y1 - 2009/10/23

N2 - 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.

AB - 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.

KW - Algorithms

KW - Artificial immune system

KW - Artificial intelligence

KW - Bee colony optimization

KW - Geometric particle swarm optimization

KW - Quantum annealing

KW - Sudoku

UR - http://www.scopus.com/inward/record.url?scp=74349119413&partnerID=8YFLogxK

U2 - 10.1109/ICEGIC.2009.5293614

DO - 10.1109/ICEGIC.2009.5293614

M3 - Conference contribution

SN - 9781424444601

SN - 9781424444595

SP - 173

EP - 185

BT - 2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC

PB - IEEE

ER -

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