# Talk:Tower of Hanoi

## A new monography

Quite recently a new monography entitled "The Tower of Hanoi - Myths and Maths" (see: http://www.amazon.com/The-Tower-Hanoi-Myths-Maths/dp/3034802366) was published written by Andreas M. Hinz, Sandi Klavzar, Uros Milutinovic and Ciril Petr. It is written in a clean and precise way (mathematically rigorous) and is a great source of information. — Preceding unsigned comment added by 2001:1470:FFF0:810:A2E:5FFF:FE31:C01B (talk) 11:37, 15 May 2013 (UTC)

Monograph” --77.169.168.165 (talk) 15:23, 27 July 2014 (UTC)

## Untitled

The total time for 64 disks seems miscalculated (or overly precise): an average year has approximately 365.25 days, not 365 days. Therefore, it seems better to write that it takes roughly 585 billion years. That also avoids the confusing (to foreigners) decimal point. On first glance, I first read 585.442 as approx. half a million. —Preceding unsigned comment added by 131.155.71.129 (talk) 07:17, 9 October 2007 (UTC)

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?

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.
Perhaps it would be better explained as:
To move n disks from peg A to peg B:
1. Apply this algorithm for moving n−1 disks from A to C. This leaves the nth disk alone on peg A;
2. Move the nth disk from A to B;
3. Apply this algorithm for moving n−1 disks from C to B so they sit on the nth disk. Smithers888 15:29, 3 June 2007 (UTC)

## Short non-recursive solution

There is a short non-recursive algorithm to solve the standard game:

In alternate moves:

• move the smallest disk to the peg it has not recently come from
• move another disk legally

To decide the first ever move, move the smallest disk to the target final destination peg if there are an odd number of disks, and to the non-target peg if there are an even number. --Audiovideo 19:40, 25 March 2007 (UTC)

There is another way to put this which does not seperate the smallest disc as being different to the rest:
On each move, perform the unique legal move which satisfies the following:
• It does not simply reverse the previous move,
• It does not put an odd numbered disc on an odd numbered disc, or an even numbered disc on an even numbered disc.
For the first move: if there are an odd number of discs move the smallest disc to the target peg; if there are an even number of discs move the smallest disc to the intermediate peg.Smithers888 15:29, 3 June 2007 (UTC)

## 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)

## 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)

## ...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)

I think it's a joke.— MFH:Talk 01:16, 25 October 2006 (UTC)
Indeed, it looks like a joke; it doesn't look adequate to an encyclopedia article. In fact, the whole "Binary solutions" section needs to be rewritten with a better wording; the comments in the scheme code also don't help. It looks more like it was copy-pasted from some article instead of being written for wikipedia. I'll make some minor editing to try to make it more serious and clear. DanielKO 04:14, 26 January 2007 (UTC)

how to find the no. of moves

Jos.koot 20:55, 27 July 2007 (UTC) The Scheme examples are from my hand and not copy pasted from other articles (except my own). Jos.koot 20:55, 27 July 2007 (UTC)

## 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

## 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.

Jos.koot 12:53, 10 November 2006 (UTC)Jos Koot

## 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

## 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

Can these be SVGified? No offense, but ASCII art looks pretty unprofessional. 70.88.111.65 12:18, 5 June 2007 (UTC)
I have created SVGs of these - any comments? Should they be inserted as-is or does anyone want to suggest improvements/reckon the ASCII is better? Smithers888 (talk) 05:37, 28 January 2008 (UTC)

ToHGraph1.svg

ToHGraph2.svg

ToHGraph3.svg

ToHGraph3Long.svg

ToHGraph3Hamiltonian.svg

Thanks, The graphs look great. Jos.koot (talk) 15:24, 14 April 2009 (UTC)

Jos.koot 20:52, 27 July 2007 (UTC)JosKoot I agree insofar the graphs should be presented in a better shape. I have programs that produce the graphs in a neat form, but I dont know (and dont want to know) how to carry these into this article. Jos.koot 20:52, 27 July 2007 (UTC)JosKoot

## Binary solutions

There is a bug in the algorithm presented in section Binary Solutions. For example:

1. 0  : LLLLLLLL, ok
2. 1  : LLLLLLLM, ok
3. 2  : LLLLLLRL, wrong, must be LLLLLLRM
4. 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

## 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

## 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)

## Recursive Algorithm

I just removed the old C code (that is from "Programming=++Algorithms;"). Even though the code is distributed gratis, it doesn't contain any term of use, copyright notice, nothing. We should not assume that it's public domain, nor that the copyright holder(s) allow its use here. So I just replaced it with my (not worse, I hope) implementation. I also added the implementation to solve the problem from a generic initial configuration.

I also removed the informal explanation of the algorithm; the formal explanation itself, although complete, is not very clear. The informal explanation added nothing but confusion (you would look for the "Explanation" title and would be lured to not look where the real explanation is).

In all, the article needs to be re-structured. There are too many bulleted lists, and too little continuation. The Scheme samples also don't help to clarify. I'll try to do it when I have time, trying to not lose any information. DanielKO 12:25, 27 January 2007 (UTC)

There should be implemetation in java or c++ since those are the two most commonly used coding languages —Preceding unsigned comment added by 76.190.134.238 (talk) 03:25, 2 November 2008 (UTC)

## Scheme examples

I find the Scheme examples very instructive and clear, particularly because they are complete and can be copy/pasted and run without any ado. Jos.koot 20:40, 18 July 2007 (UTC) JosKoot

## Mayor revision

I streamlines the article by choosing consistent variable names in the various examples (some examples are still left to be streamlined) I also moved the recursive algorithms up such as to preceed the non recursive algorithms (as they did earlier) The non recursive algorithms cannot be understood without knowledge of the recursive algorithm. Furthermore the proofs of the non recursive algorithms are recursive. In some cases the correctness of an algorithm is wel argumented. I think that this article is not the right place for rigid proofs. Furthermore, such proofs are nice exercises for the reader. Jos.koot 10:57, 26 July 2007 (UTC)JosKoot

## Is it so easy?

I object to the following sentence:

By means of mathematical induction it is easily proven that the above procedure requires the minimal number of moves possible and that the produced solution is the only one with this minimal number of moves.

If it is so easy, the proof should be given. —Preceding unsigned comment added by 147.231.88.1 (talk) 12:29, August 28, 2007 (UTC)

I don't think the article should include the proof. The following proves my statement easily:

Let h be the number of disks, a the starting peg, b the destination peg and c the third peg. Let Sh be the statement that the algorithm produces the shortest path for h disks and that this path is uniquely defined. Let Nh be the number of moves. Use mathematical induction on h. S1 is obvious and N1=1. Suppose Sh. Yet to prove: Sh+1: The greatest disk can be moved only after all smaller disks have been moved from a to either b or c. After moving the largest disk, all smaller disks must be moved again. Hence the minimal number of moves required is at least 2Nh + 1. This minimal number can only be obtained when first the smaller disks go from a to c, then the largest from a to b and finally the smaller disks from c to b. The option to start with moving the smaller disks from a to b obviouly takes more moves (at least 3Nh + 1). The path for h+1 disks is uniquely defined, because the move of the greatest disk is uniquely defined and moving the smaller disks from a to c and from c to b is minimal and uniquely defined by induction hypothesis Sh. QED Jos.koot (talk) 13:22, 9 December 2007 (UTC)

## Cleanup October 2007

14-Oct-2007: I have made several dozen minor changes to cleanup the tone/format of the article:

• reworded 6 instances of using "we" or "you" in phrases;
• converted to complete sentences, such as with "how to";
• in the first recursion solution, bolded peg letters f/t/r;
• added commas in text, and added periods after webpage links;
• untagged for the "{{cleanup-tone}}" tag.

Please fix any remaining problems of wording. Thanks. -Wikid77 06:14, 14 October 2007 (UTC)

## Vandalism

I've noticed there was a lot of vandalism, so I asked to semi-protect it. Jerr (talk) 04:08, 16 January 2008 (UTC)

User:207.176.6.111 helpfully removed implementations in Java, Scheme, Haskell, SML, C and Python, leaving only the interesting ones: PL/I and OCaml!??? Someone caring for the article should put them back.

## The Pascal code is incorrect.

You can't use the reserved word 'to' in Pascal as a variable name.

That code will not compile. Change 'from' and 'to' with something else.

## Too many programming languages

There are currently full-fledged code examples for the following nine (!) languages: OCaml, PL/1, JavaScript, Ruby, Java, Scheme, C, Pascal and VB.NET. Most of these languages are not bringing anything new to the article - there is no difference between the JavaScript, Ruby and VB.NET implementations, or between the Java, C and Pascal versions. Accordingly, I would propose the following:

1. Retain one functional language, probably OCaml for its brevity, and state explicitly that it is a functional approach.
2. Retain one imperative language, maybe Pascal, and state explicitly that it is a recursive imperative approach.
3. Delete the recursive Scheme example (nothing new for this article compared to the OCaml version), but retain Scheme in iterative and long solutions.
4. Refer people who are searching for an implementation in their favorite language to the Hanoimania website, which is already listed in the External links section.
5. Not add new languages unless they are representative of a new type of programming that is not currently represented in the article and which contribute something more than just a different syntax.

-- Brhaspati\talk/contribs 17:50, 5 May 2008 (UTC)

I just pruned the list. If you feel that OCaml or Pascal should be replaced by another functional or imperative language, please do so, but make sure that you don't have more than one language of a given type. Regarding Scheme - since it's a multiparadigm language, if you have an implementation that cannot be covered with a pure functional language, please feel free to add it. -- Brhaspati\talk/contribs 18:01, 5 May 2008 (UTC)

## Java code sample is incorrect or confusing.

  if (numRings == 1)
System.out.println("Move from peg " + source + " to " + temp + ".");


Why if there only one ring, we move it to temporary rod? Alt-sysrq (talk) 20:51, 15 June 2008 (UTC)

## Removing Solution Animation

The animated solution is interesting, but it could potentially spoil the game for someone who would like to figure it out on their own. I think it should be moved to its own section, its own page, or removed. --Elplatt (talk) 03:26, 15 August 2008 (UTC)

Would a collapsed table that requires the user to click "show" be an acceptable compromise? Something like:
-- Tcncv (talk) 04:32, 2 November 2008 (UTC)
See WP:SPOILER -- it is expected that Wikipedia articles will have information, and if you want to solve the puzzle on your own you shouldn't look up Wikipedia. For what it's worth, I think it is an excellent animation and one of the best pictures on Wikipedia :P Shreevatsa (talk) 17:32, 2 November 2008 (UTC)
Sounds reasonable. It was not my intention to advocate the hidden picture, only to offer a technical option up for consideration. But you are right, there is no real need to change the image. -- Tcncv (talk) 18:53, 2 November 2008 (UTC)

## Non-recursive

The article is missing a clean (well, relatively) iterative implementation. One would think that's what Tower_of_Hanoi#Non-recursive_solution provides, but that's not really true. There should be a simple code or psuedo-code implementation. I will try to write it myself if I have time. Superm401 - Talk 12:33, 23 March 2009 (UTC)

Why would this not be true? (Provided we accept some numerical functions for granted and do not consider hem as recursive, although at base level they are of course) Jos.koot (talk) 16:40, 1 April 2009 (UTC)

## Graphs

Who made the fancy graphs of shortest, longest non self-crossing and circulat hamilton paths that I introduced originally? They look great! Thanks. Jos.koot (talk) 16:36, 1 April 2009 (UTC)

## Solution description in layman's terms

In my opinion, this article has become way too technical at the expense of simplicity. One prime example is the Non-recursive solution section. It starts out with a mathematical analysis that is hardly suitable for the general audience. I looked at the article's history and found an explanation that appears much more suited to those without a mathematical background (see below).

I think this is much more reader friendly, so I propose restoring the older wording. The current working could be to a separate analysis section, if retained. -- Tcncv (talk) 01:21, 10 April 2009 (UTC)

Done. -- Tcncv (talk) 02:36, 12 April 2009 (UTC)

## Too many equivalent programming examples

Currently the Recursive solution section contains four programming examples. Except for syntax and whether the recursion stops at one disc or zero, they accomplish the same result using the same method. Even the "elegant" OCaml example is different only in syntax and the use of a match statement (aka case statement) in place of the if/else. Since this article is not a comparative study on programming languages, I do not see the need for any more than a single programming example in this section.

As for which one to keep, I think the answer lies with the target audience. I would expect that those with extensive programming experience would be able to understand any of the examples. However, for those with little of no programming background, I think the more-traditional and wordy Pascal syntax is most likely to be understood. In contrast, the meaning of "[(a,c)]", "|" and "_" in OCaml and the meaning of "(cond ...)" or "(- disc 1)" in Lisp are not likely to be readily apparent. The Python example is okay, but given the choice between Pascal and Python for the purpose of illustration, I'd choose Pascal. I am not a Pascal advocate by no means, in fact I'd prefer Python over Pascal for real work, but again the question is what is best for the audience.

As for the rest of the article, I'm less concerned about the programming examples, although there are sections that do seem to focus more on the programming than the topic and might benefit from a bit of trimming. -- Tcncv (talk) 02:00, 10 April 2009 (UTC)

Done. -- Tcncv (talk) 02:35, 12 April 2009 (UTC)

## "Most toy versions have 8 disks" - or is it 9?

An anonymous user changed it to 9. I believe this is false and most toy versions in fact have 8 disks. I personally have seen quite a number of toy versions with 8 disks, and don't recall ever seeing one with 9, but I understand that this is obviously a claim that is going to be hard to substantiate. However here's some circumstantial evidence for this: if I google "tower of hanoi 256" I get 19800 hits, whereas googling "tower of hanoi 512" gives 10600 hits. You get similar discrepancies if you google "tower of hanoi 8 disks" versus "tower of hanoi 9 disks" or other such variations. --Primalbeing (talk) 20:22, 3 June 2009 (UTC)

changed it from 9 back to 8 --Primalbeing (talk) 20:22, 3 June 2009 (UTC)

Agree. 8 appears correct. -- Tcncv (talk) 22:45, 3 June 2009 (UTC)

I've seen three different sets with 9 disks, but none with 8. Reverted -- Cjfjcjfjc (talk) 15:34, 5 June 2009

I think the obvious answer is that the number of rings varies from set to set. Primalbeing and I have (or have seen) sets with eight rings, Cjfjcjfjc has seen several with nine. A google search and in particular this site shows a variety of sets, most in the range of seven to nine disks. (Different search parameters may yield a different mix, but the point is there is no single correct number.) I propose we change the text to read "Most toy versions of the puzzle have between seven and nine disks, but the puzzle can be played with any number of disks." -- Tcncv (talk) 06:47, 5 June 2009 (UTC)
That sounds reasonable, so I made the change you suggested. --Primalbeing (talk) 09:37, 5 June 2009 (UTC)

## Two stacks and more stacks

Does the Two stacks and more stacks section belong in this article? Unlike the preceding sections that describe Reve's puzzle and the Frame-Stewart algorithm, I cannot find any references describing this variation that would demonstrate notability. I have found numerous articles covering many variations of the Tower of Hanoi puzzle, but not this particular variation. Looking at the edit history, this section appears to have been added and mostly maintained by a single editor, Victor7574. This editor is also likely the creator and patent holder of the described variation, and may also have an interest in its commercial development.

I propose removing the section as non-notable, original research, and a conflict of interest. In it's place, I would propose adding a section that lists and briefly describes (with proper references) several of the many of the Tower of Hanoi variations that can be found in a simple web search – preferably concentrating on those that have some academic coverage or some other notable attribute. -- Tcncv (talk) 02:48, 19 July 2009 (UTC)

## Simple solution isn't simple

It seems to me that the simple solution is not easy to understand.What's the 'left' side?What's the 'right' side?I think it is confusing. —Preceding unsigned comment added by Gxmcn (talkcontribs) 02:39, 18 August 2009 (UTC)

## Variant

I've seen a variant with one more additional rule, each disc cannot travel more than a peg at a time, ie, cannot travel from peg 1-3. 1-2, 2-3, 3-2 and 2-1 onely. It makes the number of moves go up much faster, roughly 7000 for optimal play with 8 rings. Benkenobi18 (talk) 09:56, 29 September 2009 (UTC)

## Proof of optimality?

I may be rusty on my mathematical analysis, but I don't undertand why the following excerpt from the article is true (last paragraph of [1]):

"By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal number of moves."

Mathematical induction is used to prove the solution takes 2^N-1 steps, but this is technically not a proof of optimality. The proposition one proves by induction is: "It takes 2^N-1 moves to solve the N-disk problem". A proof of optimality would need to prove the following proposition: "It takes at minimum 2^N-1 moves to solve the N-disk problem". This is trivially true for the base case of induction, but not so for the inductive step. If, by some mathematical or logical argument I'm missing, a proof by induction like this guarantees the optimality (and uniqueness too?) of the solution, then I think the article should mention it. It's not clear to me the way it is.

Meithan (talk) 17:19, 15 February 2010 (UTC)

## Cup puzzle

Per the edit summary by DavidWBrooks, the cup puzzle is really not needed in this article. Besides which, the edit which Anufriyev is repeatedly inserting is,

• Spammy, linking directly to a software download page and prablably failing WP:EL
• Full of asterisks, failing WP:MOS
• Attempting to change the spelling system, failing WP:ENGVAR
• Not provided with references, failing WP:V and WP:N

SpinningSpark 10:10, 7 June 2010 (UTC)

## Code samples

Please add the code samples back. Lot of other wikipedia aricles related to programming concepts have sample code in them. —Preceding unsigned comment added by 71.197.230.42 (talk) 15:18, 14 September 2010 (UTC)

Seconded. This is not about programming, nor is it a how-to, and code samples in any one language serve readers far less well than a clear description of the problem and solution that can be implemented in any language.--JohnBlackburnewordsdeeds 18:41, 16 September 2010 (UTC)

## Rationale for my External Link

I posted a link that I transparently identified as my own in the External Links section. The reason given for reverting my link was that it didn't contain variations that are notable outside of the site. Well, other than the Classic variation, this contains three variations mentioned in the Hanoi article: Reve's problem (Change "Towers per stack" to 4), more than 4 pegs problem (Change "Towers per stack" to > 4), and the Multistack Towers of Hanoi (Change Stacks to > 1). For all of these problems, not only can you play them, but the site can solve them, illustrating the Frame-Stewart algorithm as well as the method taken to solve Multistack which isn't documented in this article.

In addition to notable variations shown outside of this article, we have Cyclic (Article on this published here), Rainbow (Article on this published here by different person), Antwerp (here), Little Antwerp (here. Set Stacks to 2 to see the problem), and Super Hanoi (here. This is the equivalent of selecting the Random and Shuffle options).

So, this page graphically illustrates 3 puzzles that nothing else in the article does, as well as 5 other variations that have been written about and have been published in mathematic journals. Would that make this notable? If not, why? I often make contributions to Wikipedia that are disputed, but this is one case in which I think it's a valid contribution. Nevertheless, I'm up for discussion on it. BrandMan211 (talk) 17:50, 31 December 2010 (UTC)

You should not add links to your own site to Wikipedia. Wikipedia is not here to promote such sites, and even if you think such a site is a valuable addition you are probably the last person able to judge that. So you should leave it to others whether it is good to include. Se WP:ADV for the official policy. Looking at it I agree with the editor that removed it. It's a trivial and crude demonstration and a commercial rather than educational site. The animated GIF that is in the article is a far better demonstration of the puzzle. I'm not convinced the variations are that interesting or notable, and they are barely mentioned in the article which is mostly on the standard 3-peg approach.--JohnBlackburnewordsdeeds 18:12, 31 December 2010 (UTC)
Aside from that, though, he loved it. - DavidWBrooks (talk) 18:35, 31 December 2010 (UTC)
I was the editor who deleted the link. In light of the journal references provided by BrandMan211, I withdraw my objection on notability grounds. If another editor chooses to put the link back I will not challenge it again. However, I will not be restoring it myself. The Wikipedia policy on external links says that a link should not be included that does not provide a unique resource beyond what the article would contain if it became a featured article. I am always deeply suspicious of editors who want to link to their own site rather than add information to the Wikipedia article - which, after all, is the point of this project. When not done for blatant advertising reasons (probably not the case here) the motivation is usually to keep the information out of the control of Wikipedia editors. This leaves the graphic implementation of the puzzle as the unique resource of the site. I am not particularly fond of these either, all the simple puzzles tend to attract a growing number of sites offering puzzle solvers (just as all the simple physics laws attract "calculator" sites). If one is let in, the article is soon buried in them. SpinningSpark 19:34, 31 December 2010 (UTC)
My motivation for including the link instead of editing the article is that, quite frankly, I don't know enough about the solutions to properly document them. This page was primarily an attempt to implement a similar program on the web (With the original author's permission and guidance). If the community considers the variations illustrated here that are not already mentioned in the article to be notable, I'd hope that someone more math savvy could mention them, but I had very little to do with the solution algorithms and much more to do with the implementation of previously conceived algorithms, so all I can do is link to my implementation and the original documentation. BrandMan211 (talk) 20:04, 31 December 2010 (UTC)
Wikipedia has a high standard for including external links: not just any link should be included, and links can be excluded for a number of reasons, given here. Links to personal web sites in particular are usually excluded, especially commercial ones and a site with multiple paying adverts on a page is commercial. But my main objections are the quality: programming a Tower of Hanoi is a trivial programming exercise, even with animations (missing from this one). It's also very crude graphically. There's already a GIF that looks better. The generalisations are not the focus of the article, and the four pegs problem is a open problem so your claim that your site can "solve them" seems dubious. This is why such links are best restricted to recognised academic sources, where such claims tend to be justified by rigorous mathematics. Mathworld is one such source, the brainchild of Stephen Wolfram who also created Mathematica.--JohnBlackburnewordsdeeds 19:38, 31 December 2010 (UTC)
Again, although it might be your opinion that the graphic looks better, I'd like to understand why. Certainly you find this to be less crude or at least as crude as the animation on the Wolfram Alpha site. I'm not posing objections to the notability of the Mathworld link on the grounds of mathematical documentation, but that animation is simply as good if not worse than mine. In regards to my claims that it "solves" the 4 peg puzzle, well, it does. I never claimed optimality, but it implements the Frame-Stewart algorithm, which solves the problem without proof that it does it in the minimum amount of moves possible. BrandMan211 (talk) 20:04, 31 December 2010 (UTC)
I'm comparing it to the image already in the article which is animated and nicely rendered. I did not want to be too rude about it but as you've asked a second time yours looks like something a 12 year old drew. And 'the other site is as bad as mine' is hardly an argument for inclusion, especially when there are other reasons for including Mathworld than image quality.--JohnBlackburnewordsdeeds 20:27, 31 December 2010 (UTC)
You're welcome to that observation; yes, it's extremely simple, but it's a web application, not an image. If you have to make dynamic moving objects, you have to make it workable, and that gives you a lot more limits than a GIF has. Again, the goal here is not to visually dazzle; it's to show solutions / educate, just like Mathworld, and with the addition of the mathematical documentation I provided, I can easily say this page achieves that goal. If you are going so far as to say that the graphics are visually offensive, I strongly disagree. It is clear what disks are going where. Unless you disagree with that, the graphics aren't a reason to discount the page. BrandMan211 (talk) 22:58, 31 December 2010 (UTC)

I did not write offensive, just that the graphics are crude. A 5 second search turns any number of similar exercises, most better looking or better animated, using Flash, Java, Javascript and CSS. AS noted by User:Spinningspark if we include one we could end up including many more. Given that, and the clear rules on links to personal sites and conflict of interest, I don't think this should be included.--JohnBlackburnewordsdeeds 23:19, 31 December 2010 (UTC)

All I'm saying is if it's not graphically offensive, I don't think it's a reason not to include it. As far as the animation, what browser are you using? I've noticed as of late that Firefox has a bit of a lag in the solution (I use Chrome), so if that's you're main complaint, I definitely agree that I should do something about it. That said, the only remaining debate is whether it is a useful resource, whether or not it breaks the rules of Wikipedia, or whether it's not worth including because of the reason of slippery slope (Although that is a fallacy; you don't have to include other animations of lesser quality, especially if they bring nothing new to the table). What is the consensus on these points? As a irrelevant point, my site aside, are those variations notable? For instance, if I or one of the people who I know were willing to write an article on Cyclic, Rainbow, etc, would that be useful? Have a happy new year all, BrandMan211 (talk) 02:51, 1 January 2011 (UTC)
You have this the wrong way round, a strong reason to include is required for external links, not a strong reason to exclude. The default position is to exclude external links. To me, the issues are: material that could be included in the article fails WP:EL#EL1; links to personal sites fail WP:EL#EL11 unless written by a recognised authority (you are not a recognised authority on game theory are you?); the site contains ads, failing WP:EL#EL5; and you own the site, failing WP:ADV. I suggest that you read the guidelines before presenting any more arguments for inserting this link.
New articles are always welcome. The test of whether or not a subject is suitable for wikipedia is notability. The essential requirement is that the subject should have non-trivial coverage (more than merely mentioned) in multiple reliable sources. If suitable references are provided to establish notability in a new article there is usually no difficulty with keeping it. SpinningSpark 11:01, 1 January 2011 (UTC)
I probably worded my response badly. What I'm getting at is I believe that the introduction of these variations, many of which notable, and their solutions are a strong reason to include. To negate this, strong reasons to exclude need to be provided. I don't think the graphics issue is a strong issue to exclude. Now, let's discuss the points you brought up. For the first one, is the point that if the Wikipedia article was better written, it would contain all of the data on the page? This might be possible, but it's obvious that the solver is something that can't be included in a Wikipedia article, and I figure that one, good, comprehensive solver is worth including, although you could debate whether this page fulfills that requirement. To the second argument, no, I'm not a recognized authority, but does it change anything at all if this was a collaboration between me and several published authors on the subject, including the author of 4 of the 5 articles I cited, Steven Minsker? More importantly, can this really be considered a personal site just because it is hosted under a domain with my name on it? I don't mention myself anywhere but in the footer. To the third, I'm still not sure what makes my advertisments worse than Mathworld's. They take up a very small percentage of the page. Is the concern that there are two instead of one? You'll probably never see them both at the same time considering the massive block of graphics and text in between them. In regards to the last item, that's why I'm here asking the editors to decide, although I hope that the decision is primarily based on its usefulness and whether it abides by the rules or not instead of making the deciding factor that of conflict of interest. Again, I'm sorry for not having first prompted a discussion.
In regards to the addition of content on some of these variations, I was suggesting an additional section instead of an article. I think it's clear that Cyclic is a common variation that has been written about by several people, and if the consensus believes it is useful enough, I can probably through together a section describing the rules and an algorithm on how to solve it (Though the only free source I have regarding it is the documentation to the original program I based my page on, written by Fred Lunnon, and hosted on the same domain as this page. I'm not sure if such a citation would cause a similar controversy, though I'll assume that the links used for citations have different guidelines than external links). To avoid further reversion, I request some feedback on this before I proceed. I also wonder which of the other variations on the page would be considered notable enough for a section. I think Rainbow's been a pretty common variation, though I don't grasp the solution nearly enough to write a suitable article for it. I by no means am suggesting that all of the variations we've implemented are notable (Especially considering Lunnon created "Lundon" as a challenge for me, and I responded with "Brandonburg"), but I certainly would be interested to know which of the 5 puzzles cited would be considered a useful contribution to the article. BrandMan211 (talk) 19:31, 1 January 2011 (UTC)
Interesting; I wouldn't think that an article featured in a non-free journal would be considered a good reference, considering there's no easy way of verifying if the source really says what is claimed. More importantly, I don't have a copy of said journal, yet it's obvious that the provided solution works consistently, and I'm not sure what a journal article does to change that. So, although I could easily write a section on the variation from personal knowledge, without a copy of a "reliable source" that says the same thing that I know to be true, I'm not sure how I'd be able to write one that fits the rules and standards of Wikipedia. BrandMan211 (talk) 04:23, 2 January 2011 (UTC)
Yes, you now understand Wikipedia's policies on notability and verifiability. Without the requirement for reliable sources, Wikipedia would become an indiscriminate collection of articles on trivia such as "the third stone from the left on the top of my garden wall". Gandalf61 (talk) 08:22, 2 January 2011 (UTC)
thing that I know to be true...You might know it, and I might believe you, but Wikipedia has no way of judging your competence; that is why sources known to reliably verify their material are required. Many Wikipedia editors have free access to journals through their library, educational institution or company. Finding someone able to check a source is rarely a problem here given the number of people involved in the project. Try asking at WP:REX, someone there is usually willing to provide a copy, although it sometimes takes a while - you will get a faster response if you give them the exact citation (author, title, journal, issue, volume, page numbers). It is always good to check the sources before writing even if you think you know all the answers. There have been many occasions when researching an article I have discovered that things I thought to be true were not so, or were not exactly so - even on subjects in which I am professionally competent. SpinningSpark 10:36, 2 January 2011 (UTC)
Strangely enough, I found the recursive solution to Cyclic in an article on the iterative solution. Would this be acceptable? BrandMan211 (talk) 18:32, 2 January 2011 (UTC)
It would satisfy me. SpinningSpark 20:27, 2 January 2011 (UTC)
Added. I would write about the given iterative solution, but I don't quite understand it yet. If someone wants to give it a try, be my guest. But, is what I have right now acceptable? BrandMan211 (talk) 21:04, 2 January 2011 (UTC)

## Mnimal number of moves for any number of pegs and discs

For p as the number of pegs, d as the number of discs and n defined by: ${\displaystyle n\geq 0}$ and ${\displaystyle {\tbinom {n+p-3}{p-2}}

The minimal number of moves for any number of pegs and discs is:

${\displaystyle d\times 2^{n}-\sum _{k=0}^{n-1}{\tbinom {k+p-3}{p-3}}(2^{n}-2^{k})}$

For 10 pegs and 1000 discs, n is 5 and the minimal number of moves are 22561

Sublinhado (talk) 02:50, 25 June 2011 (UTC)

## Iterative Towers of Hanoi Edit

There is an interesting way to think about the iterative version of Towers of Hanoi. It is described below. I attempted to edit the page in order to add this information which is well known among computer scientists but not very well known in general. The edit was reverted three times. Please read the edit and support this change if you believe the information is interesting and worthwhile.

### Equivalent iterative solution

Another, perhaps simpler, way to think of the iterative solution is to color the base of the Start peg white, and alternately color the disks on this peg from largest to smallest: black, white, black, etc. Note that no black touches black and no white touches white. Also, color the Finish peg white and the Using peg black. Now, add the constraint that a black disk can only sit on a white disk (or peg) and a black disk can only sit on a black disk (or peg).
With this extra constraint, and the obvious rule of never undoing your last move, there is only one unique move at every turn. The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.
Lippert, Eric "How Not to teach Recursion". Microsoft MSDN. 2004-05-19.

— Preceding unsigned comment added by 71.233.104.55 (talkcontribs)

I believe the main reason your edit has been reverted is that you did not provide a reliable source. The citation you provided points to a blog, which is not a reliable source for Wikipedia articles - and the blog entry cited doesn't even seem to mention this black-and-white alogorithm (unless it is perhaps buried somewhere in the comments, which I didn't read). A secondary problem is that your explanation is not very clearly written - there is an obvious error in the version above, for example. Gandalf61 (talk) 10:29, 3 November 2011 (UTC)

The reference I gave is a nice piece about recursion and includes the algorithm I described. The relevant section is pasted below: The text is not buried in the comments. Moreover, I checked my description above again and found no errors. Further, the version I gave above seems clear enough. The reference excerpt from Lippert is reproduced here:

In case you're curious, the iterative solution can be produced by writing a program that implements these rules in a loop:

   Number the disks 1 to n starting from the top.
Never move an odd disk onto an odd disk.
Never move an even disk onto an even disk.
Never move a larger disk onto a smaller disk.
Never move the same disk twice in a row.
Never move a disk onto an empty spike unless you have to.
Move disks until there are no legal moves.  — Preceding unsigned comment added by 71.233.104.55 (talk) 12:41, 9 November 2011 (UTC)


I found a printed reference and rewrote the description -- I hope the new entry is acceptable... Thanks all... 204.144.15.10 (talk) 14:21, 9 November 2011 (UTC)

## Popular Culture

The game "Escape From Paradise" has a mini-game called "The Towers of Hanoi" based on this. — Preceding unsigned comment added by 69.114.132.26 (talk) 03:00, 12 December 2011 (UTC)

Thanks but that really is trivia: it's appeared and re-appeared in computer games where a puzzle is called for. It's trivial to implement but can be a break for the normal puzzles of adventure and other computer games.--JohnBlackburnewordsdeeds 03:56, 12 December 2011 (UTC)

## Links to play the game

I can see people have tried to add links to show people what the game is all about and allows them to try it for themselves. Surely this would be a way of supporting the whole article and backing it up? As long as there is a strict number of links, say two or at the VERY most three, what is the problem? Cexycy (talk) 23:34, 19 December 2011 (UTC)

See again the external link guidance, and the previous discussion which again emphasised WP:ELNO #1 after another editor tried to add their preferred link. Reading the guidance page again I noticed WP:ELMAYBE #3, recommending "a well-chosen link to a directory", which is a good alternative to the inevitable long list if each editor adds their favourite(s), so I've added a {{dmoz}} template.--JohnBlackburnewordsdeeds 05:53, 27 December 2011 (UTC)

## Actual tower in Hanoi?

I was curious is there was any connection to the actual city. A check of the Hanoi page found the image on the right. Could this be THE Tower of Hanoi? Are there other towers in Hanoi like this? (I've always heard the puzzle called "Towers of Hanoi", since there's three "towers".) Even if the puzzle wasn't designed in Hanoi, it may have been inspired by it, hence the name. Just wondering if it might be worth putting this image on the page as a historical curiosity. Lurlock (talk) 14:50, 11 July 2013 (UTC)

Here is the illustration from the box in which the original 1883 puzzle was sold. The instructions refer to the "Sacred Tower of Brahma" in "the Temple of Bernares". I very much doubt whether the puzzle was inspired by any actual building - Hanoi and Benares were probably chosen simply because they sounded mysterious and oriental. Gandalf61 (talk) 15:35, 11 July 2013 (UTC)
The building in the illustration does have a sort of generic pagoda-like look to it. I suppose there are any number of buildings in that style throughout the far east. The question would of course be how many of these buildings existed in 1883 that an average Frenchman might have been aware of? The current history section even gives a possible origin of India, which as far as I know did not use that building style (though I could be wrong on that one). It also says "publicized in the West" - is this meant to imply that the puzzle already existed before that elsewhere? Did Édouard Lucas actually invent it and just give it random oriental names just for marketing? Or did he merely discover it from some other (presumably eastern) source and publicize it? Lurlock (talk) 16:02, 11 July 2013 (UTC)

## Invention

As I know, most modern source attributes the invention of the toy to Lucas alone (eg. Britannica and Mathworld. That said, I see no reason to say "fist publicized" instead of "invented". Lechatjaune (talk) 10:48, 30 September 2014 (UTC)

## Misuse of Mass Effect Reference?

It's kind of weird Mass Effect is listed as a game that has this puzzle, as it does not actually have a Tower of Hanoi puzzle, instead Shepard's rather strong "No Thank You" to the suggestion of playing it is a reference to both how common this puzzle appears in video games (especially Puzzle and Adventure games) and gamer's general dislike for Tower of Hanoi for both being tediously long to solve and having little to no variation. In fact, it might be something to note if anyone can find research about the dislike for this puzzle in game format. — Preceding unsigned comment added by 184.97.110.24 (talk) 09:33, 11 March 2015 (UTC)

## Possible error in Recursive solution section

To move n discs from peg A to peg C:

move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc n

...

The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1.
This step, moving a single disc from peg A to peg B, is trivial.

Shouldn't the last sentence in say "from peg A to peg C"? Raneksi (talk) 11:30, 3 April 2015 (UTC)

You are correct. Fixed. Bill Cherowitzo (talk) 15:33, 3 April 2015 (UTC)

## Frame-Stewart for four pegs

I discovered that the Frame-Stewart conjecture has been proven for four pegs, and I updated the article accordingly. I still think that section could do with a rewrite for clarity but I do not have the ambition to do it. MathHisSci (talk) 14:55, 28 February 2016 (UTC)

## Base 3 Gray code for the longest non self-crossing path

For every number of disks h there is a base 3 Gray code with h digits that shows the distribution of the disks among the pegs 0, 1 and 2 in the right order for the longest non self-crossing path moving a tower from peg 0 to peg 2. I think this can be included in the article. The following Racket program is an illustration. (number->list (Gray-code m 3 h)) gives the distribution of disks after m moves. Notice that procedure Gray-code returns a number, not a list of digits. I can simplify the program to an acceptable number of lines, say less than 15.

1. lang racket
If b is even, Gray-code is circular.
If b is odd, Gray-code is not circular.
Every more significant digit changes more frequently than less significant digits.
If b=3, the Gray-code can be used for the longest non self-crossing path from peg 0 to peg 2.

(define (Gray-code m b h) ; m b h -> m-th element of (b,h) gray code

(list->number
(reverse
(let ((2b (* 2 b)))
(let loop ((m m) (h h) (gc '()))
(if (zero? h) gc
(let ((q (quotient m b)) (d (modulo m 2b)))
(loop q (sub1 h) (cons (if (>= d b) (- 2b d 1) d) gc)))))))
b))


(define (Gray-code-inverse gc b h) ; n-th (b,h) gray-code -> n

(let ((gc (number->list gc b h)))
(let loop ((gc (reverse gc)) (b^h (expt b (sub1 (length gc)))))
(if (null? gc) 0
(let ((p (car gc)) (gc (cdr gc)))
(let ((m (loop gc (quotient b^h b))))
(+ (* p b^h) (if (odd? p) (- b^h m 1) m))))))))

number->list produces a list of h digits in base b for number m.
list->number is its inverse.

(define (number->list m b h)

(define (number->list m h)
(if (zero? m) (make-list h 0)
(let-values (((q r) (quotient/remainder m b)))
(cons r (number->list q (sub1 h))))))
(reverse (number->list m h)))


(define (list->number gc b)

(define (list->number gc)
(if (null? gc) 0
(let ((d (car gc)) (gc (cdr gc)))
(+ d (* b (list->number gc))))))
(list->number (reverse gc)))

Procedure move-tower is used to check the results of the gray code solution.

(define (move-tower h)

(define distr (make-vector h 0))
(define move-list (list (vector-copy distr)))
(define (move-disk d f t)
(vector-set! distr d t)
(set! move-list (cons (vector-copy distr) move-list)))
(define (move-tower h f t)
(unless (zero? h)
(define h-1 (sub1 h))
(define r (- 3 f t))
(move-tower h-1 f t)
(move-disk  h-1 f r)
(move-tower h-1 t f)
(move-disk  h-1 r t)
(move-tower h-1 f t)))
(move-tower h 0 2)
(reverse (map vector->list move-list)))

Do the test now
Erase #; if you want to print the lists of moves.

(for ((h (in-range 1 13)))

#;(printf "b=~s, h=~a~n" 3 h)
(for ((m (in-range 0 (expt 3 h))) (distr (in-list (move-tower h))))
(define gc (Gray-code m 3 h))
(define ngc (number->list gc 3 h))
#;(printf "~a ~a ~a ~a ~a~n"
(number->list m 3 h)
ngc
distr)
(unless (and (= (Gray-code-inverse gc 3 h) m) (equal? distr ngc))
(error 'test "b=3, h=~a, gc=~a, ngc=~a, m=~a" h gc ngc m)))
#;(printf "end of list~n~n"))


Jacob.Koot (talk) 17:18, 5 April 2016 (UTC)

## OEIS A001511 -- The Simplified Ruler Function

One of the first solutions (1872) is the most elegant, the so-called Ruler function (sequence A001511 in the OEIS) -- 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 -- number of disk to be moved at n-th step of optimal solution to Towers of Hanoi problem. The sequence is basically one more than the power of 2 used in move ${\displaystyle n}$. This is also the bit that changes in step ${\displaystyle n}$ of the Gray code. I've modified Thomae's function to include the sub-sequence known as the Ruler function, hopefully that will stick. Users User:Jasper_Deng and User:DavidWBrooks are rejecting core sequences in OEIS as a valid source, are saying this ancient sequence is original research, and that the sequence needs to be proven afresh. EdPeggJr (talk) 21:48, 25 July 2016 (UTC)

No, we were saying that it was unclear where this code came from, that it appeared to be something you, the editor, had dreamed up; in which case it might be wonderful but it doesn't belong in wikipedia - and the fact that you just said you have modified the code sure sounds like original research. Verifiability rather than truth is a cornerstone of wikipeda - and yes, that's often annoying and sometime gets in the way of valid information, but such is life. Even if you really are Ed Pegg Jr., the articles here shouldn't feature work you create just for this article. - DavidWBrooks (talk) 15:14, 26 July 2016 (UTC)
Have you looked at sequence (sequence A001511 in the OEIS) yet? This is a heavily verified core OEIS sequence. Any person with the slightest skill in mathematics can verify the sequence is correct within seconds. The connection of this sequence and the Towers of Hanoi dates back to 1872. I modified Thomae's function to include the ruler function. Absolutely nothing about this is original research, and all of it is easily checkable by going to (sequence A001511 in the OEIS).
I'm afraid you're not quite understanding how wikipedia works - saying that something is "easily checkable" by people with certain skills by going to so-and-so source and doing such-and-thus task is not considered a reference in wikipedia, although it's certainly valid in other places. Can you point us to a published source which talks about the connection between the sequence and the tower of Hanoi - that's the sort of thing that wikipedia considers a reference/source. - DavidWBrooks (talk) 22:22, 27 July 2016 (UTC)

## Graphical representation 2.0

Can the "b" and "c" on the one-disc triangle be switched so the two-disc graph follows logically? D k mackenzie (talk) 03:48, 2 January 2017 (UTC)

## Help please Mersenne question

The edit in question is [here]. The section and statement is "The puzzle can be played with any number of disks, although many toy versions have around seven to nine of them. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n – 1, where n is the number of disks.[4] This is precisely the nth Mersenne number. " (my bold) I think this added statement needs a source and/or better explanation. I will appreciate any help here either way- And I know this is probably a really stupid ? but if left "as-is" would that be a prime or not or would not make a difference in the statement? thanksTeeVeeed (talk) 16:32, 20 March 2017 (UTC)spellTeeVeeed (talk) 16:33, 20 March 2017 (UTC)

@TeeVeeed: To be perfectly honest, if you don't understand that, then I think you need to read up on exponentiation. What about "this is ${\displaystyle M_{n}=2^{n}-1}$" is not clear to you? And note that here, ${\displaystyle M_{n}}$ most definitely need not be prime (consider n = 4).--Jasper Deng (talk) 16:36, 20 March 2017 (UTC)
Well I ask because you have it int lnk to Mersenne prime. (It is a redir but still room for confusion there). The duplicate equation is fine exponentially. (as far as I know), but then going into nth M number, without any source except the redir to Mersenne prime, which is lengthy, may not be the best way to present that for readers. That's why I'm asking here. Is there any simpler way to say it (about the "nth") in the article or better yet source it imo. TeeVeeed (talk) 17:27, 20 March 2017 (UTC)
(edit conflict) What I gather from the linked article is that while there is agreement on what Mersenne prime means, there are at least a couple of different usages of Mersenne number, so I agree that “precisely“ may not be the best qualifier without more explanation (although I think the lead of Mersenne prime does make it reasonably clear), and it would be nice to have a reference that mentions them in the context of this puzzle. The sense intended here is evidently the broader one, but the bare mention is almost tautological. Does the Tower of Hanoi exhibit any particular properties of Mersenne numbers? Remember that many readers of this article may not have much mathematical background. @TeeVeeed: to expand a bit on the above, where the exponent n is composite, so is the corresponding Mersenne number Mn, but not all prime exponents produce Mersenne primes: for example M11 = 2047 = 23 × 89. See the article for details, including some relevant proofs.—Odysseus1479 17:53, 20 March 2017 (UTC)
So to keep the "M" statement if no source can be found, I don't object to that completely (but would appreciate it), but would it be correct to say it a different way like, "The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n – 1, where n is the number of disks.[4] Which is the same formula used for a Mersenne number." (?) TeeVeeed (talk) 18:01, 20 March 2017 (UTC)
ALso. Using this version with minimum number of moves needed pre-calculated, the formula/solution does not work.https://www.mathsisfun.com/games/towerofhanoi.html Is the "solution" correct?TeeVeeed (talk) 18:34, 20 March 2017 (UTC)
Yes, it is meant in the broad sense, but that broad sense is the one most used in the article. I don't see the difference between "matches the formula for" and "is precisely".
And yes you can solve the 3-disk instance in 7 moves. I even once wrote a computer program to graphically illustrate the solution.--Jasper Deng (talk) 18:56, 20 March 2017 (UTC)
I do not understand what you mean when you say the formula/solution does not work. The mathisfun website gives the correct number which is 2n -1. That is, for 3 rings you get 23 - 1 = 8 - 1 = 7 for the minimum number of moves and for 4 rings it is 24 - 1 = 16 - 1 = 15 moves, etc. The Mn notation for Mersenne numbers was introduced in 1911. Although some authors may use a variation of the terminology, the common name, and therefore the one used on Wikipedia, for the numbers 2n - 1 = Mn is Mersenne number. The usage section in Mersenne prime has a citation which may link the Tower of Hanoi puzzle to a Mersenne number, but I don't have access to the citation to verify this. I also don't see what all the fuss is about, this is just the name of a type of number. If I were to make the statement that the minimum number of moves was always an odd number, would there be any objection? Is there something about the puzzle which reflects the oddness of the minimum number of moves? However, in the spirit of compromise, let me suggest replacing "... is precisely a Mersenne number." with "...is also known as a Mersenne number." --Bill Cherowitzo (talk) 19:04, 20 March 2017 (UTC)
The preferred alternative for me would be "happens to be the nth Mersenne number". Mathematical coincidences are common, this is no exception.--Jasper Deng (talk) 19:07, 20 March 2017 (UTC)
FWIW I would prefer either that or Bill’s wording above to the present version.—Odysseus1479 20:00, 20 March 2017 (UTC)
nevermind about solution my bad.TeeVeeed (talk) 19:17, 20 March 2017 (UTC)
@TeeVeeed: Do you still have concerns about the statement in question here?--Jasper Deng (talk) 19:57, 20 March 2017 (UTC)
Yes I think I still do have a little trouble with the way it is worded and refrenced but I honestly can't even look at it anymore. But take my word for it, on first reading and even second it is clunky and dirversionary in my opinion, when it could be simplified. But I do think it is a good addition to the topic.TeeVeeed (talk) 20:35, 20 March 2017 (UTC)
I don't think it's diversionary. Remarking about coincidences is very commonplace in mathematics articles. Does my suggested wording sound good?--Jasper Deng (talk) 23:57, 2 April 2017 (UTC)