Scorpion is a puzzle game that falls under the category of Solitaires. The problem of determining whether a starting configuration of a Solitaire game (generalised 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 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 ini- tial configuration contains no face down (locked) cards. We then negatively answer a question posed in [2] by proving 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.

Arena, F., DI IANNI, M. (2020). Complexity of Scorpion Solitaire and applications to Klondike. In Proceedings of the 21th Italian Conference on Theoretical Computer Science (ICTCS 2020) (pp.172-183). CEUR Workshop Proceedings.

Complexity of Scorpion Solitaire and applications to Klondike

Miriam Di Ianni
2020-01-01

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 (generalised 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 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 ini- tial configuration contains no face down (locked) cards. We then negatively answer a question posed in [2] by proving 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.
The 21th Italian Conference on Theoretical Computer Science (ICTCS 2020)
2020
Rilevanza internazionale
2020
Settore INF/01 - INFORMATICA
English
Computational complexity; games and puzzles
Intervento a convegno
Arena, F., DI IANNI, M. (2020). Complexity of Scorpion Solitaire and applications to Klondike. In Proceedings of the 21th Italian Conference on Theoretical Computer Science (ICTCS 2020) (pp.172-183). CEUR Workshop Proceedings.
Arena, F; DI IANNI, M
File in questo prodotto:
File Dimensione Formato  
Scorpionllncs.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non specificato
Dimensione 788.51 kB
Formato Adobe PDF
788.51 kB 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/263531
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact