Tower of Hanoi; History and Solutions

tower of hanoi
tower of hanoi

The Tower of Hanoi is additionally called the Tower of Brahma or Lucas. Tower and sometimes pluralized as Towers, it is a mathematical game or puzzle. It consists of three rods and a variety of disks of various sizes, which may slide onto any rod. The puzzle starts with the disks during a neat stack in ascending order of size on one rod, the littlest at the highest, thus making a conical shape.

The objective of the puzzle is to maneuver the whole stack to a different rod, obeying the subsequent simple rules:

  • Only one disk can be moved at a time.
  • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  • No larger disk may be placed on top of a smaller disk.
  • With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to unravel a Tower of Hanoi puzzle is 2n − 1, where n is that the number of disks.

History of Tower of Hanoi

tower of hanoi solution
tower of hanoi solution

The puzzle was invented by the French mathematician Edouard Lucas in 1883. Numerous myths regarding the traditional and mystical nature of the puzzle popped up soon. These myths are recounted in the monograph The Tower of Hanoi “Myths and Maths”. There is a story about an Indian temple in Kashi Vishwanath which contains an outsized room with three time-worn posts in it, surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, are moving these disks in accordance with the immutable rules of Brahma since that point. The puzzle is therefore also referred to as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the planet will end.

If the legend were true, and if the priests were ready to move disks at a rate of 1 per second, using the littlest number of moves it might take them 264 − 1 second or roughly 585 billion years to end, which is about 42 times the present age of the Universe. There are many variations on this legend. For instance, in some telling’s the temple is a monastery, and the priests are monks. The temple or monastery could also be said to be in several parts of the planet including Hanoi, Vietnam and should be related to any religion. In some versions, other elements are introduced, like the very fact that the tower was created at the start of the planet or that the priests or monks may make only one move per day.

Solutions for the Tower of Hanoi

The puzzle is often 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 is 2n − 1, where n is the number of disks and this is precisely the nth number.

  • Iterative solution
  • Recursive solution
  • Non-recursive solution
  • Binary solution
  • Gray code solution

1. Iterative solution:

A simple solution for the toy puzzle is to alternate moves between the littlest piece and a non-smallest piece. When moving the littlest piece, always move it to subsequent position within the same direction (to the proper if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there’s no tower position within the chosen direction, move the piece to the other end, on the other hand still move within the correct direction.

2. Recursive solution:

The key to solving a drag recursively is to acknowledge that it is often weakened into a set of smaller sub-problems, to every of which that very same general solving procedure that we are seeking applies and therefore the total solution is then found in some simple way from those sub-problems solutions. The full Tower of Hanoi solution then consists of moving n disks from the source peg A to the target peg C, using B because of the spare peg. This approach is often given rigorous proof with mathematical induction.

Rules:

  • label the pegs A, B, C.
  • Let n be the total number of disks.
  • Number the disks from 1 (smallest, topmost) to n (largest, bottom-most).

3. Non-recursive solution:

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 ranging from 1, the ordinal of the disk to be moved during move m is that the number of times m are often divided by 2. Hence every odd move involves the smallest disk. It also can be observed that the littlest disk traverses the pegs f, t, r, f, t, r, etc. for the 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 subsequent algorithm, which is simpler, administered 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 and there will be only one possibility.
  • For the very first move, the smallest disk goes to peg t if it is odd and to peg r if it is even.

An important point to keep in mind:

  • Disks whose ordinals have even parity move in the same sense as the smallest disk.
  • Disks whose ordinals have odd parity move in the opposite sense.
  • If his even, the remaining third peg during successive moves is t, r, f, t, r, f, etc.
  • If his odd, the remaining third peg during successive moves is r, t, f, r, t, f, etc.

4. Binary solution:

Disk positions could also be determined more directly from the binary (base-2) representation of the move number (the initial state being move #0, with all digits 0, and therefore the final state being with all digits 1).

Rules:

  • There is one binary digit (bit) for each disk.
  • The bit string is read from left to right, and each bit can be used to determine the location of the corresponding disk.
  • A bit with the same value as the previous one means that the corresponding disk is stacked on top of the previous disk on the same peg.
  • Assume that the initial peg is on the left.
  • Also assume “wrapping” so the right peg counts as one peg “left” of the left peg, and vice versa.

Applications:

The Tower of Hanoi is usually utilized in psychological research on problem-solving. There also exists a variant of this task called the Tower of London for neuropsychological diagnosis and treatment of executive functions.

Zhang and Norman used several isomorphic (equivalent) representations of the sport to review the impact of representational effect in task design. They demonstrated an impression on user performance by changing the way that the principles of the sport are represented, using variations within the physical design of the sport components. This knowledge has impacted on the event of the framework for the representation of Human-Computer Interaction. The Tower of Hanoi is also used as a Backup rotation scheme when performing computer data Backups where multiple tapes are involved.

As mentioned above, the Tower of Hanoi is popular for teaching recursive algorithms to begin programming students. A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing M-x Hanoi. There is also a sample algorithm written in Prolog. The Tower of Hanoi is additionally used as a test by neuropsychologists trying to gauge lobe deficits. In 2010, researchers published the results of an experiment that found that the ant species Linepithema humile were successfully ready to solve the 3-disk version of the Tower of Hanoi problem through non-linear dynamics and pheromone signals.

Variations:

  • Adjacent Pegs
  • Cyclic Hanoi
  • Magnetic Hanoi
  • Bicolor Towers of Hanoi

Adjacent Pegs:

If all moves must be between adjacent pegs then moving a stack of n disks from peg A to peg C takes 3n-1 moves. The solution uses all 3n valid positions, always taking the unique move that doesn’t undo the previous move. The position with all disks at peg B is reached halfway, i.e. after (3n-1)/2 moves.

Cyclic Hanoi:

In Cyclic Hanoi, there are three pegs A, B and 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 moving direction of the disk must be clockwise. It suffices to represent the sequence of disks to be moved. The solution is often found using two mutually recursive procedures:

To move n disks counterclockwise to the neighboring target peg:

  • Move n − 1 disks counterclockwise to the target peg.
  • Move disk #n one step clockwise.
  • Move n − 1 disks clockwise to the start peg.
  • Move disk #n one step clockwise.
  • Move n − 1 disks counterclockwise to the target peg.

To move n disks clockwise to the neighboring target peg:

  • Move n − 1 disks counterclockwise to a spare peg.
  • Move disk #n one step clockwise.
  • Move n − 1 disks counterclockwise to the target peg.

The Frame–Stewart algorithm is described below:

  • Let n be the number of disks.
  • Let r be the number of pegs.
  • Define T (n , r) to be the minimum number of moves required to transfer n disks using r pegs.

The algorithm can be described recursively:

  1. Without disturbing the peg that now contains the top k disks, transfer the remaining n-k disks to the destination peg, using only the remaining r-1 pegs, taking T (n-k, r-1) moves.
  2. Finally, transfer the top k disks to the destination peg, taking T (k,r) moves.

The solution for the Cyclic Hanoi has some interesting properties:

  1. The move-patterns of transferring a tower of disks from a peg to a different peg are symmetric with reference to the middle points.
  2. The smallest disk is the first and last disk to move.
  3. Groups of the smallest disk moves alternate with single moves of other disks.
  4. The number of disks moves specified by C (n) and A (n) are minimal.

The solution for the Cyclic Hanoi has some interesting properties:

  1. The move-patterns of transferring a tower of disks from a peg to a different peg are symmetric with reference to the middle points.
  2. The littlest disk is that the first and last disk to maneuver.
  3. Groups of the littlest disk moves alternate with single moves of other disks.
  4. The amount of disks moves specified by C (n) and A (n) are minimal.

Magnetic Hanoi:

In the Magnetic Tower of Hanoi, each disk has two distinct sides North and South (typically colored “red” and “blue”). Disks must not be placed with similar poles together magnets in each disk prevent this illegal move. Also, each disk must be flipped because it is moved.

Bicolor Towers of Hanoi:

This variation of the famous Tower of Hanoi puzzle was offered to grade 3–6 students at 2eme Championnat de France des Jeux Mathematiques et Logiques held in July 1988.

The rules of the puzzle are essentially the same, disks are transferred between pegs one at a time. At no time may a much bigger disk be placed on top of a smaller one.

The difference is that now for every size there are two disks, one black, and one white. Also, there are now two towers of disks of alternating colors. The goal of the puzzle is to make the towers monochrome and same color. The biggest disks at rock bottom of the towers are assumed to swap positions.

Next, you can learn about C Programming and C Language.

Imad

I am a Software Engineer with ample experience in making games, websites, mobile apps and augmented reality solutions.

Pin It on Pinterest