Yet another “Is this NPcomplete?” 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.

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.

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^{n−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(n2^{n}) steps.
Note that there are (n−1)! sequences of moves that attain the goal. A similar reduction (from n! to around n2^{n}) 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 NPcomplete?
Javi Gomez showed me a polynomial time algorithm for this problem.
ReplyDelete