Tower of Hanoi
The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape.
In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day.
The minimal number of moves required to solve a Tower of Hanoi puzzle with n disks is 2n − 1.
The key to solving a problem recursively 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], and the total solution is then found in some simple way from those sub-problems' solutions.
The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm, has many regularities.
The binary numeral system of Gray codes gives an alternative way of solving the puzzle.
For three disks the graph is: The sides of the outermost triangle represent the shortest ways of moving a tower from one peg to another one.
As more disks are added, the graph representation of the game will resemble a fractal figure, the Sierpiński triangle.
[17][18] In Cyclic Hanoi, we are given three pegs (A, B, C), which are arranged as a circle with the clockwise and the counterclockwise directions being defined as A – B – C – A and A – C – B – A, respectively.
The solution can be found using two mutually recursive procedures: To move n disks counterclockwise to the neighbouring target peg: To move n disks clockwise to the neighbouring target peg: Let C(n) and A(n) represent moving n disks clockwise and counterclockwise, then we can write down both formulas: The solution for the Cyclic Hanoi has some interesting properties: Although the three-peg version has a simple recursive solution long been known, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle) was not verified until 2014, by Bousch.
[21] For the formal derivation of the exact number of minimal moves required to solve the problem by applying the Frame–Stewart algorithm (and other equivalent methods), see the following paper.
[22] For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper.
Hinz and Chan Tat-Hung independently discovered[27][28] (see also [29]: Chapter 1, p. 14 ) that the average number of moves in an n-disk Tower is given by the following exact formula: For large enough n, only the first and second terms do not converge to zero, so we get an asymptotic expression:
An alternative explanation for the appearance of the constant 466/885, as well as a new and somewhat improved algorithm for computing the shortest path, was given by Romik.
[30] In Magnetic Tower of Hanoi, each disk has two distinct sides North and South (typically colored "red" and "blue").
This variation of the famous Tower of Hanoi puzzle was offered to grade 3–6 students at 2ème Championnat de France des Jeux Mathématiques et Logiques held in July 1988.
A variation of the puzzle has been adapted as a solitaire game with nine playing cards under the name Tower of Hanoy.
There also exists a variant of this task called Tower of London for neuropsychological diagnosis and treatment of disorders of executive function.
[39] As mentioned above, the Tower of Hanoi is popular for teaching recursive algorithms to beginning programming students.
A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing M-x hanoi.
[citation needed] The Tower of Hanoi is also used as a test by neuropsychologists trying to evaluate frontal lobe deficits.
[40] In 2010, researchers published the results of an experiment that found that the ant species Linepithema humile were successfully able to solve the 3-disk version of the Tower of Hanoi problem through non-linear dynamics and pheromone signals.
The protagonist knows that a rescue ship might take a year or more to arrive, so he chooses to play Towers of Hanoi with 64 disks.
This story makes reference to the legend about the Buddhist monks playing the game until the end of the world.
[42][43][44] In the 1966 Doctor Who story The Celestial Toymaker, the eponymous villain forces the Doctor to play a ten-piece, 1,023-move Tower of Hanoi game entitled The Trilogic Game with the pieces forming a pyramid shape when stacked.
[43][45] In 2007, the concept of the Towers Of Hanoi problem was used in Professor Layton and the Diabolical Box in puzzles 6, 83, and 84, but the disks had been changed to pancakes.
Since it is easy to implement, and easily recognised, it is well suited to use as a puzzle in a larger graphical game (e.g. Star Wars: Knights of the Old Republic and Mass Effect).
Sook Jai threw the challenge to get rid of Jed even though Shii-Ann knew full well how to complete the puzzle.
The problem is featured as part of a reward challenge in a 2011 episode of the American version of the Survivor TV series.
Both players (Ozzy Lusth and Benjamin "Coach" Wade) struggled to understand how to solve the puzzle and are aided by their fellow tribe members.
