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 条
  • [41] Lexicalized Non-Local MCTAG with Dominance Links is NP-Complete
    Champollion L.
    Journal of Logic, Language and Information, 2011, 20 (3) : 343 - 359
  • [42] Embedding into l∞2 Is Easy, Embedding into l∞3 Is NP-Complete
    Jeff Edmonds
    Discrete & Computational Geometry, 2008, 39 : 747 - 765
  • [43] Embedding into l∞2 is easy, embedding into l∞3 is NP-complete
    Edmonds, Jeff
    DISCRETE & COMPUTATIONAL GEOMETRY, 2008, 39 (04) : 747 - 765
  • [44] Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete
    de Figueiredo, Celina M. H.
    de Melo, Alexsander A.
    Oliveira, Fabiano S.
    Silva, Ana
    DISCRETE & COMPUTATIONAL GEOMETRY, 2024, 71 (03) : 893 - 917
  • [45] Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete
    Celina M. H. de Figueiredo
    Alexsander A. de Melo
    Fabiano S. Oliveira
    Ana Silva
    Discrete & Computational Geometry, 2024, 71 : 893 - 917
  • [46] Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
    Jimenez, Andrea
    Schmidt, Tina Janne
    DISCRETE MATHEMATICS, 2020, 343 (09)
  • [47] Deciding Whether a Grid is a Topological Subgraph of a Planar Graph is NP-Complete
    Jimenez, Andrea
    Schmidt, Tina Janne
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 545 - 556
  • [48] Register Reassignment for Mixed-width ISAs is an NP-Complete Problem
    Shen, Bor-Yeh
    Hsu, Wei Chung
    Yang, Wuu
    IMCIC 2010: INTERNATIONAL MULTI-CONFERENCE ON COMPLEXITY, INFORMATICS AND CYBERNETICS, VOL I (POST-CONFERENCE EDITION), 2010, : 139 - 143
  • [49] Tree Convex Bipartite Graphs: NP-Complete Domination, Hamiltonicity and Treewidth
    Wang, Chaoyi
    Chen, Hao
    Lei, Zihan
    Tang, Ziyang
    Liu, Tian
    Xu, Ke
    FRONTIERS IN ALGORITHMICS, FAW 2014, 2014, 8497 : 252 - 263
  • [50] LINEARLY-GROWING REDUCTIONS OF KARP'S 21 NP-COMPLETE PROBLEMS
    Filar, Jerzy A.
    Haythorpe, Michael
    Taylor, Richard
    NUMERICAL ALGEBRA CONTROL AND OPTIMIZATION, 2018, 8 (01): : 1 - 16