Scorpion is a puzzle game that falls under the category of Solitaires. The problem of determining whether a starting configuration of a Solitaire game (generalized to contain an arbitrary number of cards) can lead to a winning configuration has been studied from the perspective of Computational Com- plexity for some of the most popular Solitaires, namely Free Cell [1], Klondike [2] and Spider [3], all resulting in hardness proofs. Scorpion, though, has a unique twist compared to the aforementioned ones: each card can be moved to cover only one other card. This property narrows the set of possible moves and makes a worthwhile issue investigating whether the same problem proved NP-complete for Free Cell, Klondike and Spider falls in P as far as Scorpion is considered. In this paper we prove that the problem of deciding whether an n-card s-suits initial configuration of Scorpion allows for a winning sequence of moves is NP-complete for any s ≥ 1, and it remains so also when the initial configuration contains no face down (locked) cards and under a constant ratio constraint between deck size and tableau size. As a side effect of our results, we have also succeeded in negatively answering a question posed in [2], in that we prove that it is NP-complete to decide whether an n-card one red suit-one black suit configuration of the Klondike Solitaire allows for a winning sequence of moves.

DI IANNI, M., Arena, F. (2021). Complexity of Scorpion Solitaire and applications to Klondike. THEORETICAL COMPUTER SCIENCE, 890, 105-124.

Complexity of Scorpion Solitaire and applications to Klondike

Di Ianni Miriam;
2021

Abstract

Scorpion is a puzzle game that falls under the category of Solitaires. The problem of determining whether a starting configuration of a Solitaire game (generalized to contain an arbitrary number of cards) can lead to a winning configuration has been studied from the perspective of Computational Com- plexity for some of the most popular Solitaires, namely Free Cell [1], Klondike [2] and Spider [3], all resulting in hardness proofs. Scorpion, though, has a unique twist compared to the aforementioned ones: each card can be moved to cover only one other card. This property narrows the set of possible moves and makes a worthwhile issue investigating whether the same problem proved NP-complete for Free Cell, Klondike and Spider falls in P as far as Scorpion is considered. In this paper we prove that the problem of deciding whether an n-card s-suits initial configuration of Scorpion allows for a winning sequence of moves is NP-complete for any s ≥ 1, and it remains so also when the initial configuration contains no face down (locked) cards and under a constant ratio constraint between deck size and tableau size. As a side effect of our results, we have also succeeded in negatively answering a question posed in [2], in that we prove that it is NP-complete to decide whether an n-card one red suit-one black suit configuration of the Klondike Solitaire allows for a winning sequence of moves.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01
English
Card Solitaires, Computational Complexity, NP-completeness
Francesco Arena, Miriam Di Ianni: Complexity of Scorpion Solitaire and applications to Klondike. ICTCS 2020: 172-183 (extended abstract)
DI IANNI, M., Arena, F. (2021). Complexity of Scorpion Solitaire and applications to Klondike. THEORETICAL COMPUTER SCIENCE, 890, 105-124.
DI IANNI, M; Arena, F
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
revisedTCSScorpion.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Copyright dell'editore
Dimensione 1.35 MB
Formato Adobe PDF
1.35 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/280456
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact