| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Peter Gilbert recently asked me if I knew of any work done on the classic Tower of Hanoi problem when there are more than 3 pegs. I came up with the following reference for him: Brother Alfred Brousseau, Tower of Hanoi with More Pegs. Journal of Recreational Mathematics. 8(1975-1976)169-176. Brousseau comes up with some recursion formulae for the minimum number of moves needed. I've seen lots of computer programs around DEC for the classic case of 3 pegs. Does anyone out there have any program that uses more than 3 pegs?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 8.1 | TURTLE::GILBERT | Tue Jan 24 1984 01:40 | 5 | ||
Indeed, I do. It minimizes the number of moves. Although Brousseau's formulae minimize the number of moves, they are given without proof that they are minimal. The problem is for a simple way to prove the recurrence relations. | |||||
| 8.2 | RANI::LEICHTERJ | Wed Jan 25 1984 00:50 | 14 | ||
For a fascinating "different approach" to the Tower of Hanoi, see "Pattern Analysis as a Tool for Inventing Algorithms", by Richard Hart (Software - Practice and Experience, V10, pg. 405-417 (1980)). He gives a non-recursive "closed-form" algorithm, which reads as follows "Move the smallest piece to the next spindle on the left. Then make the only other move possible. Repeat, always moving the smallest disk in a circle - 3 to 2 to 1 to 3..." The spindles are 1,2,3 = start, spare, finish, left to right. The same paper also contains the strangest date conversion algorithm you ever saw, and a description of a new sort that is alleged to be the fastest one known. All programs are given in uncommented, very basic BASIC (letter and letter-digit variable names, for example); the sort program is totally incomprehensible (to me). -- Jerry | |||||
| 8.3 | REX::POWERS | Thu Feb 23 1984 17:34 | 6 | ||
There is another interesting approach, though not as rigorous, in the October 1983 "Computer Recreations" column in Scientific American. The thrust of the column is directed to 'associative processing' aka spreadsheets in genericalc. The question is asked, but not pursued, regarding whether there is a non-algorithmic approach to the Towers of Hanoi problem. | |||||
| 8.4 | TURTLE::GILBERT | Wed Apr 04 1984 18:02 | 8 | ||
For the 3-spire version of the Towers of Hanoi, consider the following non-procedural solution: Never move the same disk twice in a row. Never place an odd-width disk on an odd-width disk. Never place an even-width disk on an even-width disk. This assumes that there is a solution to the problem! | |||||
| 8.5 | TURTLE::GILBERT | Wed Apr 04 1984 18:08 | 4 | ||
I'm still interested in a proof that recurrence relation or procedure gives the smallest number of disk moves for the case of 4 or more spires. Any takers? | |||||
| 8.6 | HARE::STAN | Mon May 14 1984 16:47 | 4 | ||
An optimality proof can be found in Helmut Jurgensen and Derick Wood, The Multiway Trees of Hanoi, Intern. J. Computer Math, 14(1983)137-153. | |||||
| 8.7 | TURTLE::GILBERT | Sun Aug 05 1984 08:10 | 17 | ||
The "Multi-way Trees of Hanoi" describes a generalization of the Towers of Hanoi which allows several small disks (of the same size) to sit atop a larger disk. For example: 1 1 1 1 1 1 1 1 1 ==2== ==2== ==2== ========3======== This one requires at least 6 "places" (counterparts of spires in vanilla Hanoi) to move the tree. Unfortunately, the reference only considers having the fewest possible number of places which allow the movement. The request for proof of a recurrence giving the minimal number of moves for four or more spires is still open. - Gilbert | |||||