Computational Complexity of Generalized Golf Solitaire

Chuzo IWAMOTO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.3   pp.541-544
Publication Date: 2015/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014FCL0001
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
computational complexity,  NP-completeness,  puzzle,  

Full Text: PDF(372.2KB)>>
Buy this Article



Summary: 
Golf is a solitaire game, where the object is to move all cards from a 5×8 rectangular layout of cards to the foundation. A top card in each column may be moved to the foundation if it is either one rank higher or lower than the top card of the foundation. If no cards may be moved, then the top card of the stock may be moved to the foundation. We prove that the generalized version of Golf Solitaire is NP-complete.