Scorpion is a puzzle game that falls under the category of Solitaires. The problem of determining whether a starting con guration of a Solitaire game (generalised to contain an arbitrary number of cards) can lead to a winning con guration has been studied from the perspective of Computational Complexity 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 con guration of Scorpion allows for a winning sequence of moves is NP-complete for any s 1, and it remains so also when the initial con guration 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 con guration of the Klondike Solitaire allows for a winning sequence of moves.
Solitaire games are one-player games, or puzzles, which employ a deck of cards
and a tableau of possible positions for the cards. The goal of the game is to
achieve a winning con guration of the cards on the tableau by applying
legitimate moves to an initial con guration. The possible decks, tableaux, moves,
initial and winning con gurations are determined by the rules of the
particular type of Solitaire one intends to play. According to [
In this paper, we consider the Scorpion Solitaire that we now introduce in its traditionally played version. The deck is composed of 52 cards, partitioned into 4 suits of 13 cards each (~, }, | or ), ranging from rank 1 (Ace) to 13 (King). The setting consists of a tableau and a stock, with the tableau, in turn, consisting of 7 columns each of which may contain a stack of cards, and the stock being a special reserve set of cards. At the start of the game an initial layout is supplied, with 3 face down cards placed in the stock and 7 stacks of cards dealt in the tableau: the rst 4 stacks contain 2 face down cards at the bottom and 5 face up cards on top, while the last 3 stacks consist of 7 face up cards (see Figure 1). The goal of the game is to build 4 stacks of cards on the tableau, each of them containing 13 cards of the same suit arranged in descending order, with the King (rank 13) at the bottom and the Ace (rank 1) on top of each stack. The goal is pursued by performing a sequence of moves: a face up card x is allowed to be moved from the stack containing it to cover card y only if y is the top card of a di erent stack , suit(x) = suit(y) and rank(y) = rank(x) + 1. Hence, any non-King card x is allowed to perform one single move within the game, and has no choice about which move to perform. When a card x is moved, all the cards covering x are moved together as a unit, preserving their relative order (see Figure 2). A face up King and all the cards covering it can be moved to any empty column slot on the tableau, which appears after a card located at the bottom of its own stack is moved. A face down card is turned up when it becomes the top card of its stack. At any point in the game, the player can deal the 3 cards in the stock on top of the stacks located in the 3 leftmost column slots on the tableau.
We study the computational complexity of deciding, given an initial layout, if a sequence of moves exists achieving the goal. Needless to say, we shall consider generalized layouts, that is, layouts dealing with a deck of s suits with n cards each, with a tableau composed of k columns of arbitrary size in the initial arrangement and a stock with d cards in the initial arrangement (with d k).
Di erently from the original game, we deal with a complete information game, that is, we have no face down cards. Instead, we may have face up locked cards: a locked card cannot be moved until the card covering it is not moved; in particular, all cards in the stock will be considered locked. Our choice of dealing with complete information games is shared with the literature on this topic [1{4].
The study of Solitaire card games from a computational complexity
perspective is not a novel topic, where (as we remarked a few lines above), whenever we
talk about a complexity result for a Solitaire game, we implicitly refer to
generalized versions employing decks of arbitrarily large size. The rst major result
about computational complexity in Solitaire games comes from a paper about
Automated Planning domains used in AI planning competitions [
The hardness proofs for the Scorpion Solitaire we present in this paper are also reductions from 3SAT. However, they require a substantially di erent approach to model the non deterministic nature of the choice of a truth assignment to the variables in a boolean formula: indeed, while a non deterministic behaviour is intrinsic in the Free Cell (or Spider) playing rules, in that each (let's say, black) card may be covered by two (let's say, red) cards (for instance card (3; |) may be covered by both (2; ~) and (2; })), the Scorpion playing rules state that any (non-ace) card may be covered by exactly one other card (that is, card (3; |) may be covered only by (2; |)).
In [
After having provided the needed formal de nitions in Section 2, in Section 3 we prove the NP-completeness of deciding if a winning strategy for a 4-suits Scorpion game exists even when the initial setting has an empty stock. In Section 3, we also state the stronger result according to which the problem remains NPcomplete for 1-suit games and initial setting not containing locked cards. Then, in Section 4, we prove the NP-completeness of the one-black one-red suits version of Klondike. Finally, in Section 5 we draw some conclusions and discuss some open problems. 2
Let n 2 N and s 2 N; a deck of cards is a set D = [n] [s]1. A Scorpion layout L = fS; C1; : : : ; Ckg for a deck of cards D is an arrangement of the cards in D into k columns C1; : : : ; Ck and a stock S. The stock is a sequence hs1; s2; : : : ; sdi of d k cards. Each column consists of a pair of (possibly empty) stacks: the locked cards stack and the unlocked cards stack. Let hu1; u2; : : : uhi be the (non-empty) unlocked cards stack in some column: for any j 2 2; : : : ; h 1, the sequence of cards huj ; : : : uhi is called a sub-column starting at uj , card u1 is the base of the column, card uh is the top of the column and, for i = 2; : : : ; h, card uj covers card uj 1.
A Scorpion game is a sequence hL0; L1; : : : ; Lni of Scorpion layouts such that, for any t = 1; : : : ; n, the transition from Lt to Lt+1 occurs according to one of the (mutually exclusive) rules described in the following. 1) Lt has a non-empty stock and Lt+1 is derived from Lt by moving all cards in the stock: for h = 1; : : : ; d, the hth card in the stock in Lt becomes the (unlocked) top card of column Ch in Lt+1 and the stock of Lt+1 is empty. 2) In Lt card (i; j) is the top card of column `, (i 1; j) is unlocked and contained in column `0 6= `, and Lt+1 is derived from Lt by moving card (i 1; j) to cover card (i; j): the whole sub-column starting at (i 1; j) is moved to column ` so that the top card of column `0 in Lt is the top card of column of column ` in Lt+1. If (i 1; j) covers card (i0; j0) in Lt, then (i0; j0) is the top card of column `0 in Lt+1 while, if (i 1; j) is the base card of column `0 in Lt, column `0 is empty in Lt+1. 1 For m 2 N, we shortly denote as [m] the set f1; 2; : : : ; mg. 3) In Lt column ` is empty and an unlocked card (n; j) is contained in column `0 6= `, and Lt+1 is derived from Lt by moving to column ` the subcolumn starting at (n; j): in Lt+1 the base of column ` is (n; j), the top card of column ` is the top card of column `0 in Lt, and similarly as in the previous case as to the top of column `0.
A winning Scorpion layout is a Scorpion layout L such that in L exactly s columns are non empty, the base of each of them is a (di erent) card (n; j), with j 2 [s], and, for any i 2 [n 1] and j 2 [s], card (i; j) covers card (i + 1; j).
A winning Scorpion game starting at L0 is a Scorpion game hL0; L1; : : : ; Lpi such that Lp is a winning Scorpion layout.
Given a deck D of cards and a Scorpion layout L0, the Scorpion Winning Game problem (in short, SWG) consists in deciding if there exists a winning Scorpion game starting at L0. 3
Our rst step to the study of the computational complexity of SWG is the proof of its membership to NP. To this aim, we claim that, for any Scorpion layout L0, if there exists a winning Scorpion game starting at L0 then there also exists a winning Scorpion game hL0; L1; : : : ; Lpi with p ns + 1 + 2jSj. Indeed, since any card (i; j) 2 D such that i < n may be moved at most once (that is, once it covers card (i + 1; j) it can be no longer moved), then a winning Scorpion game consists of at most one transition occurring according to rule 1), at most (n 1)s transitions occurring according to rule 2), at most s transitions occurring according to rule 3) each of which places a di erent card (n; j) as the base of a column (for any j 2 [s]), and a set of transitions still occurring according to rule 3) each of which move some card (n; j) from the base of a column to another. At most 2 S
j j moves in the last set are meaningful as to compose a winning game: they are those pairs of moves such that one move frees one of the rst jSj columns and the other move possibly shifts to it another column having as its base some (n; j) and as its top an appropriate card to be covered by a card in the stock.
Hence, a certi cate for an instance L0 of SWG is a sequence L1; : : : ; Lp of p j j Scorpion layouts. Since verifying if hL0; L1; : : : ; Lpi is actually a ns + 1 + 2 S Scorpion winning game requires polynomial time, this proves that SWG is in NP.
We now turn to proving the NP-completeness of SWG.
Theorem 1. SWG is NP-Complete even when restricted to set of instances such that D is a deck on four suits and the stock in the initial layout is empty. Proof. To prove the assertion, we provide a reduction from 3SAT. Let hX; f i be an instance of 3SAT, where X = fx1; : : : ; xng is a set of boolean variables and f = fc1; : : : ; cmg is a set of clauses over X each containing exactly three literals (each literal, in turn, being a variable in X or its negation). We write li;j for the ith literal in cj (i = 1; 2; 3), and, with a slight abuse of notation, we write xi 2 cj (:xi 2 cj ) if xi (respectively, :xi) is a literal in cj . Without loss of generality, in what follows we shall assume that m n.
The description of the instance hD; Lf0 i of SWG corresponding to an instance hX; f i of 3SAT is rather intricate and the reader may refer to Fig. 3 to get some intuition about how the gadgets are structured.
The deck of cards D consists of 4 suits of nf = 10m + 1 cards each. In order to make the proof closer to the language of card players, in what follows we shall denote the four suits as ~, |, } and (instead of 1; 2; 3; 4 as de ned in Section 2).
For any 1 i n, we de ne the base variable value of xi as i = 5(i 1) and, for any 1 j m, we de ne the base clause value of cj as j = 3(j 1) and the base clubs clause value of cj as j = 10(j 1).
The columns of Lf0 are partitioned into three sets: a set of variable gadgets columns, a set of clause gadgets columns, and a set consisting of one critical columns and four suit columns.
Variable gadgets columns. Each variable xi is associated to a pair of columns denoted as vi and vi: 1. column vi contains the unlocked cards ( i + 3; ~) and ( i + 2; ~), ( i + 2; ~) being the top of column vj and covering card ( i + 3; ~); 2. column vi contains the unlocked cards ( i + 1; ~) and ( i + 4; ~), ( i + 4; ~) being the top of column vj and covering card ( i + 1; ~).
Clause gadgets columns. Each clause cj is associated to the four columns uj1 , uj2 , uj3 and uj4 : 1. uj1 , uj2 and uj3 contain a single unlocked card each (being their, respective, top card): uj1 contains ( j + 3; |), uj2 contains ( j + 6; |) and uj3 contains ( j + 9; |); 2. nally, uj4 contains the following stack of unlocked cards:
h( j + 2; }); ( j + 1; ); ( j + 7; |); ( j + 4; |); ( j + 1; |); ( j + 2; )i; with ( j + 2; ) at its top.
We can now model a variable (or its negation) being contained in a clause. Starting with j = 1, and up to j = m, we repeat the following steps: for any 1 i n, { if l1;j = xi then we add card ( j + 8; |) as a locked card at the bottom of column vi, while if l1;j = :xi then we add card ( j + 8; |) as a locked card at the bottom of column vi; { if l2;j = xi then we add card ( j + 5; |) as a locked card at the bottom of column vi, while if l2;j = :xi then we add card ( j + 5; |) as a locked card at the bottom of column vi; { if l3;j = xi then we add card ( j + 2; |) as a locked card at the bottom of column vi, while if l3;j = :xi then we add card ( j + 2; |) as a locked card at the bottom of column vi.
As an example, if c2 = f:x2; x3; :x8g then we add (18; |) to the bottom of column v2, (15; |) to the bottom of column v3 and (12; |) to the bottom of column v8, all of them locked.
Critical column: the critical column consists of the single unlocked card ( m + 1; }), which is both base and top of the critical column and covers the following stack of locked cards: h (10; |); (20; |); : : : ; (10m; |); (3; ); (6; ); : : : ; (3m; ); (3; }); (6; }); : : : ; (3(m 1); }); (3m; }); (5; ~); (10; ~); : : : ; (5n; ~); (1; }) = ( 1 + 1; }); (4; }) = ( 2 + 1; }); : : : ; ( m 1 + 1; }) i:
As to the suit columns, that is, the hearts column, the spades column, the diamonds column and the clubs column, all the cards they contain are unlocked and { the hearts column consists of the stack h(nf ; ~); (nf
1; ~); : : : ; (5n + 1; ~)i with (5n + 1; ~) as its top; { the remaining three suit columns have a similar structure, that is, spades column: h(n;f ); (nf 1; ); : : : ; (3m + 1; )i; diamonds column: h(nf ; }; (nf 1; }); : : : ; (3m + 1})i; clubs column: h(10m + 1; |)i:
The description of Lf0 is now complete. Needless to say, deriving Lf0 from hX; f i requires polynomial time.
It remains to show that there exists a winning Scorpion game starting at Lf0 if and only if there exists a truth assignment for X satisfying all clauses in f .
Assume there is a truth assignment a : X ! ftrue; falseg satisfying f . We now derive from a a winning Scorpion game starting at L0 ; for the sake of f readability, in what follows we shall describe the sequence of card moves yielding the Scorpion layouts by which the winning game is composed.
For any 1 i n, the following steps are repeated. { If a(xi) = true, the sub-column h( i + 3; ~); ( i + 2; ~)i is moved from column vi to column vi so that card ( i + 3; ~) covers card ( i + 4; ~). In this way, cards in the locked stack of column vi get unlocked one after the other and can be moved to become the top cards of some clause gadget column: if, for some 1 j m, card ( j + 2; |) (or ( j + 5; |) or ( j + 8; |)) has become the top card of column vi then it gets unlocked and it is moved to cover card ( j + 3; |) in column uj1 (respectively, card ( j + 6; |) in column uj2 or card ( j + 9; |) in column uj3 ). This makes another card in the locked stack unlocked, and so on. { If a(xi) = false, the sub-column h( i + 1; ~); ( i + 4; ~)i is moved from column vi to column vi so that card ( i + 1; ~) covers ( i + 2; ~). In this way, just as in the previous case, cards in the locked stack of column vi get unlocked one after the other and are moved to become top cards of some clause gadget column.
Since a satis es all clauses in f then, for each 1 j m, at least one column out of uj1 ; uj2 ; uj3 has its top card changed into, respectively, ( j + 2; |), ( j + 5; |) and ( j + 8; |); we can therefore move at least one of the three cards ( j + 7; |), ( j + 4; |), or ( j + 1; |) from uj4 to cover the new top card in uj1 , or uj2 or uj3 . After this, the top card of either uj1 , or uj2 or uj3 has become ( j + 2; ): we can then move ( j + 1; ) from uj4 to cover ( j + 2; ). By doing so, card ( j + 2; }) has become the top card of column uj4 .
We have, thus, derived a Scorpion Layout such that, for any 1 j m, card ( j + 2; }) is the top card of column uj4 (and, actually, its only card). At this point, we move ( m + 1; }) from the critical column to cover ( m + 2; }) on top of column um4 , so unlocking ( m 1 + 1; }) in the critical column. This last card, in turn, can be moved to cover card ( m 1 + 2; }) on top of column u(m 1)4 , and so on. At the end of this procedure, card (5n; ~) has been unlocked and has become the top card of the critical column: we move it to cover the top card in the hearts column, then we cover it by moving card (5n 1; ~) = ( n + 4; ~) from column vn or vn. Continuing, we move all the ~ cards onto the hearts pile. Now, card (3m; }) is the top card of the critical column and, hence, unlocked. It can, thus, be moved on top of the diamonds column and, then, be covered by card (3m 1; }) that is, by the sub-column h(3m 1; }); (3m 2; })i, that moves from column um4 , followed by (3m 2; }) from the critical column. Proceeding this way, we bring all the } cards in the diamonds column.
Similarly, all cards are moved to the spades column and all | cards are moved to the clubs column.
We have thus derived from a a winning Scorpion game starting at L0 . f
Conversely, assume there exists a winning Scorpion game hLf0 ; L1; : : : ; LM i. This means that there exists 1 k M such that the critical column in Lk does not contain any }. In L0 , the critical column contains a single unlocked f card, that is, ( m + 1; }), and such card has to be moved in order to unlock the card it covers (( m 1 + 1; })). Before card ( m + 1; }) can be moved, card ( m + 1; ) (that, in L0 , covers card ( m + 2; }) in column um4 ) has to be moved f and this is possible only after ( m + 2; ) has been moved to a di erent column. This is possible either by direcly moving ( m + 2; ) to cover ( m + 3; ) or by moving any of the | cards lying in um4 beneath ( m + 2; ) (so moving the whole sub-column). The former case cannot happen, since ( m + 3; ) = (3m; ) is locked in the critical column and can become unlocked only after all } cards above it are moved. Hence, in order to move card ( m + 1; }), some card out of ( m +7; |), ( m +4; |), ( m +1; |) (the cards lying on um4 beneath ( m +2; )) are to be moved rst. All such | cards are locked in some variable gadget column and they become unlocked only after the ~ segment at its top is moved, that is, a) after the sub-column h( i + 3; ~); ( i + 2; ~)i is moved to cover card ( i + 4; ~) (in column vi), for some vi containing ( m + 7; |), or ( m + 4; |), or ( m + 1; |), b) or after the sub-column h( i + 1; ~); ( i + 4; ~)i is moved to cover card ( i + 2; ~) (in column vi), for some vi containing ( m + 7; |), or ( m + 4; |), or ( m + 1; |).
Summarizing, card ( m + 1; }) is moved only after ( i + 3; ~) has been moved to cover ( i + 4; ~) or ( i + 1; ~) has been moved to cover ( i + 2; ~). Notice that these last two moves are mutually exclusive, that is, the occurrence of one of them forbids the occurrence of the other; hence, we may set a(xi) = 8 true if case a) occurs, that is, > >< ( i + 3; ~) is moved to cover ( i + 4; ~), > false if case b) occurs, that is, >: ( i + 1; ~) is moved to cover ( i + 2; ~).
Since, by construction, case a) occurs when xi 2 cm and case b) occurs when :xi 2 cm, the truth assignment above to variable xi satis es clause cm. The above reasoning can be repeated for card ( m 1 + 1; }) and, hence, clause cm 1, and so on down to card ( 1 + 1; }) and, hence, clause c1. This proves that the so built truth assignment a satis es all clauses in f .
It turns out that SWG is NP-complete even for sets of instances satisfying stronger restrictions than those considered in Theorem 1, that is, when the game is played with a single suit deck of cards (s = 1), and the initial layout has an empty stock and no locked cards. Since the proof of this case is much more intricate and long of that of Theorem 1, for the sake of simplicity and due to space constraints, we have shown the proof for the case of a traditional 4 suits deck of cards and an initial layout containing locked cards. The proof of the following, stronger, result is then deferred to the full version of the paper. Theorem 2. SWG is NP-Complete even when restricted to set of instances such that D is a deck on just one suit, and the initial layout contains an empty stock and no locked cards.
We explicitly observe that, by simple generalization, from Theorem 2 it follows that SWG is NP-complete for any ( xed) number of suits. 4
Klondike is played with a 4 suits deck of cards and its setting consists of a stock, a waste, 4 foundations (one foundation per suit) and a tableau (see Figure 4). The foundations are initially empty, but, as the game progresses, the foundations will be built up by suit. The tableau consists of seven stacks of cards: at the beginning, all cards in each stack are face down except for the top card which is left face up. Goal of a Klondike game is to place all the cards into the foundations: when a foundation is empty, as soon as an Ace appears as the top card of any stack in the tableau, it can be removed from the tableau to become the top card of that foundation; when the top card of a foundation is card i of suit x, with 1 i < 13 and x 2 f~; |; }; g, as soon as card i+1 of suit x appears as the top card of any stack in the tableau, it can be removed from the tableau to become the top card of that foundation. Hence, the last card moved to a foundation is a King.
The tableau is used to organize cards until it becomes possible to place them in the foundations. Cards can be moved among the stacks in the tableau by alternating color: if the top card of a stack in the tableau is card i of a red suit (~ or }) and card i 1 of a black suit (| or ) is a face up card in a di erent stack, then card i 1 can be moved to cover card i (and similarly with opposite colors). Similarly to Scorpion Solitaire, whenever a card is moved from a source stack to a destination stack in the tableau all (face up) cards on the source stack lying above the moved card must be moved as well, in their order, to the destination stack. Only a king can be placed into an empty stack. If a face down card is on the top of a stack, it becomes face up.
The stock is a stack-like set of face down cards: when the player clicks on the stock, 3 cards are dealt face up to the waste. Only the top most card in the waste is playable (once it has been played, the card immediately below it becomes playable, and so on): more precisely, it can be moved to cover a face up card in some stack in the tableau in decreasing order and alternating color (that is, a red suit card i may cover a black suit card i + 1 and a black suit card i may cover a red suit card i + 1).
We again consider complete information games (in [
Among the other results, [
Due to space limitations, the proof of Theorem 3 will be provided in the full paper. For the time being, we want to notice the similarities occurring between SWG restricted to 2 suits decks and empty stock and FLAT-SOLIT(1,1): indeed, in both problems, for every card c (other than maximum rank cards) there exists a unique card c0 such that c may be moved to cover c0 in the tableau and, conversely, for every card c (other than aces) there exists a unique card c0 such that c0 may be moved to cover c in the tableau. However, there is also a noticeable di erence between the two games: according to the Klondike rules, foundations are lled by cards of the same suit, in decreasing order, and by moving one card after the other. No similar structure exists in the Scorpion Solitaire, and this is the reason why it does not seem so easy to directly design a reduction from
SWG to FLAT-SOLIT(1,1). and we have, instead, exploited again a reduction from 3SAT to prove Theorem 3. However, the Klondike layout corresponding to an instance of 3SAT we construct in the proof of Theorem 3 is directly derived from the Scorpion layout associated to the same instance built in Theorem 2. 5
In this paper we have studied the computational complexity of deciding if a
winning strategy exists for a Scorpion Solitaire game and we have proved that
the problem is NP-complete even for one suit games and no face down (locked)
cards. We have also negatively answered a question posed in [
A Scorpion game depends on several parameters: number of suits, of cards per suit and of locked cards, stock size, number of columns. It seems quite clear after Theorem 2 that the complexity of the problem is not in uenced by number of suits, number of locked cards and stock size.
Instead, the role played as to the complexity of the problem by the number of columns and by the relation between number of cards and number of columns looks intriguing. In fact, the problem is trivially in P when the number of column is one or is equal to the (total) number of cards. And it seems reasonable to conjecture that the problem remains in P when the number of columns is \reasonably" larger than half of the (total) number of cards. On the other hand, the Scorpion layout corresponding to an instance hX; f i of 3SAT derived in the proof of Theorem 2 is built over a deck of 8n + 24m cards and consists of 2n + 4m + 1 columns (where n = jXj and m is the numbe of clauses in f ): that is, the problem is NP-complete when the number of columns is much smaller than half of the number of cards. But what about an even smaller number of columns? Actually, it seems quite a hard issue to understand what happens, for instance, for a constant number of columns; even for just two columns. We think investigating such topic could be interesting, eventually also in the parameterized complexity setting.