Solving Sudoku with Ant Colony Optimization

Lloyd, Huw and Amos, Martyn (2020) Solving Sudoku with Ant Colony Optimization. IEEE Transactions on Games, 12 (3). pp. 302-311. ISSN 2475-1502

[img]
Preview
Text
FINAL_VERSION.pdf - Accepted Version

Download (895kB) | Preview
Official URL: https://doi.org/10.1109/tg.2019.2942773

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.

Item Type: Article
Uncontrolled Keywords: Ant Colony Optimzation, Sudoku, Puzzle Games
Subjects: G400 Computer Science
G500 Information Systems
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Elena Carlaw
Date Deposited: 18 Feb 2020 11:19
Last Modified: 22 Sep 2020 10:15
URI: http://nrl.northumbria.ac.uk/id/eprint/42112

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics