Editing Tower of Hanoi (section)

== Solution ==
The puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. The minimal number of moves required to solve a Tower of Hanoi puzzle with ''n'' disks is {{nowrap|2<sup>''n''</sup> − 1}}.<ref>{{cite book |last=Petković |first=Miodrag |title=Famous Puzzles of Great Mathematicians |year=2009 |publisher=AMS Bookstore |isbn=978-0-8218-4814-2 |page=197}}</ref>

=== Iterative solution ===
[[File:Iterative algorithm solving a 6 disks Tower of Hanoi.gif|thumb|Animation of an iterative algorithm-solving 6-disk problem]]
A simple solution for the toy puzzle is to alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest moves.<ref>{{cite journal |last=Troshkin |first=M. |title=Doomsday Comes: A Nonrecursive Analysis of the Recursive Towers-of-Hanoi Problem |journal=Focus |volume=95 |issue=2 |pages=10–14 |language=ru }}</ref>

==== Simpler statement of iterative solution ====
{{More citations needed section|date=January 2024}}
The iterative solution is equivalent to repeated execution of the following sequence of steps until the goal has been achieved:
* Move one disk from peg A to peg B or vice versa, whichever move is legal.
* Move one disk from peg A to peg C or vice versa, whichever move is legal.
* Move one disk from peg B to peg C or vice versa, whichever move is legal.
Following this approach, the stack will end up on peg B if the number of disks is odd and peg C if it is even.

=== Recursive solution ===
{{More citations needed section|date=January 2024}}
[[File:Tower of Hanoi recursion SMIL.svg|thumb|link={{filepath:Tower_of_Hanoi_recursion_SMIL.svg}}|Illustration of a recursive solution for the Towers of Hanoi puzzle with 4 disks. In [{{filepath:Tower_of_Hanoi_recursion_SMIL.svg}} the SVG file,] click a grey button to expand or collapse it]]
The key to solving a problem [[recursive]]ly is to recognize that it can be broken down into a collection of smaller sub-problems, to each of which ''that same general solving procedure that we are seeking'' applies{{Citation needed|date=January 2024}}, and the total solution is then found in some ''simple'' way from those sub-problems' solutions. Each of these created sub-problems being "smaller" guarantees that the base case(s) will eventually be reached. For the Towers of Hanoi:
* label the pegs A, B, C,
* let ''n'' be the total number of disks, and
* number the disks from 1 (smallest, topmost) to ''n'' (largest, bottom-most).

Assuming all ''n'' disks are distributed in valid arrangements among the pegs; assuming there are ''m'' top disks on a ''source'' peg, and all the rest of the disks are larger than ''m'', so they can be safely ignored; to move ''m'' disks from a source peg to a ''target'' peg using a ''spare'' peg, without violating the rules:
# Move ''m'' − 1 disks from the '''source''' to the '''spare''' peg, by ''the same general solving procedure''. Rules are not violated, by assumption. This leaves the disk ''m'' as a top disk on the source peg.
# Move the disk ''m'' from the '''source''' to the '''target''' peg, which is guaranteed to be a valid move, by the assumptions — ''a simple step''.
# Move the ''m'' − 1 disks that we have just placed on the spare, from the '''spare''' to the '''target''' peg by ''the same general solving procedure'', so they are placed on top of the disk ''m'' without violating the rules.
# The base case is to move ''0'' disks (in steps 1 and 3), that is, do nothing—which does not violate the rules.

The full Tower of Hanoi solution then moves ''n'' disks from the source peg A to the target peg C, using B as the spare peg.

This approach can be given a rigorous mathematical proof with [[mathematical induction]] and is often used as an example of recursion when teaching programming.

==== Logical analysis of the recursive solution ====
{{More citations needed section|date=January 2024}}
<!-- TODO:  This section needs copy-editing for tone, professionalism and clarity: edited/bolded .-->
As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of ''h'' (height) disks from a starting peg ''f'' = '''A''' (from) onto a destination peg ''t'' = '''C''' (to), '''B''' being the remaining third peg and assuming ''t'' ≠ ''f''. First, observe that the problem is symmetric for permutations of the names of the pegs ([[Symmetric group|symmetric group ''S''<sub>3</sub>]]). If a solution is known moving from peg '''A''' to peg '''C''', then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If ''h'' = 1, then move the disk from peg '''A''' to peg '''C'''. If ''h'' > 1, then somewhere along the sequence of moves, the largest disk must be moved from peg '''A''' to another peg, preferably to peg '''C'''. The only situation that allows this move is when all smaller ''h'' − 1 disks are on peg '''B'''. Hence, first all ''h'' − 1 smaller disks must go from '''A''' to '''B'''. Then move the largest disk and finally move the ''h'' − 1 smaller disks from peg '''B''' to peg '''C'''. The presence of the largest disk does not impede any move of the ''h'' − 1 smaller disks and can be temporarily ignored. Now the problem is reduced to moving ''h'' − 1 disks from one peg to another one, first from '''A''' to '''B''' and subsequently from '''B''' to '''C''', but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the ''h'' − 1 problem to ''h'' − 2, ''h'' − 3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows.

Identify the disks in order of increasing size by the natural numbers from 0 up to but not including ''h''. Hence disk 0 is the smallest one, and disk ''h'' − 1 the largest one.

The following is a procedure for moving a tower of ''h'' disks from a peg '''A''' onto a peg '''C''', with '''B''' being the remaining third peg:
# If ''h'' > 1, then first use this procedure to move the ''h'' − 1 smaller disks from peg '''A''' to peg '''B'''.
# Now the largest disk, i.e. disk ''h'' can be moved from peg '''A''' to peg '''C'''.
# If ''h'' > 1, then again use this procedure to move the ''h'' − 1 smaller disks from peg '''B''' to peg '''C'''.

By [[mathematical induction]], it is easily proven that the above procedure requires the minimum number of moves possible and that the produced solution is the only one with this minimal number of moves. Using [[recurrence relation]]s, the exact number of moves that this solution requires can be calculated by: <math>2^h - 1</math>. This result is obtained by noting that steps 1 and 3 take <math>T_{h-1}</math> moves, and step 2 takes one move, giving <math>T_h = 2T_{h-1} + 1</math>.

==== Non-recursive solution ====
{{More citations needed section|date=January 2024}}
The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm, has many regularities. When counting the moves starting from 1, the ordinal of the disk to be moved during move ''m'' is the number of times ''m'' can be divided by 2. Hence every odd move involves the smallest disk. It can also be observed that the smallest disk traverses the pegs ''f'', ''t'', ''r'', ''f'', ''t'', ''r'', etc. for odd height of the tower and traverses the pegs ''f'', ''r'', ''t'', ''f'', ''r'', ''t'', etc. for even height of the tower. This provides the following algorithm, which is easier, carried out by hand, than the recursive algorithm.

In alternate moves:
* Move the smallest disk to the peg it has not recently come from.
* Move another disk legally (there will be only one possibility).
For the very first move, the smallest disk goes to peg ''t'' if ''h'' is odd and to peg ''r'' if ''h'' is even.

Also observe that:
* Disks whose ordinals have even parity move in the same sense as the smallest disk.
* Disks whose ordinals have odd parity move in opposite sense.
* If ''h'' is even, the remaining third peg during successive moves is ''t'', ''r'', ''f'', ''t'', ''r'', ''f'', etc.
* If ''h'' is odd, the remaining third peg during successive moves is ''r'', ''t'', ''f'', ''r'', ''t'', ''f'', etc.

With this knowledge, a set of disks in the middle of an optimal solution can be recovered with no more state information than the positions of each disk:
* Call the moves detailed above a disk's "natural" move.
* Examine the smallest top disk that is not disk 0, and note what its only (legal) move would be: if there is no such disk, then we are either at the first or last move.
* If that move is the disk's "natural" move, then the disk has not been moved since the last disk 0 move, and that move should be taken.
* If that move is not the disk's "natural" move, then move disk 0.

=== Binary solution ===
Disk positions for an ''n''-disk puzzle can be determined directly from the [[Binary numeral system|binary]] representation of the move number, ''m''. For example, all the details for move ''m''=216 of an 8-disk Tower of Hanoi can be computed without any iteration or recursion, and without reference to any previous moves or distribution of disks. Conversely, given a legal disk distribution, the move number to achieve that distribution can be computed.

Let the disks be labeled ''n'', ''n''-1,…,1, in decreasing size. Let the pegs '''A''', '''B''', and '''C''' be labeled 0, 1, and 2 respectively, with 0 always being the starting peg and 2 always being the ending peg. Further, let the bases for the pegs upon which the disks are stacked be labeled ''n''+1, ''n''+2, and ''n''+3, for pegs 0, 1, and 2 respectively.

The disk positions after move ''m'' can be mapped from the binary representation of ''m'' by the following rules:<ref>T.R. Walsh, ''The Towers of Hanoi revisited: moving the rings by counting the moves'', Information Processing Letters, 1982, Vol.15, 64-67. Netherlands.</ref>

* There is 1 binary digit (bit) in ''m'' for each disk.

* The bitstring for ''m'' is read from left to right, and each bit can be used to map the location of the corresponding disk, from disk ''n'' to disk 1.
* The most significant (leftmost) bit represents the largest disk, disk ''n''. A value of 0 indicates that the largest disk is on the starting peg 0 ('''A'''), while a 1 indicates that it is on the final peg 2 ('''C''').
* After any move:

# Each disk is stacked on another disk, or an empty base, in opposite [[Parity (mathematics)|parity]] order. That is to say: 5>4>3 (3 over 4 over 5) is valid; 5>4>2 (with 2 over 4) is invalid.
# Exactly 1 of the top labels (disk number or empty base) is even (for even ''n;'' otherwise exactly 1 is odd).
# A bit with the same value as the previous digit means that the corresponding disk is stacked on top of the previous disk. That is to say: a contiguous sequence of 1s or 0s means that the corresponding disks are all on the same peg.

* A bit with a different value than the previous one means that the corresponding disk is on another peg and not on the previous stack. Given 1) above, only 1 choice of the remaining 2 pegs is a legal placement. Note that after the placement of the first set of disks, every “placement round” starts and ends with 1 of the potential pegs having even parity, the other having odd.

For example, in 8-disk Tower of Hanoi:

* Move 0 = 00000000.
** The largest disk (leftmost) bit is 0, so it is on the starting peg (0).
** All other disks are 0 as well, so they are stacked on top of it. Hence all disks are on the starting peg, in the puzzle's initial configuration.
* Move 255<sub>10</sub> (2<sup>8</sup> − 1) = 11111111.
** The largest disk bit is 1, so it is on the final peg (2).
** All other disks are 1 as well, so they are stacked on top of it. Hence all disks are on the final peg and the puzzle is solved.
* Move 216<sub>10</sub> = 11011000.
** The largest disk bit is 1, so disk 8 is on the final peg (2). Note that it sits on base number 11 (11>8).
** Disk 7 is also 1, so it is stacked on top of disk 8 (11>8>7).
** Disk 6 is 0, so it is on another peg. Peg 1 is empty but its base number is 10.  The 6 disk cannot sit on the 10 base (both are even).  Therefore disk 6 is placed on peg 0 (9>6).
** Disk 5 is 1, so it is on another peg. Since peg 2 is now topped with 7, it cannot go there. Therefore disk 5 is placed on peg 1 (10>5).
** Disk 4 is also 1, so it is stacked on top of disk 5 (10>5>4).
** Disk 3 is 0, so it is on another peg. Since peg 2 is topped with 7, it cannot go there. Disk 3 is placed on peg 0 (9>6>3).
** Disks 2 and 1 are also 0, so they are stacked on top of disk 3 (9>3>2>1).

The source and destination pegs for the ''m''th move (excluding move 0) can be found elegantly from the binary representation of ''m'' using [[Bitwise operation|bitwise operations]]. To use the syntax of the [[C programming language]], move ''m'' is:

from peg<code>(m & m - 1) % 3</code> to peg <code>((m | m - 1) + 1) % 3</code>.

Another formulation for this is:

from peg <code>(m - (m & -m)) % 3</code> to peg <code>(m + (m & -m)) % 3</code>. 

These hold for odd ''n'' puzzles.  For even ''n'' puzzles, the output references to pegs 1 and 2 need to be reversed.

Furthermore, the single disk to be moved for any specific move is determined by the number of times the move count (''m'') can be divided by 2 (i.e. the number consecutive zero bits at the right of ''m''), and then adding 1.  In the example above for move 216, with 3 right hand 0s, disk 4 (3 + 1) is moved from peg 2 to peg 1.

=== Gray-code solution ===
{{More citations needed section|date=January 2024}}
The binary numeral system of [[Gray code]]s gives an alternative way of solving the puzzle. In the Gray system, numbers are expressed in a binary combination of 0s and 1s, but rather than being a standard [[positional numeral system]], the Gray code operates on the premise that each value differs from its predecessor by only one bit changed.

If one counts in Gray code of a bit size equal to the number of disks in a particular Tower of Hanoi, begins at zero and counts up, then the bit changed each move corresponds to the disk to move, where the least-significant bit is the smallest disk, and the most-significant bit is the largest.

: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 technique identifies which disk to move, but not where to move it to. For the smallest disk, there are always two possibilities. For the other disks there is always one possibility, except when all disks are on the same peg, but in that case either it is the smallest disk that must be moved or the objective has already been achieved. Luckily, there is a rule that does say where to move the smallest disk to. Let ''f'' be the starting peg, ''t'' the destination peg, and ''r'' the remaining third peg. If the number of disks is odd, the smallest disk cycles along the pegs in the order ''f'' → ''t'' → ''r'' → ''f'' → ''t'' → ''r'', etc. If the number of disks is even, this must be reversed: ''f'' → ''r'' → ''t'' → ''f'' → ''r'' → ''t'', etc.<ref>{{cite book |first=Charles D. |last=Miller |title=Mathematical Ideas |chapter=Ch. 4: Binary Numbers and the Standard Gray Code |edition=9 |publisher=Addison Wesley Longman |year=2000 |isbn=978-0-321-07607-6 |url-status=dead |archive-url=https://web.archive.org/web/20040821062630/http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower |archive-date=2004-08-21 |url=http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html }}</ref>

The position of the bit change in the Gray code solution gives the size of the disk moved at each step: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... {{OEIS|id=A001511}},<ref>{{Cite book|title=Théorie du Baguenodier|last=Gros|first=L.|publisher=Aimé Vingtrinier|year=1872|location=Lyon}}</ref> a sequence also known as the [[ruler function]], or one more than the power of 2 within the move number. In the [[Wolfram Language]], <code>IntegerExponent[Range[2^8 - 1], 2] + 1</code> gives moves for the 8-disk puzzle.