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 条
  • [1] Rikudo is NP-complete
    Viet-Ha Nguyen
    Perrot, Kevin
    THEORETICAL COMPUTER SCIENCE, 2022, 910 : 34 - 47
  • [2] BoxOff is NP-Complete
    Hayward, Ryan
    Hearn, Robert
    Jamshidian, Mahya
    ADVANCES IN COMPUTER GAMES, ACG 2021, 2022, 13262 : 118 - 127
  • [3] Generalized Pyramid is NP-Complete
    Iwamoto, Chuzo
    Matsui, Yuta
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (11) : 2462 - 2465
  • [4] DECIDING FRATTINI IS NP-COMPLETE
    RYTER, CH
    SCHMID, J
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1994, 11 (03): : 257 - 279
  • [5] Chained Block is NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2024, E107D (03) : 320 - 324
  • [6] Choco Banana is NP-Complete∗
    Iwamoto, Chuzo
    Tokunaga, Takeru
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2024, E107A (09) : 1488 - 1491
  • [7] MaxCut on permutation graphs is NP-complete
    de Figueiredo, Celina M. H.
    de Melo, Alexsander A.
    Oliveira, Fabiano S.
    Silva, Ana
    JOURNAL OF GRAPH THEORY, 2023, 104 (01) : 5 - 16
  • [8] Medical diagnosis and treatment is NP-complete
    Arle, Jeffrey. E.
    Carlson, Kristen W.
    JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 2021, 33 (02) : 297 - 312
  • [9] Column subset selection is NP-complete
    Shitov, Yaroslav
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 610 : 52 - 58
  • [10] Five Cells and Tilepaint are NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2022, E105D (03) : 508 - 516