e-space
Manchester Metropolitan University's Research Repository

Solving Sudoku with Ant Colony Optimization

Lloyd, Huw ORCID logoORCID: https://orcid.org/0000-0001-6537-4036 and Amos, Martyn (2019) Solving Sudoku with Ant Colony Optimization. IEEE Transactions on Games. p. 1. ISSN 2475-1502

[img]
Preview
Accepted Version
Download (1MB) | Preview

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.

Impact and Reach

Statistics

Activity Overview
6 month trend
184Downloads
6 month trend
222Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

View Item View Item