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 shoud read the Wikipedia article first.
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=nOne 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 roted 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 remaingng 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 remainding 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 (not proofs!) the correctness of the formula. Have a lot of fun with Tower of Hanoi. -- Clifford