Clifford’s Tower of Hanoi Formula

This formula can be used to calculate any of the 2ⁿ-1 states of a Tower of Hanoi game in constant time. The variables have the following meaning:

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):

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 2^d 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 2^d-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 2^d 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