Zen Puzzle Garden is NP-complete

Robin Houston; Joseph White; Martyn Amos

doi:10.1016/j.ipl.2011.10.016

Zen Puzzle Garden is NP-complete

Robin Houston, Joseph White, Martyn Amos^*

^*Corresponding author for this work

Computer Information Sciences Department

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

Zen Puzzle Garden is a commercial computer puzzle game. We prove that deciding the solvability of the game is NP-complete. The game therefore provides a useful test-bed for new automatic solving methods.

Original language	English
Pages (from-to)	106-108
Number of pages	3
Journal	Information Processing Letters
Volume	112
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2011.10.016
Publication status	Published - 31 Jan 2012

Keywords

Computational complexity
NP-completeness
Puzzle

Access to Document

10.1016/j.ipl.2011.10.016

Cite this

@article{5e8d33ad7a31489996ed34d6e9a328b2,

title = "Zen Puzzle Garden is NP-complete",

abstract = "Zen Puzzle Garden is a commercial computer puzzle game. We prove that deciding the solvability of the game is NP-complete. The game therefore provides a useful test-bed for new automatic solving methods.",

keywords = "Computational complexity, NP-completeness, Puzzle",

author = "Robin Houston and Joseph White and Martyn Amos",

year = "2012",

month = jan,

day = "31",

doi = "10.1016/j.ipl.2011.10.016",

language = "English",

volume = "112",

pages = "106--108",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Zen Puzzle Garden is NP-complete

AU - Houston, Robin

AU - White, Joseph

AU - Amos, Martyn

PY - 2012/1/31

Y1 - 2012/1/31

N2 - Zen Puzzle Garden is a commercial computer puzzle game. We prove that deciding the solvability of the game is NP-complete. The game therefore provides a useful test-bed for new automatic solving methods.

AB - Zen Puzzle Garden is a commercial computer puzzle game. We prove that deciding the solvability of the game is NP-complete. The game therefore provides a useful test-bed for new automatic solving methods.

KW - Computational complexity

KW - NP-completeness

KW - Puzzle

U2 - 10.1016/j.ipl.2011.10.016

DO - 10.1016/j.ipl.2011.10.016

M3 - Article

AN - SCOPUS:82255195402

SN - 0020-0190

VL - 112

SP - 106

EP - 108

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Zen Puzzle Garden is NP-complete

Abstract

Keywords

Access to Document

Fingerprint

Cite this