Lloyd, Huw and Amos, Martyn (2020) Solving Sudoku with Ant Colony Optimization. IEEE Transactions on Games, 12 (3). pp. 302-311. ISSN 2475-1502
|
Text
FINAL_VERSION.pdf - Accepted Version Download (895kB) | 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.
| 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: | 31 Jul 2021 13:36 |
| URI: | http://nrl.northumbria.ac.uk/id/eprint/42112 |
Actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
