Solving Nurikabe with Ant Colony Optimization

Martyn Amos, Matthew Crossley, Huw Lloyd

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

1 Citation (Scopus)
58 Downloads (Pure)

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.
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
PublisherACM
Pages129-130
Number of pages2
ISBN (Electronic)9781450361118, 9781450367486
DOIs
Publication statusPublished - 13 Jul 2019
EventThe Genetic and Evolutionary Computation Conference 2019 - Prague Conference Center, Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019
https://gecco-2019.sigevo.org/index.html/HomePage

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO'19
CountryCzech Republic
CityPrague
Period13/07/1917/07/19
Internet address

Fingerprint

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

Cite this