Zen Puzzle Garden is NP-complete

2011/06/10 by Robin Houston, Houston, Robin, Joseph White +3 · 1 voice
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.1106.2104

Submitted

arxiv created 2011/06/10 · arxiv published 2011/06/10 · arxiv updated 2011/06/13

Abstract

Zen Puzzle Garden (ZPG) is a one-player puzzle game. In this paper, we prove that deciding the solvability of ZPG is NP-complete.

Discussions

• Zen Puzzle Garden is NP-complete (2011) [hn, 2 points, 0 comments]

Related

• ZHED is NP-complete
• Rikudo is NP-complete
• Solitaire Chess is NP-complete
• On the NP-Completeness of Satisfying Certain Path and Loop Puzzles
• Mastermind is NP-Complete