Magnetic Tower of Hanoi

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 the another if their touching sides have the same color. Using an analogy to magnetism, each disk can be considered to have a North and South pole, with similar poles repelling one another and opposite poles attracting one another.
One of the striking features of the classical ToH puzzle is it's relation to the base 2: the minimum number of total moves required to solve the puzzle is 2 -1 (where n is the number of disks), while the minimum number of moves made by disk k is 2 (disks are numbered bottom up so that k1 being the largest disk, and kn 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
The 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 Red side facing downwards cannot be placed on top of a disk that has its Red side facing upwards).
Puzzle solution for n 2 and 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 n2 and n3.
For the case of n2, four steps are required, as shown in the accompanying figure, compared to 3 steps in the n2 case of the original ToH. The extra step is required due to the fact that after the second step the small disk cannot be moved directly from the I post to the D post, as this would mean that it's 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, we first move disks 2 and 3 from the S post to the I post. This stage takes 4 moves, and is similar to the n2 puzzle described above, where the D and I posts are interchanged. Note however, that it is not identical to the n2 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 (1 move)
At this stage one might be tempted to again make use of the n=2 puzzle, and try and 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 n2 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 n2 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 form D to I (1 move)
* Move disk 2 from S to D (1 move)
* Move disk 1 from I to D (1 move)
Thus, the solution requires 11 steps altogether. As just shown, it is natural to try and use the n2 solution to solve parts of the n3 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 post 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
The above description of the MToH puzzle assumes that while the disks themselves are colored, the posts are neutral. This means that an empty post may accept a disk with either its Red side or Blue side facing up. This basic version of the MToH is called the "free" MToH.
Other variations of the MToH puzzle are possible whereby the posts themselves are colored, as shown in the accompanying figure. If a post is pre-colored Red/Blue, then only disks with their Red/Blue side facing upwards may be placed on this pre-colored post. The different variations of the MToH may be named using a 3 letter label "SID", where S,I D refer to the color of the posts, and may assume the values R (Red), B (Blue), or N (Neutral - no color). Thus, the "NNN" puzzle refers to the free MToH, while the "RBB" puzzle refers to the variation where the S post is pre-colored Red, while the I and D posts are pre-colored Blue.
While the variations of the MToH are puzzles within their own right, they also play a key role in solving the free MToH. As seen above, intermediate states of the free MToH can be considered as colored variations, since a post with a disk already on it assume the corresponding color of the disk (meaning that only disk with the same color facing upwards can be placed on the post).
For example, in the free n=3 MToH puzzle described above, after 5 moves an intermediate state is reached where the large disk is on the D post. From this point on, the D post is considered to be colored Blue, and the puzzle becomes equivalent to the "NNB" puzzle. If a solution is known for the n=2 "NNB" puzzle, it could immediately be applied to complete the n=3 free puzzle.
Symmetry relations
Not all of the different colored variations are distinct puzzles, since symmetry means that some pre-colored puzzle variations are identical to others. For example, if we solve the RBB puzzle backwards, then this is the same as solving the RRB puzzle in the regular forward direction (Note - the Blue and Red colors have been swapped to keep the rule that at the start of the puzzle all disks must be on the source post with their Red side facing up). Thus, the RBB and RRB puzzles form a time reversal symmetry pair. This means that they share the same characteristics with respect to the number of optimal moves required, even though each puzzle requires a distinct algorithm to solve it. In fact, it will be shown below that puzzles forming a time reversal symmetry pair are interdependent one on the other, in the sense that the solving algorithm of one makes use of the solving algorithm of the other.
Solutions
As with the classical ToH puzzle, one of the simplest and most instructive methods for solving the MToH is to use recursive algorithms. Such algorithms are presented below for selected variations of the puzzle, and the optimality of the solutions is proved. Using these recursive algorithms, recursive relations, and subsequently closed form expressions, can be derived for the number of total moves required to solve the puzzle, and the number of moves each disk makes during the solution. The integer sequences resulting from these recursive relations are also briefly discussed.
A detailed discussion of these optimal algorithms can be found in the paper by Dr. Levy, the integer sequences generate by the other puzzle variations are far less trivial, and were not found in OEIS prior to the analysis of the MToH. These new sequences, 15 in number, are now all listed.

Main Menu

See Also

Main Menu