Solving Nurikabe with Ant Colony Optimization

Amos, Martyn, Crossley, Matthew and Lloyd, Huw (2019) Solving Nurikabe with Ant Colony Optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '19): July 13–17, 2019, Prague, Czech Republic. GECCO (19). ACM, New York, NY, USA, pp. 129-130. ISBN 9781450361118

Amos et al - Solving Nurikabe with Ant Colony Optimization AAM.pdf - Accepted Version

Download (672kB) | Preview
Official URL:


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: Book Section
Uncontrolled Keywords: Puzzle game, NP-complete, Combinatorial optimization, Ant colony optimization
Subjects: G400 Computer Science
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Paul Burns
Date Deposited: 17 Apr 2019 17:02
Last Modified: 01 Aug 2021 11:08

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics