Generalized Pyramid is NP-Complete

Chuzo IWAMOTO  Yuta MATSUI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.11   pp.2462-2465
Publication Date: 2013/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.2462
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
NP-complete,  computational complexity,  one-player game,  pyramid,  

Full Text: PDF>>
Buy this Article




Summary: 
Pyramid is a solitaire game, where the object is to remove all cards from both a pyramidal layout and a stock of cards. Two exposed cards can be matched and removed if their values total 13. Any exposed card of value 13 and the top card of the stock can be discarded immediately. We prove that the generalized version of Pyramid is NP-complete.