Hanoi configuration at a certain move

Question

I am interested in finding how many disks are on each peg at a given move in the towers of Hanoi puzzle. For example, given n = 3 disks we have this sequence of configurations for optimally solving the puzzle:

   0 1 2
0. 3 0 0
1. 2 0 1 (move 0 -> 2)
2. 1 1 1 (move 0 -> 1)
3. 1 2 0 (move 2 -> 1)
4. 0 2 1 (move 0 -> 2)
5. 1 1 1 (move 1 -> 0)
6. 1 0 2 (move 1 -> 2)
7. 0 0 3 (move 0 -> 2)

So given move number 5, I want to return 1 1 1, given move number 6, I want 1 0 2 etc.

This can easily be done by using the classical algorithm and stopping it after a certain number of moves, but I want something more efficient. The wikipedia page I linked to above gives an algorithm under the Binary solutions section. I think this is wrong however. I also do not understand how they calculate n.

If you follow their example and convert the disk positions it returns to what I want, it gives 4 0 4 for n = 8 disks and move number 216. Using the classical algorithm however, I get 4 2 2.

There is also an efficient algorithm implemented in C here that also gives 4 2 2 as the answer, but it lacks documentation and I don't have access to the paper it's based on.

The algorithm in the previous link seems correct, but can anyone explain how exactly it works?

A few related questions that I'm also interested in:

1. Is the wikipedia algorithm really wrong, or am I missing something? And how do they calculate n?
2. I only want to know how many disks are on each peg at a certain move, not on what peg each disk is on, which is what the literature seems to be more concerned about. Is there a simpler way to solve my problem?

Answer 1

1) If your algo says Wikipedia is broken I'd guess you are right...

2) As for calculating the number of disks in each peg, is it pretty straightfoward to do a recursive algorithm for it:

(Untested, unelegant and possibly full of +-1 errors code follows:)

function hanoi(n, nsteps, begin, middle, end, nb, nm, ne)
    // n = number of disks to mive from begin to end
    // nsteps = number of steps to move
    // begin, middle, end = index of the pegs
    // nb, nm, ne = number of disks currently in each of the pegs

    if(nsteps = 0) return (begin, middle, end, nb, nm, ne)

    //else:

    //hanoi goes like
    // a) h(n-1, begin, end, middle) | 2^(n-1) steps
    // b) move 1 from begin -> end   | 1 step
    // c) h(n-1, middle, begin, end) | 2^(n-1) steps
    // Since we know how the pile will look like after a), b) and c)
    // we can skip those steps if nsteps is large...

    if(nsteps <= 2^(n-1)){
        return hanoi(n-1, nsteps, begin, end, middle, nb, ne, nm):
    }
    nb -= n;
    nm += (n-1);
    ne += 1;
    nsteps -= (2^(n-1) + 1);
    //we are now between b) and c)

    return hanoi((n-1), nsteps, middle, begin, end, nm, nb, ne);

function(h, n, nsteps)
    return hanoi(n, nsteps, 1, 2, 3, n, 0, 0)

If you want effieciency, it should try to convert this to an iterative form (shouldn't be hard - you don't need to mantain a stack anyways) and find a way to better represent the state of the program, instead of using 6+ variables willy nilly.

Answer 2

You can make use of the fact that the position at powers of two is easily known. For a tower of size T, we have:

Time          Heights
2^T-1      |  {  0,   0,   T }
2^(T-1)    |  {  0, T-1,   1 }
2^(T-1)-1  |  {  1, T-1,   0 }
2^(T-2)    |  {  1,   1, T-2 }
2^(T-2)-1  |  {  2,   0, T-2 }
2^(T-2)    |  {  2, T-3,   1 }
2^(T-2)-1  |  {  3, T-3,   0 }
          ...
0          |  {  T,   0,   0 }

It is easy to find out in between which those levels your move k is; simply look at log2(k).

Next, notice that between 2^(a-1) and 2^a-1, there are T-a disks which stay in the same place (the heaviest disks). All the other blocks will move however, since at this stage the algorithm is moving the subtower of size a. Hence use an iterative approach.

It might be a bit tricky to get the book-keeping right, but here you have the ingredients to find the heights for any k, with time complexity O(log2(T)).

Cheers