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 (2020) Solving Sudoku with Ant Colony Optimization. IEEE Transactions on Games, 12 (3). pp. 302-311. ISSN 2475-1502

    [img]
    Preview
    Accepted Version
    Available under License In Copyright.

    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
    558Downloads
    6 month trend
    317Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record