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.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.