Solving Nurikabe with Ant Colony Optimization

Martyn Amos, Matthew Crossley, Huw Lloyd

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)
116 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationGECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
Subtitle of host publicationJuly 13–17, 2019, Prague, Czech Republic
Place of PublicationNew York, NY, USA
Number of pages2
ISBN (Electronic)9781450361118, 9781450367486
Publication statusPublished - 13 Jul 2019
EventThe Genetic and Evolutionary Computation Conference 2019 - Prague Conference Center, Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019


ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO'19
Country/TerritoryCzech Republic
Internet address


Dive into the research topics of 'Solving Nurikabe with Ant Colony Optimization'. Together they form a unique fingerprint.

Cite this