Computational Complexity of Generalized Golf Solitaire

Chuzo IWAMOTO

doi:10.1587/transinf.2014FCL0001

Computational Complexity of Generalized Golf Solitaire

Chuzo IWAMOTO

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.541-544

Publication Date: 2015/03/01

Publicized

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

Authors

Chuzo IWAMOTO
Hiroshima University

Keyword

computational complexity, NP-completeness, puzzle

Cite this

Copy

Chuzo IWAMOTO, "Computational Complexity of Generalized Golf Solitaire" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 3, pp. 541-544, March 2015, doi: 10.1587/transinf.2014FCL0001.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2014FCL0001/_p

Copy

@ARTICLE{e98-d_3_541,
author={Chuzo IWAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Computational Complexity of Generalized Golf Solitaire},
year={2015},
volume={E98-D},
number={3},
pages={541-544},
abstract={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.},
keywords={},
doi={10.1587/transinf.2014FCL0001},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Computational Complexity of Generalized Golf Solitaire
T2 - IEICE TRANSACTIONS on Information
SP - 541
EP - 544
AU - Chuzo IWAMOTO
PY - 2015
DO - 10.1587/transinf.2014FCL0001
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - 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.
ER -