Solving Nurikabe with Ant Colony Optimization

Martyn Amos; Matthew Crossley; Huw Lloyd

doi:10.1145/3319619.3338470

Solving Nurikabe with Ant Colony Optimization

Martyn Amos, Matthew Crossley, Huw Lloyd

Computer Information Sciences Department

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

133 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 language	English
Title of host publication	GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
Subtitle of host publication	July 13–17, 2019, Prague, Czech Republic
Place of Publication	New York, NY, USA
Publisher	ACM
Pages	129-130
Number of pages	2
ISBN (Electronic)	9781450361118, 9781450367486
DOIs	https://doi.org/10.1145/3319619.3338470
Publication status	Published - 13 Jul 2019
Event	The Genetic and Evolutionary Computation Conference 2019 - Prague Conference Center, Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 https://gecco-2019.sigevo.org/index.html/HomePage

Conference

Conference	The Genetic and Evolutionary Computation Conference 2019
Abbreviated title	GECCO'19
Country/Territory	Czech Republic
City	Prague
Period	13/07/19 → 17/07/19
Internet address	https://gecco-2019.sigevo.org/index.html/HomePage

Keywords

Puzzle game
NP-complete
Combinatorial optimization
Ant colony optimization

Access to Document

10.1145/3319619.3338470

Solving_Nurikabe_with_Ant_Colony_Optimisation__GECCO_poster_version_Accepted author manuscript, 657 KB

Cite this

@inproceedings{b9dfc2d9b617419d8dc6c06d0fe77e2f,

title = "Solving Nurikabe with Ant Colony Optimization",

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.",

keywords = "Puzzle game, NP-complete, Combinatorial optimization, Ant colony optimization",

author = "Martyn Amos and Matthew Crossley and Huw Lloyd",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3319619.3338470",

language = "English",

pages = "129--130",

booktitle = "GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion",

publisher = "ACM",

address = "United States",

note = "The Genetic and Evolutionary Computation Conference 2019, GECCO'19 ; Conference date: 13-07-2019 Through 17-07-2019",

url = "https://gecco-2019.sigevo.org/index.html/HomePage",

}

Amos, M, Crossley, M & Lloyd, H 2019, Solving Nurikabe with Ant Colony Optimization. in GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion: July 13–17, 2019, Prague, Czech Republic. ACM, New York, NY, USA, pp. 129-130, The Genetic and Evolutionary Computation Conference 2019, Prague, Czech Republic, 13/07/19. https://doi.org/10.1145/3319619.3338470

Solving Nurikabe with Ant Colony Optimization. / Amos, Martyn; Crossley, Matthew; Lloyd, Huw.
GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion: July 13–17, 2019, Prague, Czech Republic. New York, NY, USA: ACM, 2019. p. 129-130.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Solving Nurikabe with Ant Colony Optimization

AU - Amos, Martyn

AU - Crossley, Matthew

AU - Lloyd, Huw

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - Puzzle game

KW - NP-complete

KW - Combinatorial optimization

KW - Ant colony optimization

U2 - 10.1145/3319619.3338470

DO - 10.1145/3319619.3338470

M3 - Conference contribution

SP - 129

EP - 130

BT - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion

PB - ACM

CY - New York, NY, USA

T2 - The Genetic and Evolutionary Computation Conference 2019

Y2 - 13 July 2019 through 17 July 2019

ER -

Solving Nurikabe with Ant Colony Optimization

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this