Calculation Solitaire is NP-Complete

被引:0
|
作者
Iwamoto, Chuzo [1 ]
Ide, Tatsuya [1 ]
机构
[1] Hiroshima Univ, Grad Sch Adv Sci & Engn, Higashihiroshima 7398527, Japan
关键词
calculation solitaire; card game; NP-complete;
D O I
10.1587/transinf.2022FCL0002
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 maybe used as a card of rank i+13 j for j E {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.
引用
收藏
页码:328 / 332
页数:5
相关论文
共 50 条