Solving Nurikabe with Ant Colony Optimization

Amos, Martyn, Crossley, Matthew ORCID: https://orcid.org/0000-0001-5965-8147 and Lloyd, Huw ORCID: 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.

Preview

Accepted Version
Available under License In Copyright.
Download (672kB) | Preview

Official URL: https://dl.acm.org/doi/10.1145/3319619.3338470

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.

Item Type:	Conference or Workshop Item (Poster)
Published Proceedings:	GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion
Peer-reviewed:	Yes
Date Deposited:	29 Jul 2019 11:16
Publisher:	Association for Computing Machinery (ACM)
Divisions:	Faculties > Science and Engineering
Subject terms:	Puzzle game, NP-complete, Combinatorial optimization, Ant colony optimization
URI:	https://e-space.mmu.ac.uk/id/eprint/622803
DOI:	https://doi.org/10.1145/3319619.3338470

Impact and Reach

Statistics

DownloadsShow export options

Activity Overview

6 month trend

350Downloads

6 month trend

337Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Repository staff only

Edit record