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
21Downloads
6 month trend
222Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

View Item View Item