e-space
Manchester Metropolitan University's Research Repository

    Solving Nurikabe with Ant Colony Optimization

    Amos, Martyn, Crossley, Matthew ORCID logoORCID: https://orcid.org/0000-0001-5965-8147 and Lloyd, Huw ORCID logoORCID: https://orcid.org/0000-0001-6537-4036 (2019) Solving Nurikabe with Ant Colony Optimization. In: Genetic and Evolutionary Computation Conference (GECCO) 2019, 13 July 2019 - 17 July 2019, Prague, Czech Republic.

    [img]
    Preview
    Accepted Version
    Download (672kB) | Preview

    Abstract

    We present the first nature-inspired algorithm for the NP-complete Nurikabe pencil puzzle. Our method, based on Ant Colony Optimization (ACO), offers competitive performance with a direct logic-based solver, with improved run-time performance on smaller instances, but poorer performance on large instances. Importantly, our algorithm is “problem agnostic", and requires no heuristic information. This suggests the possibility of a generic ACO-based framework for the efficient solution of a wide range of similar logic puzzles and games. We further suggest that Nurikabe may provide a challenging benchmark for nature-inspired optimization.

    Impact and Reach

    Statistics

    Activity Overview
    6 month trend
    208Downloads
    6 month trend
    302Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record