# Is this version of the Hanoi towers problem NP-complete?

This was really inspired by Solitaire, but a few people reacted with oh, it's like the towers of Hanoi, isn't it?'' so I'll try to pose the problem in terms of discs here.

Let's start. There are n disks on the real line, one of size 1 at position $x_1$, one of size 2 at position $x_2$, ..., and one of size n at position $x_n$. Your goal is to make a tower with all n discs, consuming as little energy as possible in the process. You are allowed to move a tower whose base is a disk of size k only on top of the disk with size k+1 (which may be the top of another mini-tower). The energy you consume to perform such a move is the distance traveled by the moved mini-tower. For example, the energy consumed by the first move is $|x_k-x_{k+1}|$.

Now, you'd like to write a program that tells you whether the energy you have is enough to perform the task. It just needs to say Y or N. (If the answer is Y, then clearly the list of moves is proof enough that the answer is correct, so the problem is NP. If the answer is N, there's no point in even attempting the task---you are too tired.)

What's the fastest such program you can find? Is the problem NP-complete? If it helps, consider a simplifications that restrict $x_k$'s to be rational, integers, integers in a certain range, etc.

Here's an upper bound: $O(n2^n)$. Represent the initial state by the list $x_1$, $x_2$ ,... ,$x_n$. A move affects the state by deleting a number in this list and the energy consumed by the move is the absolute difference between the deleted number and the number coming after. Clearly there are $2^n$ states with at most $n$ moves each. (See my blog post for an example run of this algorithm if it's not clear. The description there is in terms of cards.)

Note: Some of the comments below refer to older versions of the questions. See the history of edits if they seem confusing.

-
The way you have the question stated now, the solution is always to place 1 on top of 2, 2 on top of 3, 3 on top of 4, etc., which I doubt is what you intended. Are the discs meant to be placed in a random order, or are the "distances" arbitrary (meaning they're not really in a line?), or is moving a tower with more rings supposed to take more energy? –  BlueRaja - Danny Pflughoeft Jul 30 '10 at 16:25
The distances are integers. Equivalently, the discs always have integer coordinates along this line. Equivalently, there is an infinite line of empty boxes all of the same size. –  rgrig Jul 30 '10 at 16:29
Start with 1,3,2. Your solution uses 3 units of energy, while it's clearly possible to use only 2: move 2 on top of 3, then move 1 on top of 2. –  rgrig Jul 30 '10 at 16:33
Oh, now I see what was troubling you. I edited the question. –  rgrig Jul 30 '10 at 16:37
"n=3, the one with size 1 might be at position 1000" ???? If n = 3, doesn't that limit positions to 1, 2, and 3? Are there two constants here? (# disks, # of positions) If so, give them separate names. –  Jason S Jul 30 '10 at 17:06

Here's a polynomial time solution given to me by Javi Gomez. Let (i,j) with $i\le j$ represent the situation where disks i, i+1, ..., j are on top of each other in position $x_j$, and let E(i,j) represent the energy needed to obtain that configuration. Clearly E(i,i) is zero for all i. Also, $E(i,j)=\min_k E(i,k)+E(k,j)+|x_k-x_j|$. What we want is E(1,n).
You can never move a disk more than once, so the length of the certificate is $O(n)$. Taking into account the other answer, the problem is actually in P, not only in NP. –  rgrig Dec 8 '11 at 2:06