Solving Sudoku with Ant Colony Optimization

Huw Lloyd, Martyn Amos

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)
174 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 Sept 2019
DOIs
Publication statusPublished - 1 Sept 2020

Keywords

  • Ant colony optimzation
  • Sudoku
  • puzzle games

Fingerprint

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

Cite this