Manchester Metropolitan University logo
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.

    Item Type: Article
    Peer-reviewed: Yes
    Date Deposited: 07 Jan 2020 11:46
    Publisher: Institute of Electrical and Electronics Engineers (IEEE)
    Additional Information: "(c) 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works."
    Divisions: Faculties > Science and Engineering
    Subject terms: Games, Sociology, Statistics, Urban areas, Benchmark testing, Artificial intelligence, Ant Colony Optimization, Sudoku, Puzzle Games
    URI: https://e-space.mmu.ac.uk/id/eprint/624691
    DOI: https://doi.org/10.1109/tg.2019.2942773
    ISSN 2475-1502
    e-ISSN 2475-1510

    Impact and Reach

    Statistics

    DownloadsShow export options
    Activity Overview
    6 month trend
    583Downloads
    6 month trend
    328Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record