Solving Nurikabe with Ant Colony Optimization

Amos, Martyn, Crossley, Matthew and Lloyd, Huw (2019) Solving Nurikabe with Ant Colony Optimization. In: GECCO'19 - The Genetic and Evolutionary Computation Conference 2019, 13th - 17th July 2019, Prague, Czech Republic. (In Press)

[img]
Preview
Text (Full text)
Amos et al - Solving Nurikabe with Ant Colony Optimization AAM.pdf - Accepted Version

Download (672kB) | Preview

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 (Paper)
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: 17 Apr 2019 17:15
URI: http://nrl.northumbria.ac.uk/id/eprint/39017

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics


Policies: NRL Policies | NRL University Deposit Policy | NRL Deposit Licence