Talk:Tower of Hanoi
From Wikipedia, the free encyclopedia
Cool! The algorithm I wrote on Know-How has found its way back here! :-) -- Tarquin 14:03 Dec 14, 2002 (UTC)
What in the world does "the treatment of executive functions" mean? P0M 18:04, 6 Jan 2004 (UTC)
We should keep the spelling consistent in this article. Disk or disc? My vote goes to disc - I use disc for anything other than hard disk and floppy disk. --Decrypt3 18:00, May 23, 2004 (UTC)
I remember that on one episode of Survivor: Thailand, the Tower of Hanoi puzzle was used as an immunity challenge. Should this be included in the article?
Contents |
[edit] Apparent contradiction
There's an apparent contradiction in the entry.
- "The object of the game is to move the entire stack to another peg, obeying the following rules:
'only one disc may be moved at a time' "
- "Recursive algorithm ... 'move nā1 discs from A to C. This leaves disc #n alone on peg A' "
If only one disc may be moved at a time, then moving n-1 discs (where n-1 > 1) is an illegal move.
Or am I missing something here? - 200.141.105.210 20:01, 6 January 2006 (UTC)
- It's recursive: to move the n-1, you just apply the same three rules to the n-1 to move them.
- You eventually just move 1 disc. This could be made clearer, however.
-
- I agree. I'm no expert, but I've done more than the average joe's math and comp. sci, and I can't make heads or tails of that entire section.
[edit] Animated GIFs don't animate
There are two GIFS with 3 disks and 4 disks respectively. The captions indicate that they are animated GIFS that show the solution.
I couldn't get them to animate in Firefox 1.5.04, IE 6.0.2900.xpspblahblahblah or Windows Picture and Fax Viewer (the default viewer in Win XP).
I don't think they are animated GIFs anymore.
Can someone reload the animated GIFs. Otherwise the images have no purpose and will need to be removed.
- looks fine to me, latest firefox. --71.226.119.121 06:31, 29 July 2006 (UTC)
[edit] useless paragraph
I suggest to delete the first paragraph of the section "practical algorithm" which is more complicated than the rest and completely useless; the strategy is simply: "move the smallest one step in a fixed direction (e.g. always clockwise), and then make the only move possible with another disc". ā MFH:Talk 14:26, 12 October 2006 (UTC)
[edit] ...what
"One could thus easily compute the positions of discs in a set of eighty discs after some mole of advancements, if the margin were but large enough to contain it."
This sentence seems irrelevant and is completely out of the blue. Is it supposed to be there? 134.173.200.102 05:10, 23 October 2006 (UTC)
how to find the no. of moves
[edit] four pegs and beyond
It is stated that: "Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four or more pegs is still an open problem." To me this seems incorrect. Represent the problem by an undirected graph, the nodes representing different distributions of disks among the pegs and the branches representing moves. Give each branch length 1. Use Dijkstra's algorithm to find the shortest path from one distribution to another one. It is not difficult to prove that the graph is connected, i.e. that at least one path exists from every node to every other node. Jos.koot 18:10, 5 November 2006 (UTC)JosKoot
- Obviously one can find a solution for any specified number of disks using a brute-force search. However, no general solution is known, and the minimal number of moves, as a function of the number of disks, is also unknown. -- Dominus 20:22, 5 November 2006 (UTC)
A brute force method is a general solution too and does define the minimum number of moves as a function of the number of disks and the number of pegs. Therefore I think the problem cannot simply be said to be open. May be it is ment that a solution in O(nr of required moves) is an open problem. Jos.koot 17:36, 6 November 2006 (UTC)JosKoot
- No, your understanding is at fault here. If you think that the number of moves is a solved problem, please tell me the minimum number of moves required to solve the problem for four pegs and 10,000 disks. -- Dominus 20:48, 6 November 2006 (UTC)
- Here is an analogy that may make the point clearer. It is an open problem whether 286,028,157-1 is a prime number. But the algorithm to decide the question is well-known, obvious, and simple: just divide 286,028,157-1 by every integer from 2 up to 243,014,079 and you are done. Nevertheless, in spite of the easy decision algorithm, it is an open problem, because nobody knows the answer. "Open" does not mean "cannot be solved by a simple method"; it means "unsolved".
- Similarly, nobody knows about the existence of large Latin squares, large discrete projective planes, the size of the Ramsey and van der Waerden numbers, etc., even though special cases of these things can be calculated by simple, search algorithms left to run sufficiently long.
- I hope this helps your understanding of the meaning of "open problem". -- Dominus 20:57, 6 November 2006 (UTC)
Ok, a matter of definition of "open problem". From WikiPedia: "An open problem is a problem that can be formally stated and for which a solution is known to exist but which has not yet been solved." To me this does not seem to include "a problem ... for which an ALGORITHM is known but which has not yet been EFFECTIVELY COMPUTED" If "open problem" is commonly understood as you indicate, I abide by it of course, although I find it confusing calling a problem unsolved even when an algorithm is known (and has been proven to be correct). If I am not mistaken, mathematiciens call a problem unsolvable if and only if no algorithm exists that (in principle) can compute a solution for every instance of the problem. Jos.koot 01:13, 7 November 2006 (UTC)JosKoot
- You are mistaken. I hope this clears up your misunderstanding. -- Dominus 11:13, 7 November 2006 (UTC)
Consider also computing the decimal positional representation of the number 2**(2**(2**(2**(2**(2**(2**(2**2))))))), where ** is the operator of exponentiation. Is this an open problem too?
- Finding the decimal expansion of that number is an open problem. Finding a method for computing it is not an open problem. -- Dominus 11:16, 7 November 2006 (UTC)
How can we claim to have found a method for computation while the computation itself remains an open problem? The problem is of pure practical nature, such as no enough matter being available in the universe for a physical representation of the decimal expansion. I assume that your interpretation of "open problem" agrees with its commonly accepted interpretation. As a matter of taste, I am not pleased with this interpretation, but it would not make sense to argue about taste. Therefore I propose to close this discussion. Thanks for your attention. Jos.koot 20:21, 7 November 2006 (UTC)JosKoot
[edit] Gray code solution
I propose to add after the second paragraph of this section:
- Counting moves from 1 and identifying the disks by numbers starting from 0 in order of increasing size, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2. This is a property of binary gray codes.
Jos.koot 12:53, 10 November 2006 (UTC)Jos Koot
[edit] Long solutions
A modification of the game can be to move the tower from one peg to another peg using as many moves as possible without ever producing the same distribution of disks more than once. A simple algorithm (written in Scheme) is:
(define (long-move-tower height from-peg onto-peg thrd-peg) (if (positive? height) (let ((height-1 (sub1 height))) (long-move-tower height-1 from-peg onto-peg thrd-peg) (move-disk height-1 from-peg thrd-peg onto-peg) (long-move-tower height-1 onto-peg from-peg thrd-peg) (move-disk height-1 thrd-peg onto-peg from-peg) (long-move-tower height-1 from-peg onto-peg thrd-peg))))
Where procedure (move-disk d f t r) moves disk d from peg f onto peg t, ignoring peg r. The number of moves of this uniquely defined solution is 3height-1 and all 3height different distributions of disks are traversed (when including the starting distribution). This is called a Hamilton path. For this solution the disk to be moved can be found with a ternary gray code in a similar way as explained for the shortest solution, which is uniquely defined too.
Another modification is to move a tower from a peg back to the same peg while traversing all distributions of disks. (circular Hamilton path) There are exactly two solutions, but they mirror each other in the sense that there is in fact one path that can be traversed in both directions. Obviously, the length of the path is 3height. A simple algorithm for the circular Hamilton path is:
(define (circular-hamilton-move-tower h a b c) ; h=height. a, b and c are the three pegs. (if (positive? h) ; start with a tower at peg a, move tower to peg b, then to peg c and finally return to peg a. (let ((h-1 (sub1 h))) (hamilton-start h-1 a c b) (move-disk h-1 a b c) (long-move-tower h-1 c a b) (move-disk h-1 b c a) (long-move-tower h-1 a b c) (move-disk h-1 c a b) (hamilton-finish h-1 b a c)))) (define (hamilton-start h a b c) (if (positive? h) (let ((h-1 (sub1 h))) (hamilton-start h-1 a c b) (move-disk h-1 a b c) (long-move-tower h-1 c b a)))) (define (hamilton-finish h a b c) (if (positive? h) (let ((h-1 (sub1 h))) (long-move-tower h-1 a c b) (move-disk h-1 a b c) (hamilton-finish h-1 c b a))))
Jos.koot 12:53, 10 November 2006 (UTC)JosKoot
[edit] Graphical representation
The game can be represented by an undirected graph, the nodes representing distributions of disks and the branches representing moves. For one disk, the graph is a triangle:
/\ /__\
For h+1 disks, take the graph of h disks and replace each small triangle by:
/\
/__\
/ \
/\ /\
/__\__/__\
The above graph is for 2 disks. The angular points of the outermost triangle represent distributions with all disks on the same peg. For 3 disks the graph is:
ccc /\ ccc ; call the pegs a, b and c
acc /__\ bcc ; list disk positions from left to right in order of increassing size
abc / \ bac
/\ /\
bbc /__\__/__\ aac
bba / cbc cac \ aab
/\ /\
cba /__\aba bab/__\ cab
caa / \ / \ cbb
/\ /\ /\ /\
aaa /__\__/__\__/__\__/__\ bbb
baa cca acb abb
bca ccb
Each side of the outermost triangle represent the shortest ways of moving a tower from one peg to another one. The branch in the middle of the sides of the largest triangle represents a move of the largest disk. The branch in the middle of the sides of each next smaller triangle represents a move of each next smaller disk. The sides of the smallest triangles represent moves of the smallest disk. The longest non repetive way for three disks can be visualized by erasing the unused branches:
/\
/ \
/ \
\ /
___\ /___
/ \
/ \
/___ ___\
\ /
/\ \ / /\
/ \_____\ /_____/ \
The circular hamilton path for three disks is:
/\
/ \
/ \
\ /
___\ /___
/ \
\ /
___\ /___
/ \
/ /\ /\ \
/_____/ \__/ \__ __\
Jos.koot 13:47, 10 November 2006 (UTC)JosKoot
[edit] Binary solutions
There is a bug in the algorithm presented in section Binary Solutions. For example:
- 0 : LLLLLLLL, ok
- 1 : LLLLLLLM, ok
- 2 : LLLLLLRL, wrong, must be LLLLLLRM
- 216 : RRMRRLLL, wrong, must be RRLMMLLL
Taking the sense of rotation of the largest disk as +1, the sense of rotation of disk d measured with repect to disk d+1 is -1**z, where z is the number of disks in {h-1, ... d+1} located on the same peg as each first larger disk, h being the total number of disks and considering the largest disk to be on the same peg as a virtual larger disk on the starting peg. The disks are identified by the numbers 0 to h-1 inclusively in order of increasing size.
However, it is true that the sense of rotation of disk d is -1**(h-1-d) with respect to the current location of disk d itself. (again taking the sense of rotation of the largest disk (h-1) to be +1.
Translated into Scheme, the presented (wrong) algorithm gives:
(define (conf m h f t) ; m=move number, h=height of tower, f=starting peg, t=destination peg
(let loop ((prev-zero? #t) (mask (arithmetic-shift 1 (sub1 h))) (rotation (- t f)) (f f))
(if (zero? mask) ()
(let ((zero-bit? (zero? (bitwise-and mask m))) (mask (arithmetic-shift mask -1)))
(if (eq? prev-zero? zero-bit?) (cons f (loop zero-bit? mask (- rotation) f))
(let ((f (modulo (+ f rotation) 3)))
(cons f (loop zero-bit? mask (- rotation) f))))))))
(require (lib "etc.ss"))
(define (list-confs h f t) (build-list (expt 2 h) (lambda (m) (conf m h f t))))
(list-confs 3 0 1) ; --> ((0 0 0) (0 0 1) (0 2 0) (0 2 2) (1 0 0) (1 0 1) (1 1 2) (1 1 1)) wrong
- With my correction
(define (conf m h f t) ; m=move number, h=height of tower, f=starting peg, t=destination peg
(let loop ((prev-zero? #t) (mask (arithmetic-shift 1 (sub1 h))) (rotation (- t f)) (f f))
(if (zero? mask) ()
(let ((zero-bit? (zero? (bitwise-and mask m))) (mask (arithmetic-shift mask -1)))
(if (eq? prev-zero? zero-bit?) (cons f (loop zero-bit? mask (- rotation) f))
(let ((f (modulo (+ f rotation) 3)))
(cons f (loop zero-bit? mask rotation f))))))))
; dont reverse the rotation if disk is on top of previous one
(list-confs 3 0 1) ; --> ((0 0 0) (0 0 1) (0 2 1) (0 2 2) (1 2 2) (1 2 0) (1 1 0) (1 1 1)) ok
Jos.koot 14:58, 11 November 2006 (UTC)JosKoot
[edit] question about number of different ways of moving
Consider the number Nh of different solutions of moving a tower from one peg to another one, disregarding all solutions in which one or more distributions of disks are produced more than once and where h is the number of disks. We have:
- N1=2
- Nh+1=(Nh)2+(Nh)3
This is a very fast increasing series. Does anyone know an analytical expression of Nh in terms of h? Jos.koot 22:53, 12 November 2006 (UTC)JosKoot
[edit] rules
I adapted the rules in the very first section of the article. Without the adaptation the solution is trivial: take the disks from the starting peg one by one and put them aside (without sliding them onto a peg). Then slide the disks onto the destination peg in reversed order. Jos.koot 20:50, 21 November 2006 (UTC)
