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

variable | description |
---|---|

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.

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.

procedure hanoi_move(from, temp, to, disks): ifOne 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.disks> 1: hanoi_move from=fromtemp=toto=tempdisks=disks-1 move_disk from=fromto=todisk_number=disksifdisks> 1: hanoi_move from=temptemp=fromto=todisks=disks-1 hanoi_move from=0 temp=1 to=2 disks=n

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 thisHave a lot of fun with Tower of Hanoi. -- Clifford