Complexity of Scorpion Solitaire and applications to Klondike

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.