page_title: Magnetic Tower of Hanoi
section_title: Markov type solution
hierarchical_section_title: Magnetic Tower of Hanoi / Solutions / Markov type solution
caption_attribution_description: English: The number of moves required for optimal solutions of different variations of the MToH puzzle
context_page_description: The Magnetic Tower of Hanoi puzzle is a variation of the classical Tower of Hanoi puzzle, 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 2ⁿ − 1, while the minimum number of moves made by disk k is 2ᵏ ⁻ ¹. 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.
context_section_description: A powerful method of analyzing the MToH puzzle (and other similar puzzles), suggested by Fred Lunnon and presented in his review of Tower puzzles variations, is a matrix method.
  In this method no effort is made to separate the various puzzles into independent groups whose solving algorithms depend only one on the other. Instead the solving algorithms are written in the most direct way so that algorithms of all the puzzle variations are interdependent. Once this has been done, the total number of moves  (S,I,D being equal to R,B,N) for each puzzle variation can be written as follows:
  Note that in contrast to the other variations and the general rule, MToH variations NNR and NBR end with the red sides of the disks facing upwards. This is a natural consequence of the destination post being colored red.
  If we now define a vector 
  Then 
  and the recursion relations can be written in the following matrix form
  where the Markov matrix  is defined by
  The equation for  can now be written as
  The characteristic polynomial of   is given by
  having the following eight roots
  and eight eigenvectors  such that
  We can now express  using the eight eigenvectors
  so that
  Now, since   for all , it is clear that
  Thus, as before we obtain the following asymptotic relation for all puzzle variations
  with the factor s given by the following table:
caption: The number of moves required for optimal solutions of different variations of the MToH puzzle
exif: {}