Hanoi configuration on a certain move

Question

I am interested to know how many disks are on each binding for a given movement in the puzzle of the tower of Hanoi . For example, when using n = 3 disks, we have this sequence of configurations for the optimal puzzle solution:

  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, for this step number 5, I want to return 1 1 1 , given the number 6, I want 1 0 2 , etc.

This is easy to do using the classic algorithm and stopping it after a certain number of moves, but I want something more efficient. The wikipedia page I linked to above gives the algorithm in the Binary solutions section. I think it's wrong. I also do not understand how they calculate n .

If you follow their example and convert the positions of the disk, it returns to what I want, it gives 4 0 4 for n = 8 disks and moves the number 216 . However, using the classic algorithm, I get 4 2 2 .

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

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

A few related questions that also interest me:

• Is the wikipedia algorithm really wrong, or am I missing something? And how do they calculate n ?
• I just want to know how many disks are on each binding for a certain move, and not what each disk binds to, and this is what the literature seems to be more worried about. Is there an easier way to solve my problem?

Answer 1

1) If your algo says that Wikipedia is broken, I think you're right ...

2). As for calculating the number of disks in each binding, it is quite easy to make a recursive algorithm for it:

(Unverified, inelegant, and possibly complete error code + -1:

 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 to increase efficiency, he should try to convert it to iterative form (it should not be difficult - you don’t have to stack it at all) and find a way to better represent the state of the program, instead of using 6 + willy nilly variables.

Answer 2

You can use the fact that the position in 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 between which levels your move is k; just look at log2 (k).

Then note that between 2 ^ (a-1) and 2 ^ a-1 there are Ta disks that remain in the same place (the heaviest disks). However, all other blocks will move, since at this stage the algorithm moves the subtraction of size a. Therefore, use an iterative approach.

It might be a little difficult to get an accounting right, but here you have the ingredients to find the heights for any k, with a time complexity of O (log2 (T)).

Greetings

Answer 3

 If you look at the first few moves of the puzzle, you'll see an important pattern. Each move (i - j) below means on turn i, move disc j. Discs are 0-indexed, where 0 is the smallest disc. 1 - 0 2 - 1 3 - 0 4 - 2 5 - 0 6 - 1 7 - 0 8 - 3 9 - 0 10 - 1 11 - 0 12 - 2 13 - 0 14 - 1 15 - 0 

Disk 0 moves every 2 turns, starting from turn 1. Disk 1 moves every 4 turns, starting from turn 2 ... Disk I moves every 2 ^ (i + 1), turns, starting from turn 2 ^ i.

So, in constant time, we can determine how many times a given disk has moved, given m:

move = (m + 2 ^ i) / (2 ^ (i + 1)) [integer division]

The next thing to note is that each disk moves cyclically. Namely, disks with an odd number move to the left each time they move (2, 3, 1, 2, 3, 1 ...), and even disks move to the right (1, 3, 2, 1, 3, 2. ..)

So, as soon as you know how many times the disk has moved, you can easily determine which icon it ends with by accepting mod 3 (and doing a bit of calculation).