Solitaire

Yet another “Is this NP-complete?” question. The problem is of a kind that I discussed before.

In the game Solitaire you sometimes visualize the state you want to achieve and regard the necessary intermediate moves as chore. A friend wondered how to reach the goal with a minimum number of key presses. (He plays on a Blackberry with no mouse.) Let us look at a simplified example.

□,1,□,□,4,3,□,2,5                     (1)   ↝ □,1,□,□,4,23,□,□,5                     (2)   ↝ □,1,□,□,234,□,□,□,5                     (3)   ↝ □,□,□,□,1234,□,□,□,5                     (4)   ↝ □,□,□,□,□,□,□,□,12345                     (5)

In this example there are 9 slots into which cards 1–to–5 are placed. In a valid state, each slot contains a contiguous sequence of cards, possibly empty (□). Each move consists of transporting a contiguous sequence of cards from one slot to another. (Take a moment to convince yourself that a valid state is reached only if the whole sequence of a slot is transported.) The cost of a move is the distance between the source and the target slots (and is independent of the size of the transported sequence). In the example above there are 4 moves with a total cost of 2+1+3+4=10. The goal is to put all the cards in one slot.

This problem has a dynamic programming solution, which works on a different representation of the states.

2,8,6,5,9                     (6)   ↝ 2,6,5,9                     (7)   ↝ 2,5,9                     (8)   ↝ 5,9                      (9)   ↝ 9                     (10)

The first state tells us that card 1 is in slot 2, card 2 in slot 8, card 3 in slot 6, and so on; the last state tells us that all cards are in slot 9. In general, a state tells us in which slots there are cards, and does so in increasing order of cards’ values. With this representation a move consists of crossing out a number. The cost of a move is the absolute difference between the crossed out number and the following number. (The last number in a state cannot be crossed out.) With n cards there are 2ⁿ⁻¹ possible states. For each state there are <n possible moves. Therefore, if each possible state and each possible move is examined at most once, then this algorithm works in O(n2ⁿ) steps.

Note that there are (n−1)! sequences of moves that attain the goal. A similar reduction (from n! to around n2ⁿ) appears when one moves from a brute force solution to a dynamic programming solution of the Hamiltonian cycle problem. In general, it is often possible to look at all subsets when it seems that looking at all permutations is necessary.

Questions: Can you do better? Is this problem NP-complete?