Re: Towers of Hanoi in RPN Message #11 Posted by Thomas Okken on 6 Nov 2010, 6:13 a.m., in response to message #10 by Patrice
I remember looking at the Towers of Hanoi puzzle many years ago, when I discovered a nonrecursive algorithm which I implemented on the HP19C. I don't remember the details, but I do remember that it started when I discovered a simple pattern in the moves for each solution:
1 disc: 13
2 discs: 12 13 23
3 discs: 13 12 32 13 21 23 13
4 discs: 12 13 23 12 31 32 12 13 23 21 31 23 12 13 23
It becomes clearer when you change the destination peg from 3 to 2 for even numbers of discs:
1 disc: 13
2 discs: 13 12 32
3 discs: 13 12 32 13 21 23 13
4 discs: 13 12 32 13 21 23 13 12 32 31 21 32 13 12 32
For odd numbers of discs, you're always moving between pegs 1 and 3, then between 1 and 2, and then between 2 and 3, and then the pattern repeats. For even numbers of discs, the cycle is 1/2, 1/3, 2/3.
I don't remember how I derived the *direction* of each move, though. Of course this is easy to do by keeping track of the discs, but I distinctly remember discovering that that was not necessary. My algorithm must have been similar to Egan's formula, but I don't remember how I solved that last part.
This is going to drive me nuts now. :)
UPDATE:
This refreshed my memory. The key is to notice the pattern of *which disc* is moved. Numbering the discs starting with the smallest being 0, the pattern of disc moves is 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,... In other words, you alternate between moving the smallest disc and some other one; discounting the moves of the smallest disc, you alternate between moving the secondsmallest disc and some other one, etc. This much is easy to verify by looking at the recursive algorithm.
So at move n (starting from 1), you always move the disc m, where m is the lowest nonzero bit in the binary representation of n (with bit b being the one that represents 2^{b}).
Using the 1/3, 1/2, 2/3 pattern I mentioned at the beginning (for odd numbers of discs; for even numbers, use 1/2, 1/3, 2/3), this means that the smallest disc (and all evennumbered discs) must move like 13, 32, 21; the second smallest (and all oddnumbered discs) must move like 12, 23, 31, for odd numbers of discs; for even numbers of discs, just swap pegs 2 and 3.
So, at move n, you must move disc m = floor(log_{2}(n xor (n  1))). How many times has disc m been moved prior to move n? Answer: p = floor((n  1) / 2^{m + 1} + 1/2).
If the sum of the total number of discs and m is odd, you must move from peg 3  (p + 2) % 3 to peg 3  p % 3, and if the sum of the total number of discs and m is even, you must move from peg p % 3 + 1 to peg (p + 1) % 3 + 1.
This is still a bit ugly; we know how to get from the move number, n, to the number of the disc to be moved, m, and how to get from m to the number of times that that disc has been moved previously, p, but we can simplify that by combining those two functions: m(n) = floor(log_{2}(n xor (n  1))) and p(m) = floor((n  1) / 2^{m + 1} + 0.5), so p(m(n)) = floor((n  1) / 2^{1 + floor(log2(n xor (n  1)))} + 1/2) = floor((n  1) / ((n xor (n  1)) + 1) + 1/2), and there you have a function that tells how many times the disc you have to move at move n has been moved previously; combining that with the formula that gives you the source and destination pegs for each disc given how many times it has been moved previously, plus the formula that tells you which disc m to move at any given move n, you have your 100% nonrecursive algorithm.
Proving the 1/21/32/3 pattern and simplifying this mess to Egan's elegant formula is left as an exercise to the reader. :)
Edited: 6 Nov 2010, 9:22 a.m.
