Talk:Tower of Hanoi/Archive 2

Archive 1

Archive 2

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"
  (pad m 4)
  (pad gc 4)
  (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 $n$. This is also the bit that changes in step $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 $M_{n}=2^{n}-1$" is not clear to you? And note that here, $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 M_n, but not all prime exponents produce Mersenne primes: for example M₁₁ = 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 2ⁿ -1. That is, for 3 rings you get 2³ - 1 = 8 - 1 = 7 for the minimum number of moves and for 4 rings it is 2⁴ - 1 = 16 - 1 = 15 moves, etc. The M_n 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 2ⁿ - 1 = M_n 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)

computing m-th move and resulting distribution without making preceding moves

The m-th move and the resulting distribution of disks of the shortest path with 3 pegs can be computed directly without computing any other move. The pegs are assumed to be located at the vertices of an equilateral triangle with a 3-fold axis of rotation (symmetries C3v) IIRC I posted these formulas earlier, but they have disappeared.

Legend

m move number, starting from 1.
h height of the tower, id est the number of disks.
f starting peg, 0, 1 or 2.
t destination peg, 0, 1 or 2, but t and f distinct.
d disk, 0≤d<h, in order of size, 0 being the smallest disk.

pari(n)         = ((n+1) mod 2)+1  = parity (1 or 2)
rotd(h,d,f,t)   = ((t–f)pari(h–d)) mod 3  = sense of rotation of disk d
rotr(h,f,t)     = rotd(h,0,t,f) = sense of rotation of unused peg
disk(m)         = number of times m is divisible by 2 = disk being moved during move m
mcnt(m,d)       = (m+2d)/2d+1 = nr of moves of disk d after a total of m moves
thrd(m,h,f,t)   = (f+mrotr(h,f,t)) mod 3 = unused peg during move m
onto(m,h,f,t)   = (thrd(m,h,f,t)–rotd(h,disk(m),f,t)) mod 3 = peg disk is moved to during move m
from(m,h,f,t)   = (thrd(m,h,f,t)+rotd(h,disk(m),f,t)) mod 3 = peg disk is taken from during move m
posi(m,h,d,f,t) = (f+mcnt(m,d)rotd(h,d,f,t)) mod 3 = position of disk d after a total of m moves

These formulas allow computing move N-Avagadro for 80 disks and the resulting distribution of disks in a millisecond.
Similar formulas exist for the circular and non-circular Hamilton path.
I think these formulas should be included in the article (in a better layout of course)

Jacob.Koot (talk) 17:33, 29 September 2017 (UTC)

This is unsupported with references and so, at least in my mind, pretty clearly WP:OR. As such, it can not be used in the article, and so, it has no place on this talk page which is devoted to improving the article. I suspect that your earlier posting was removed for this reason. --Bill Cherowitzo (talk) 17:13, 30 September 2017 (UTC)

Ok, Jacob.Koot (talk) 10:55, 1 October 2017 (UTC)

The idea of using sierpinsky graphs originates from me too. Someone transformed the graphs to a much nicer form I had introduced them originally. These graphs are WP:OR too. It would be a pity to remove them, though.Jacob.Koot (talk) 18:30, 24 October 2017 (UTC)

Solution on a spreadsheet

Let the three pegs in the toy be replaced by three columns on a spreadsheet, and let the discs in the toy be replaced by consecutive integers, with 1 representing the smallest disc, 2 the second smallest disc, etc. An empty column is understood to have the number "zero" at the bottom. The objective of the puzzle is to move the numbers from one column to another column in duplication. There are only two rules: (a) The numbers are moved one number at a time. (b) The overlying number must be smaller than the number underlying it. Surprisingly, one strategy will be sufficient to solve the puzzle, which is: "Always place the number 1 atop the exposed largest even number." The strategy works for a tower of any tiers. And there is no limit to the number of tiers. This idealization by numbers allows us to take advantage of even numbers and odd numbers. 70.54.64.194 (talk) 00:32, 4 March 2018 (UTC)

The number of bits present in Gray code is important, and leading zeros are not optional, unlike in positional systems.

The number of bits present in Gray code is important, and leading zeros are not optional, unlike in positional systems. As far as I know, Gray code does not have this requirement. It is required for a circular Gray code, used in circular encoders, but otherwise you can count to infinity, and assume zeros in unfilled positions. In the case of the game, there is normally a given number of disks. You could change the game to: Move N disks, create a new (N+1)th disk and place it appropriately, move N disks onto it, repeat, forever. Gah4 (talk) 00:07, 13 June 2018 (UTC)

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.

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) "Theory and practice of building of the Hanoi towers". Sergey Zhigalik, eBook The book contains the description of the solution path of generalized variant of the problem, which is known as The Tower of Hanoi puzzle. The general formula for problems of a certain type is derived on the base of such concepts as the optimal process and the “complete decomposition tree”. The book offers the types of problems for which the solutions and the optimality of these solutions are “obvious”. The formulas for defining the number of steps to solve these problems are given. The conclusions, based on the considered problems of simple types, are defined the solution path to generalized problem with any number of discs and pegs.It is given a method of all optimal decompositions obtaining, any of which can be used for the best solution of the particular problem. That makes it possible to get different solutions of the problem and the ability to determine all possible optimal solutions.It is considered the Formula of Frame-Stewart. It is shown, why it is possible to find the optimal solution using this formula. Here is given a method how to find all possible coefficients to solve the particular problem using the given formula.It is described a universal algorithm for the solution of the generalized the “Tower of Hanoi” problem. 176.59.22.176 (talk) 11:14, 11 April 2019 (UTC)

Editing "Towers of Hanoi" Wikipedia page

Information to be added:

After: "The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.[7]"

Please add the following sentence:

The iterative solutions can be found in a mechanical way starting from the recursive ones as indicated in [1] by using the tupling strategy. That strategy, which works also in the case of the cyclic and generalized versions of the problem (see below), is based on syntactic matchings of expressions. Thus, no proof of correctness of the derived programs is necessary. The tupling strategy has been applied in the seminal paper on program transformation by R. M. Burstall and J. Darlington [2].

Explanation of issue: I think that it was important to indicate that once you have the recursive solution, you may have the iterative solution "for free". No intricate proofs of the iterative versions are necessary.

References supporting change: here you have also the doi of my paper:

@ARTICLE(Pet85a, AUTHOR = " A. Pettorossi", TITLE = "Towers of Hanoi Problems: Deriving Iterative Solutions by Program Transformation ", JOURNAL = "BIT ", YEAR = 1985, volume = 25, pages = " 327--334", note = "doi.org/10.1007/BF01934378" ).

My homepage: http://www.iasi.cnr.it/~adp/

I wrote to prof. Gedeon who did also some work in 1996 the derivation of iterative solutions (see reference 11). But no answer from him as yet.

[1] Pettorossi A., "Towers of Hanoi Problems: Deriving Iterative Solutions By Program Trasformations". BIT 25, 327-334, 1985

[2] Burstall R.M. and Darlington J., "A Transformation System for Developing Recursive Programs", JACM, 24(1), 44-67, 1977 Alberto Pettorossi (talk) 16:26, 18 June 2020 (UTC)Alberto Pettorossi (talk) 10:55, 18 June 2020 (UTC) Alberto Pettorossi

I added a {{edit COI}}  Darth Flappy ^«Talk» 13:48, 19 June 2020 (UTC)

I'm not really sure why we need two iterative solutions for this article, let alone a new third one. - MrOllie (talk) 14:37, 19 June 2020 (UTC)

Marked as declined. Please feel free to reopen this edit request if discussion resumes. Altamel (talk) 21:16, 18 July 2020 (UTC)