e-space
Manchester Metropolitan University's Research Repository

Solving Sudoku with Ant Colony Optimization

Lloyd, Huw and Amos, Martyn (2019) Solving Sudoku with Ant Colony Optimization. IEEE Transactions on Games. p. 1. ISSN 2475-1502

[img]
Preview

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

Downloads
Activity Overview
70Downloads
99Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

Edit Item Edit Item