e-space
Manchester Metropolitan University's Research Repository

Solving Nurikabe with Ant Colony Optimization

Amos, Martyn and Crossley, Matthew and Lloyd, Huw (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]
Restricted to Repository staff only

Download (672kB)

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

Downloads
Activity Overview
1Download
126Hits

Additional statistics for this dataset are available via IRStats2.

Actions (login required)

Edit Item Edit Item