14 July 2010


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 2n−1 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(n2n) steps.

Note that there are (n−1)! sequences of moves that attain the goal. A similar reduction (from n! to around n2n) 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?

1 comment:

rgrig said...

Javi Gomez showed me a polynomial time algorithm for this problem.

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.