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 条
  • [21] NP-COMPLETE NUMBER-THEORETIC PROBLEM
    GURARI, EM
    IBARRA, OH
    JOURNAL OF THE ACM, 1979, 26 (03) : 567 - 581
  • [22] Automatically Solving NP-Complete Problems on a Quantum Computer
    Hu, Shaohan
    Liu, Peng
    Chen, Chun-Fu
    Pistoia, Marco
    PROCEEDINGS 2018 IEEE/ACM 40TH INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING - COMPANION (ICSE-COMPANION, 2018, : 258 - 259
  • [23] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS
    BAKER, BS
    JOURNAL OF THE ACM, 1994, 41 (01) : 153 - 180
  • [24] Sublinear P system solutions to NP-complete problems
    Dinneen, Michael J.
    Henderson, Alec
    Nicolescu, Radu
    THEORETICAL COMPUTER SCIENCE, 2023, 958
  • [25] Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105 (08)
  • [26] Two slightly-entangled NP-Complete problems
    Orús, R
    QUANTUM INFORMATION & COMPUTATION, 2005, 5 (06) : 449 - 455
  • [27] Solving NP-complete problems in the tile assembly model
    Brun, Yuriy
    THEORETICAL COMPUTER SCIENCE, 2008, 395 (01) : 31 - 46
  • [28] An optical fiber network oracle for NP-complete problems
    Wu, Kan
    Garcia de Abajo, Javier
    Soci, Cesare
    Shum, Perry Ping
    Zheludev, Nikolay I.
    LIGHT-SCIENCE & APPLICATIONS, 2014, 3
  • [29] Moon-or-Sun, Nagareru, and Nurimeizu are NP-Complete
    Iwamoto, Chuzo
    Ide, Tatsuya
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105A (09) : 1187 - 1194
  • [30] An optical fiber network oracle for NP-complete problems
    Kan Wu
    Javier García de Abajo
    Cesare Soci
    Perry Ping Shum
    Nikolay I Zheludev
    Light: Science & Applications, 2014, 3 (2) : e147 - e147