This formula can be used to calculate any of the 2n-1 states of a Tower of Hanoi game in constant time. The variables have the following meaning:
|s||Stack number (0 = left, 1 = middle, 2 = right)|
|m||Move number (0 = initial state)|
|d||Disk number (1 = topmost disk)|
|n||Total number of disks|
If you are not sure what the Tower of Hanoi game is at all you should read the Wikipedia article first.
What is this formula about?
According to a legend the priests of Brahma are playing a Tower of Hanoi game with 64 disks. Unfortunately the world will end when the last move of their game has been made. Fortunately a Tower of Hanoi game with 64 disks needs about 585 billion years when one is moving one disk per second and our sun will evolve into a red giant and then a white dwarf in about 5 billion years, so you we shouldn't worry about the priests of Brahma finishing the game before you have finished whatever you think is important to finish in a mens life. Unless of course the priests of Brahma do use the information here to play wrong..
Many people have published algorithms for solving a towers of Hanoi game move by move. However – solving a Tower of Hanoi game with 64 disks move by move needs a long time and so one might want a solution for skipping a few billion moves. In order to do so one just needs an algorithm to calculate the state (positions of all disks) of the game for a given move number. That is was my formula is doing.
The priests of Brahma might not necessarily use this formula to accelerate the process. I don't think that bringing the world to an early end is in their interest. However – moving disks all day might be getting boring soon and so the priests could just calculate the a position to skip 28800 steps (the number of moves that would be performed in an 8 hour shift with a rate of one move per second), rearrange the disks accordingly to the results and then take the rest of the day off.
How does it work?
I assume that you are familiar with the classic recursive Hanoi algorithm:
procedure hanoi_move(from, temp, to, disks): if disks > 1: hanoi_move from=from temp=to to=temp disks=disks-1 move_disk from=from to=to disk_number=disks if disks > 1: hanoi_move from=temp temp=from to=to disks=disks-1 hanoi_move from=0 temp=1 to=2 disks=n
One can easily see that with every recursion level the order of the stacks a disk is visiting changes between 0-1-2 (rotate right) and 0-2-1 (rotate left). One can also easily see that the same disk is always moved at the same recursion level. So a disk is either always moved to the right or to the left and so once we know how often a disk has been moved we do know its position.
This term evaluates to 1 for disks that are rotated right (0-1-2) and 2 for disks that are rotated left (0-2-1). It is obvious that we just need to multiply that with the number of moves for the disk and take the result modulo 3 to get the position of the disk. And that's exactly what I am doing in my formula:
So there is only one subterm remaining that might look like black magic on the first glimpse. The one that calculates the number of moves for a disk (in the case you are wondering: the
marks a floor operation):
See how it works? No? Read on.
As one can easily see by looking at the recursive algorithm, the topmost disk will be moved every 2nd move. The algorithm is recursive, so just go backwards (top-down) thru the recursion levels and you will see that in all remaining moves the topmost remaining disk will be moved every 2nd move. So disk d will always be moved every 2d moves.
Instead of iterating over all the moves and checking if this move is one of the moves for this disk we also can use a more efficient term using the floored division:
Remains the question: „What's this 2d-1 in the dividend?“ Just keep the previous observations from the recursive algorithm in mind and have another look at it from the bottom-up perspective. You will see that the algorithm starts exactly in the middle of the ‚move this slide every 2d moves‘ phases. So we have to add the half of the divisor to the dividend:
Here is the complete formula again. Go thru it a last time: Now the inner mechanics of the formula should be absolutely clear.
This little SPL script demonstrates (but doesn't prove!) the correctness of the formula.
Have a lot of fun with Tower of Hanoi. — Clifford