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
|
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: | 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 |
| URI: | http://nrl.northumbria.ac.uk/id/eprint/39017 |
Actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
