For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational Complexity of Generalized Golf Solitaire
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
computational complexity, NP-completeness, puzzle,
Full Text: PDF(372.2KB)>>
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.