Calculation Solitaire is NP-Complete

Chuzo IWAMOTO; Tatsuya IDE

doi:10.1587/transinf.2022FCL0002

Calculation Solitaire is NP-Complete

Chuzo IWAMOTO, Tatsuya IDE

Full Text Views

0

Cite this

Summary :

Calculation is a solitaire card game with a standard 52-card deck. Initially, cards A, 2, 3, and 4 of any suit are laid out as four foundations. The remaining 48 cards are piled up as the stock, and there are four empty tableau piles. The purpose of the game is to move all cards of the stock to foundations. The foundation starting with A is to be built up in sequence from an ace to a king. The other foundations are similarly built up, but by twos, threes, and fours from 2, 3, and 4 until a king is reached. Here, a card of rank i may be used as a card of rank i + 13j for j ∈ {0, 1, 2, 3}. During the game, the player moves (i) the top card of the stock either onto a foundation or to the top of a tableau pile, or (ii) the top card of a tableau pile onto a foundation. We prove that the generalized version of Calculation Solitaire is NP-complete.

Publication: IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.328-332

Publication Date: 2023/03/01

Publicized: 2022/10/31

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2022FCL0002

Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)

Category

Authors

Chuzo IWAMOTO
Hiroshima University
Tatsuya IDE
Hiroshima University

Keyword

calculation solitaire, card game, NP-complete

Cite this

Copy

Chuzo IWAMOTO, Tatsuya IDE, "Calculation Solitaire is NP-Complete" in IEICE TRANSACTIONS on Information, vol. E106-D, no. 3, pp. 328-332, March 2023, doi: 10.1587/transinf.2022FCL0002.
Abstract: Calculation is a solitaire card game with a standard 52-card deck. Initially, cards A, 2, 3, and 4 of any suit are laid out as four foundations. The remaining 48 cards are piled up as the stock, and there are four empty tableau piles. The purpose of the game is to move all cards of the stock to foundations. The foundation starting with A is to be built up in sequence from an ace to a king. The other foundations are similarly built up, but by twos, threes, and fours from 2, 3, and 4 until a king is reached. Here, a card of rank i may be used as a card of rank i + 13j for j ∈ {0, 1, 2, 3}. During the game, the player moves (i) the top card of the stock either onto a foundation or to the top of a tableau pile, or (ii) the top card of a tableau pile onto a foundation. We prove that the generalized version of Calculation Solitaire is NP-complete.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022FCL0002/_p

Copy

@ARTICLE{e106-d_3_328,
author={Chuzo IWAMOTO, Tatsuya IDE, },
journal={IEICE TRANSACTIONS on Information},
title={Calculation Solitaire is NP-Complete},
year={2023},
volume={E106-D},
number={3},
pages={328-332},
abstract={Calculation is a solitaire card game with a standard 52-card deck. Initially, cards A, 2, 3, and 4 of any suit are laid out as four foundations. The remaining 48 cards are piled up as the stock, and there are four empty tableau piles. The purpose of the game is to move all cards of the stock to foundations. The foundation starting with A is to be built up in sequence from an ace to a king. The other foundations are similarly built up, but by twos, threes, and fours from 2, 3, and 4 until a king is reached. Here, a card of rank i may be used as a card of rank i + 13j for j ∈ {0, 1, 2, 3}. During the game, the player moves (i) the top card of the stock either onto a foundation or to the top of a tableau pile, or (ii) the top card of a tableau pile onto a foundation. We prove that the generalized version of Calculation Solitaire is NP-complete.},
keywords={},
doi={10.1587/transinf.2022FCL0002},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Calculation Solitaire is NP-Complete
T2 - IEICE TRANSACTIONS on Information
SP - 328
EP - 332
AU - Chuzo IWAMOTO
AU - Tatsuya IDE
PY - 2023
DO - 10.1587/transinf.2022FCL0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2023
AB - Calculation is a solitaire card game with a standard 52-card deck. Initially, cards A, 2, 3, and 4 of any suit are laid out as four foundations. The remaining 48 cards are piled up as the stock, and there are four empty tableau piles. The purpose of the game is to move all cards of the stock to foundations. The foundation starting with A is to be built up in sequence from an ace to a king. The other foundations are similarly built up, but by twos, threes, and fours from 2, 3, and 4 until a king is reached. Here, a card of rank i may be used as a card of rank i + 13j for j ∈ {0, 1, 2, 3}. During the game, the player moves (i) the top card of the stock either onto a foundation or to the top of a tableau pile, or (ii) the top card of a tableau pile onto a foundation. We prove that the generalized version of Calculation Solitaire is NP-complete.
ER -