Solving Sudoku with Ant Colony Optimization

Huw Lloyd, Martyn Amos

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
147 Downloads (Pure)

Abstract

In this paper we present a new algorithm for the well-known and computationally-challenging Sudoku puzzle game. Our Ant Colony Optimization-based method significantly out-performs the state-of-the-art algorithm on the hardest, large instances of Sudoku. We provide evidence that – compared to traditional backtracking methods – our algorithm offers a much more efficient search of the solution space, and demonstrate the utility of a novel anti-stagnation operator. This work lays the foundation for future work on a general-purpose puzzle solver, and establishes Japanese pencil puzzles as a suitable platform for benchmarking a wide range of algorithms.
Original languageEnglish
Pages (from-to)302-311
Number of pages10
JournalIEEE Transactions on Games
Volume12
Issue number3
Early online date20 Sep 2019
DOIs
Publication statusPublished - 1 Sep 2020

Fingerprint

Dive into the research topics of 'Solving Sudoku with Ant Colony Optimization'. Together they form a unique fingerprint.

Cite this