Solving Sudoku With Ant Colony Optimization

摘要

In this article, we present a new algorithm for the well-known and computationally challenging Sudoku puzzle game. Our ant-colony-optimization-based method significantly outperforms 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 antistagnation 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.