HELP! Need help with this algorithm
Author Message
HELP! Need help with this algorithm

I have to write code to document the steps to the puzzle of the
Tower of Hanoi.  Basically, in this puzzle there are three poles and
rings of increasing size on the 1st pole.  The object is to get the
rings to the 2nd
pole in increasing size, but you can only move one piece at a time,
and a bigger piece can't be on a smaller one.  Example:

Start:

Pole 1     Pole 2    Pole 3
1
2
3
4

Object:

Pole 1     Pole 2    Pole 3
1
2
3
4

You have to use the conditions above

Here is my algorithm:

The disks will always move from 1 to 3 and then back to 1.  But the nth
disk can't change direction to come back until the n+1 disk moves 1
spot.  Example:  3 variable disk1, disk2, disk3 can have value of 0, 1,
or 2 for
the poles 1, 2, and 3 respectively.  Here is the steps for 3 disks.

Disk1, 2, 3 = 0 and you want to end up with Disk 1, 2, 3 = 1
Disk1 =1
Disk 1 =2
Disk 2 =1
Disk 1 = 1
Disk 1=0
Disk2 =2
Disk 1 =1
Disk 1 = 2
Disk 3 =1
Disk 1 = 1
Disk 1 = 0
Disk 2 = 1
Disk 1 =1

My problem is coding the above algorithm, does recursion need to be
used?  Are there some kind of nested for loops with if statements??

Thanks

Mon, 08 Dec 1997 03:00:00 GMT
HELP! Need help with this algorithm

Quote:

>    I have to write code to document the steps to the puzzle of the
>Tower of Hanoi.

etc.

The basic algorithm for towers of Hanoi is:

To move a stack of n disks from pole x to poll y you:
move a stack of n-1 disks to poll z (the poll that isn't x and isn't y).
move the nth disk to poll y.
move the stack of n-1 disks from poll z to poll y.

If n is 1, you can move the disk directly.

This can be coded efficiently using recursion.

Good luck!
Dave
--

AT&T Bell Laboratories    (908)946-1107