The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cálculo é um jogo de paciência com um baralho padrão de 52 cartas. Inicialmente, as cartas A, 2, 3 e 4 de qualquer naipe são dispostas como quatro bases. As 48 cartas restantes são empilhadas como estoque e há quatro pilhas vazias do tabuleiro. O objetivo do jogo é mover todas as cartas do estoque para as fundações. A base começando com A deve ser construída na sequência de um ás até um rei. As outras fundações são construídas de forma semelhante, mas em pares, três e quatro, de 2, 3 e 4, até que um rei seja alcançado. Aqui, uma carta de classificação i pode ser usado como uma carta de classificação i + 13j for j ∈ {0, 1, 2, 3}. Durante o jogo, o jogador move (i) a carta do topo do monte para uma fundação ou para o topo de uma pilha do tabuleiro, ou (ii) a carta do topo de uma pilha do tabuleiro para uma fundação. Provamos que a versão generalizada do Calculation Solitaire é NP-completa.
Chuzo IWAMOTO
Hiroshima University
Tatsuya IDE
Hiroshima University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
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
Copiar
@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},}
Copiar
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 -