The Magnetic Tower of Hanoi (MToH) puzzle is a variation of the classical Tower of Hanoi puzzle (ToH), where each disk has two distinct sides, for example, with different colors "red" and "blue". The rules of the MToH puzzle are the same as the rules of the original puzzle, with the added constraints that each disk is flipped as it is moved, and that two disks may not be placed one on another if their touching sides have the same color. Each disk has a North and South pole, with similar poles repelling one another and opposite poles attracting one another. Magnets inside each disk physically prevent illegal moves.
One of the striking features of the classical ToH puzzle is its relation to the base 2: the minimum number of total moves required to solve the puzzle is 2n − 1 (where n is the number of disks), while the minimum number of moves made by disk k is 2k − 1 (disks are numbered bottom up so that k = 1 being the largest disk, and k = n being the smallest). It will be shown below that just as the original ToH puzzle is related to base 2, so the MToH is related to base 3, though in a more complex manner.
Origin Mathematically equivalent puzzles to certain variations of the MToH have been known for some time. For example, an equivalent puzzle to one of the colored variations of the MToH appears in Concrete Mathematics. In this puzzle moves are only allowed between certain posts, which is equivalent to assigning permanent colors to the posts (e.g. if two posts have the same permanent color assigned to them, then direct moves are not allowed between the two posts). The free (non-colored) MToH first appeared publicly on the internet around 2000 (though under the name of "Domino Hanoi") as part of a detailed review by the Mathematician Fred Lunnon of the different variations of the original Tower of Hanoi puzzle. The MToH was independently invented by the Physicist Uri Levy in the summer of 1984, who also coined the name and the analogy to magnetism. Dr Levy later published a series of papers dealing with the mathematical aspects of the MToH.
Puzzle description
The MToH puzzle consists of three posts labeled source (S), destination (D), and intermediate (I), and a stack of n different sized disks with each side of a disk having a different color, either Red or Blue. At the beginning of the puzzle the disks are stacked on the S post in order of decreasing size (i.e. the largest disk is at the bottom), and such that all disks have their Red side facing upwards. The objective of the puzzle (in its "basic" version) is to move the entire stack, one disk at a time, to the D post, maintaining the order from largest to smallest disk, but with the Blue sides facing upwards.
The rules governing the movement of the disks are as follows:
A larger disk cannot be laid on top of a smaller disk (as in the original ToH) When a disk is moved, it is flipped, i.e. the color that was facing up now faces down Two sides of different disks with the same color may not touch each other (for example, a disk with its Blue side facing downwards cannot be placed on top of a disk that has its Blue side facing upwards).
Puzzle solution for n = 2 and n = 3 In order to illustrate the rules of the MToH, and also show the route to a more general solution, it is useful to work through examples for n = 2 and n = 3. For the case of n = 2, four steps are required, as shown in the accompanying figure, compared to three steps in the n = 2 case of the original ToH. The extra step is required because after the second step the small disk cannot be moved directly from the I post to the D post, as this would mean that its Blue side would be facing downwards. Thus, an extra step is required to flip the color of the small disk, so that it can then be placed on the D post with its Blue side facing upwards.
For the n = 3 case, the solution involves the following steps:
Numbering the disks 1 to 3 from largest to smallest, one first moves disks 2 and 3 from the S post to the I post (four moves) This first stage is similar to the n = 2 puzzle described above, which also takes four moves, where the D and I posts are interchanged. However, it is not identical to the n = 2 puzzle due to the presence of the large disk on the S post, which "colors" it red. This means that a disk can only be placed on this post with its red side facing upwards.
Move disk 1 from S to D (one move) At this stage one might be tempted to again make use of the n = 2 puzzle, and try to move disks 2 and 3 from I to D in 4 moves. However, here again care is needed. Due to the presence of disk 1 on D, D is now "colored" Blue, i.e. another disk can be placed on it only if it has its Blue side facing up. Furthermore, with the n = 2 puzzle the disks have their red side facing upwards in the starting position, whereas here they have their blue sides facing upwards. Thus, this intermediate configuration is not equivalent to the n = 2 MToH. Instead, we proceed as follows:
Move disk 3 from I to D via S (2 moves) Move disk 2 from I to S (1 move) Move disk 3 from D to I (1 move) Move disk 2 from S to D (1 move) Move disk 3 from I to D (1 move) Thus, the solution requires 11 steps altogether. As just shown, it is natural to try to use the n = 2 solution to solve parts of the n = 3 puzzle in a recursive manner, as typically used for solving the classical ToH puzzle. However, in contrast to the classical ToH, here the n = 2 solution cannot be blindly applied due to the coloring of the posts and disks. This point illustrates that to achieve a more general solution for the n-disk MToH puzzle, it is necessary to consider variants of the puzzle where the posts are pre-colored (either Blue or Red). By considering these variants it is possible to develop full recursive relations for the MToH puzzle, and thus find a general solution.
Colored variations of the MToH puzzle
… excerpt ends here. Continue reading the full article.
