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 language | English |
---|---|
Pages (from-to) | 302-311 |
Number of pages | 10 |
Journal | IEEE Transactions on Games |
Volume | 12 |
Issue number | 3 |
Early online date | 20 Sept 2019 |
DOIs | |
Publication status | Published - 1 Sept 2020 |
Keywords
- Ant colony optimzation
- Sudoku
- puzzle games