The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

Towers of Hanoi in RPN
Message #1 Posted by Kiyoshi Akima on 2 Nov 2010, 1:42 p.m.

Has anyone written an RPN program for the Towers of Hanoi that's theoretically capable of handling the full 64-disk configuration? Or must I finish mine?

There's one for the 32S in the software library for up to six disks and V had a 16C program for up to thirty-some disks, but I haven't seen one that can theoretically handle 64.

It's all but trivial in RPL, but in RPN without local variables and without adequate inbuilt support for recursion... And, of course, I don't expect the batteries to last long enough, and I'm not going to check the full results...

      
Re: Towers of Hanoi in RPN
Message #2 Posted by Patrice on 2 Nov 2010, 2:15 p.m.,
in response to message #1 by Kiyoshi Akima

Hi, Can you post the program for the 16C or an URL to the program.

Knowing the 16C, I don't see why it could not be able to handle 64 discs (theoricaly :) ).

The only problem I see is the lack of speed to achieve the full move. My only hope is to have an 12C+ re-purposing to a 16C on last hardware (just dreaming).

I suspect 30 disc is already out of reach for the 16C.

Patrice

            
Re: Towers of Hanoi in RPN
Message #3 Posted by Patrice on 2 Nov 2010, 6:58 p.m.,
in response to message #2 by Patrice

Hi,

I found the program with google!

HP 16C article with Hanoi towers program

      
Re: Towers of Hanoi in RPN
Message #4 Posted by Egan Ford on 2 Nov 2010, 6:37 p.m.,
in response to message #1 by Kiyoshi Akima

I'll write one, but what must a ToH program do? Just count from 1 to 2^d - 1. The source peg is (count & (count - 1)) % 3 and the target is ((count | (count -1)) + 1) % 3.

Edited: 2 Nov 2010, 6:39 p.m.

            
Re: Towers of Hanoi in RPN
Message #5 Posted by Egan Ford on 2 Nov 2010, 11:23 p.m.,
in response to message #4 by Egan Ford

Quote:
I'll write one, but what must a ToH program do?
Ok, based on the 16C example above, a ToH program should walk you through solving ToH.

Below is my version that will work for up to 64 discs on the 16C based on the equations I posted above.

Just GSB 0, then a 2 digit number will be displayed. The first number is the source rod and the second digit is the target rod. Press R/S to get the next set of numbers. This will solve any number of discs up to 64. Just keep pressing R/S until your problem is solved. For the case of 64, when the counter reaches 0, 0 will be displayed indicating that the 64 disc solution is solved.

Example output for 3 discs (23-1 moves):

13
12
32
13
21
23
13

Code:

001 - 43,22, 0  LBL 0                
002 -    42  3  SET COMPL UNSGN      
003 -       24  DEC                  
004 -        6  6                    
005 -        4  4                    
006 -    42 44  WSIZE                
007 -        0  0                    
008 -    44  0  STO 0                
009 - 43,22, 1  LBL 1                
010 -    45  0  RCL 0                
011 -        1  1                    
012 -       40  +                    
013 -    43 40  x=0                  
014 -    22  2  RTN                
015 -    44  0  STO 0                
016 -    45  0  RCL 0                
017 -        1  1                    
018 -       30  -                    
019 -    42 20  AND                  
020 -        3  3                    
021 -    42  9  RMD                  
022 -        1  1                    
023 -       40  +                    
024 -        1  1                    
025 -        0  0                    
026 -       20  x                    
027 -    45  0  RCL 0                
028 -    45  0  RCL 0                
029 -        1  1                    
030 -       30  -                    
031 -    42 40  OR                   
032 -        1  1                    
033 -       40  +                    
034 -        3  3                    
035 -    42  9  RMD                  
036 -        1  1                    
037 -       40  +                    
038 -       40  +                    
039 -       31  R/S                  
040 -    22  1  GTO 1                

Edited: 2 Nov 2010, 11:46 p.m.

                  
Re: Towers of Hanoi in RPN
Message #6 Posted by Egan Ford on 3 Nov 2010, 12:30 a.m.,
in response to message #5 by Egan Ford

I should have stated my admiration for the 16C. What an awesome machine!

                        
Re: Towers of Hanoi in RPN
Message #7 Posted by Patrice on 5 Nov 2010, 6:16 p.m.,
in response to message #6 by Egan Ford

Welcome to the club :)

                  
Re: Towers of Hanoi in RPN
Message #8 Posted by Kiyoshi Akima on 12 Nov 2010, 12:16 p.m.,
in response to message #5 by Egan Ford

I believe there's a bug in this program, one that only shows when doing 64 disks. And no, I don't blame Egan for not running this case to its completion :-)

Halfway through, when it's finally time to move the biggest disk:

count              = 8000000000000000h
count-1            = 7FFFFFFFFFFFFFFFh
count or (count-1) = FFFFFFFFFFFFFFFFh
then (count or (count-1)+1) overflows. (2^64)mod 3 is 1 but the 16C, having lost the top bit, produces 0.

A partial fix is to replace the 1, + in lines 32-33 with 2, -. This will make it work correctly for the 64-disk case but the underflow screws up the 1-disk case.

                        
Re: Towers of Hanoi in RPN
Message #9 Posted by Egan Ford on 12 Nov 2010, 5:09 p.m.,
in response to message #8 by Kiyoshi Akima

Here's a quick fix. I'll try to think of something better this weekend.

Replace:

((count | (count -1)) + 1) % 3

with:

((count | (count -1)) % 3 + 1) % 3

            
Re: Towers of Hanoi in RPN
Message #10 Posted by Patrice on 5 Nov 2010, 6:17 p.m.,
in response to message #4 by Egan Ford

Hi Egan,

Quote:
Just count from 1 to 2^d - 1. The source peg is (count & (count - 1)) % 3 and the target is ((count | (count -1)) + 1) % 3.

Where did you find this formula ?

Patrice

                  
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 non-recursive algorithm which I implemented on the HP-19C. 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:  1-3
2 discs: 1-2 1-3 2-3
3 discs: 1-3 1-2 3-2 1-3 2-1 2-3 1-3
4 discs: 1-2 1-3 2-3 1-2 3-1 3-2 1-2 1-3 2-3 2-1 3-1 2-3 1-2 1-3 2-3

It becomes clearer when you change the destination peg from 3 to 2 for even numbers of discs:

1 disc:  1-3
2 discs: 1-3 1-2 3-2
3 discs: 1-3 1-2 3-2 1-3 2-1 2-3 1-3
4 discs: 1-3 1-2 3-2 1-3 2-1 2-3 1-3 1-2 3-2 3-1 2-1 3-2 1-3 1-2 3-2

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 second-smallest 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 2b).

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 even-numbered discs) must move like 1-3, 3-2, 2-1; the second smallest (and all odd-numbered discs) must move like 1-2, 2-3, 3-1, 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(log2(n xor (n - 1))). How many times has disc m been moved prior to move n? Answer: p = floor((n - 1) / 2m + 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(log2(n xor (n - 1))) and p(m) = floor((n - 1) / 2m + 1 + 0.5), so p(m(n)) = floor((n - 1) / 21 + 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% non-recursive algorithm.

Proving the 1/2-1/3-2/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.

                  
Re: Towers of Hanoi in RPN
Message #12 Posted by Egan Ford on 8 Nov 2010, 12:53 p.m.,
in response to message #10 by Patrice

Quote:
Where did you find this formula ?
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solutions
      
Re: Towers of Hanoi in RPN
Message #13 Posted by Juergen Keller on 3 Nov 2010, 3:16 a.m.,
in response to message #1 by Kiyoshi Akima

There is also one in the software library for the 42S with graphical display of the disk moves:

Towers of Hanoi

Enjoy, Juergen

            
Re: Towers of Hanoi in RPN
Message #14 Posted by Kiyoshi Akima on 3 Nov 2010, 10:30 a.m.,
in response to message #13 by Juergen Keller

The 42S program apparently only handles up to 7 disks.

I'm putting on the finishing touches on a pair of 35s programs that will handle up to 64 disks each, using different algorithms. I also have a 27-step program for the 16C.

I hadn't seen Egan's formulae before. They sure make the thing easy, don't they?

                  
Re: Towers of Hanoi in RPN
Message #15 Posted by Juergen Keller on 3 Nov 2010, 1:26 p.m.,
in response to message #14 by Kiyoshi Akima

The 7-disk limitation is only because of the limited 42S graphics capabilities. The algorithm itself - which is non-recursive - can handle more disks ...

      
Re: Towers of Hanoi in RPN
Message #16 Posted by Kiyoshi Akima on 16 Nov 2010, 3:07 p.m.,
in response to message #1 by Kiyoshi Akima

Since I started this thread, I suppose I have to contribute my code to it. Here are ten programs for the full 64-disk Towers of Hanoi puzzle including RPN programs for the 35s, 30b, 16C, and 15C. The 30b is by far the fastest of this lot.

            
Re: Towers of Hanoi in RPN
Message #17 Posted by Thomas Klemm on 17 Nov 2010, 6:16 a.m.,
in response to message #16 by Kiyoshi Akima

Very nice paper! Thanks a lot for sharing.

However I assume there's a typo in the recursive RPL program:

Quote:
n 1. = t d s \<-h EVAL

Should be:

n 1. - t d s \<-h EVAL

Kind regards
Thomas

                  
Re: Towers of Hanoi in RPN
Message #18 Posted by Kiyoshi Akima on 17 Nov 2010, 12:14 p.m.,
in response to message #17 by Thomas Klemm

Thanks. I've corrected that and fixed some other transcription errors in the 30b version.

                        
Re: Towers of Hanoi in RPN
Message #19 Posted by Thomas Klemm on 17 Nov 2010, 4:54 p.m.,
in response to message #18 by Kiyoshi Akima

Unfortunately I have also trouble with iterative RPL program:

Quote:
UNROT OR #2d - DUP #3d / #3d x

Here I assume a minus is missing at the end. I've also changed the #2d - to #1d + though I know what you possibly had in mind. But I prefer to have the first move displayed correctly in all cases than having the last one in the special case of n=64.

In the condition of the do-loop I simply use:

UNTIL
  DUP2 ==
END

Otherwise the program did not end.

There's a minor typo on page 7: 234 mod 2 = 1

Probably you mean: 234 mod 3 = 1. At least that would make sense in this context.

Cheers
Thomas

Edited: 17 Nov 2010, 5:01 p.m.

                        
Re: Towers of Hanoi in RPN
Message #20 Posted by Katie Wasserman on 17 Nov 2010, 10:00 p.m.,
in response to message #18 by Kiyoshi Akima

Excellent writeup and programming work! Why not post this in the articles section here to make it more accessible to everyone?

-Katie

                              
Re: Towers of Hanoi in RPN
Message #21 Posted by Kiyoshi Akima on 18 Nov 2010, 12:35 a.m.,
in response to message #20 by Katie Wasserman

I'd like to, but it's going to take some time unless I can find a good way to convert a LaTeX document to HTML. Any suggestions?

                                    
Re: Towers of Hanoi in RPN
Message #22 Posted by Thomas Klemm on 18 Nov 2010, 4:39 a.m.,
in response to message #21 by Kiyoshi Akima

cf. Advanced Article Formatting

Quote:
If you don't have a place to host your images, then please log in and request a guest directory. Once the directory is created, you will be able to upload your files. (This is actually preferred since I won't have to worry about the images moving or disappearing in the future and leaving broken links.)

Create an article with a short abstract and provide a link to the PDF. It's not possible to upload HTML anyway.

How did you create the nice listings in LaTeX?

Best regards
Thomas

                                          
Re: Towers of Hanoi in RPN
Message #23 Posted by Kiyoshi Akima on 18 Nov 2010, 12:39 p.m.,
in response to message #22 by Thomas Klemm

Quote:
How did you create the nice listings in LaTeX?

Very carefully. Below is an excerpt from the 30b version.

\noindent\begin{tabular}{|rl|rl|rl|rl|}
\hline
\textsf{  1}&\textsf{Input}              &\textsf{ 29}&\textsf{2}                  &\textsf{ 57}&\textsf{EEX}                &\textsf{ 85}&\textsf{RCL Data}           \\
\textsf{  2}&\textsf{0}                  &\textsf{ 30}&\textsf{Call04}             &\textsf{ 58}&\textsf{2}                  &\textsf{ 86}&\textsf{EEX}                \\
...
\textsf{ 26}&\textsf{*}                  &\textsf{ 54}&\textsf{Math}               &\textsf{ 82}&\textsf{\underline{Lbl 03}} &\textsf{110}&\textsf{Up}                 \\
\textsf{ 27}&\textsf{RCL Data}           &\textsf{ 55}&\textsf{Up}                 &\textsf{ 83}&\textsf{Call04}             &\textsf{111}&\textsf{Input}              \\
\textsf{ 28}&\textsf{EEX}                &\textsf{ 56}&\textsf{Input}              &\textsf{ 84}&\textsf{+}                  &\textsf{112}&\textsf{RTN}                \\
\hline
&\multispan{6}\textsf{\hfil \ length/checksum = 142.056\hfil}&\\
\hline
\end{tabular}\label{prog.30b.r}

There are easier ways, and I have some scripts that handle numbering and columnating (is that a word?).

            
Re: Towers of Hanoi in RPN
Message #24 Posted by Angel Martin on 17 Nov 2010, 3:26 p.m.,
in response to message #16 by Kiyoshi Akima

Indeed a great contribution, thanks for sharing it.

I don't suppose you could also add another version for the 41, or could you? I remember your original contributions to the PPC journal on the same subject, so it's been a while since then and it's great to see how you've come full circle :)

Best, 'AM

                  
Re: Towers of Hanoi in RPN
Message #25 Posted by Kiyoshi Akima on 18 Nov 2010, 12:33 p.m.,
in response to message #24 by Angel Martin

Quote:
I remember your original contributions to the PPC journal on the same subject, so it's been a while since then and it's great to see how you've come full circle :)

Thanks for making me feel old. And to make me even older, I can't remember writing for the PPCJ about the Towers of Hanoi. Eight Queens, yes. The Game of Life, yes. The Towers, no.

As for the 41 (and I presume, the 42), it's simple to translate the first (recursive) 35s program. Number the black triangles showing the destinations of branches. Type in the program and put in the labels where needed. Instead of variable I, use register R00 so that DSE I becomes DSE 00, RCL(I) becomes RCL IND 00, and so forth. Or use synthetics and use M or N. IP is INT and RMDR is MOD. I didn't include a 41 program because I don't have a working 41 and I didn't want to use an emulator (all of the programs were done on the actual hardware).

For a bare-bones 41 without additional memory, use the 15C program, using R33 for RAN#.

I still want to shoehorn the program into the 19C/29C. A 12C version would be fun, as well.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall