Tower of hanoi

Model of the Tower of Hanoi with eight discs

Tower of Hanoi is one of the popular puzzles of the 19th century . Three rods are given, on one of which eight rings are strung, and the rings differ in size and lie smaller on the larger. The challenge is to transfer the pyramid of eight rings in the least number of moves to another rod. Only one ring can be transferred at a time, and you cannot put a larger ring on a smaller one.

Content

Puzzle Story

This game was invented by the French mathematician Eduard Luke in 1883 ^[1] , it was sold as a fun toy. It was originally called "Professor Klaus (Claus) from the College of Li-Su-Stian (Li-Sou-Stian)" ^[1] , but it soon became clear that the mysterious professor from a non-existent college is nothing more than an anagram of the name of the inventor of the game, Professor Luke ( Lucas) from Saint Louis College.

Four-disc puzzle progress

Solution

Flowchart of recursive decision algorithm

There are several approaches to the solution.

Recursive Solution

We recursively solve the problem “transfer a tower from n −1 disk to the 2nd pin”. Then we transfer the largest disk to the 3rd pin, and recursively solve the problem “transfer a tower from n −1 disk to the 3rd pin”.

From this we conclude by mathematical induction that the minimum number of moves necessary to solve the puzzle is 2 ⁿ - 1, where n is the number of disks ^[2] ^[3] .

In computer science, tasks based on the legend of the Tower of Hanoi are often considered as examples of using recursive algorithms and converting them to non-recursive ones.

Triangular Decision

Place the pins in the shape of a triangle. Let's start with the smallest ring and shift it to any mark. In the future, this ring must be moved in the same direction as during the first shift. Then we transfer one of the remaining rings (such a move is unique), after which we again shift the smallest ring, etc. (It is interesting to note that by renumbering the “rings” in order, we will achieve an unexpected effect: even rings will move from one vertex a triangle in the other in one direction, and odd ones in the opposite direction.)

Loop

We denote by “1-2” the following action: shift the disk either from the 1st pin to the 2nd, or from the 2nd to the 1st, depending on where it is smaller. Then, in order to solve the puzzle with an even number of disks, it is necessary to repeat the steps many times: 1-2, 1-3, 2-3. If the number of disks is odd - 1-3, 1-2, 2-3.

Applying a Gray Code to a Solution

Gray code , a reflex binary code in a binary number system in which two adjacent values differ only in one binary digit. Initially, the Gray code was intended to protect against false triggering of electromechanical switches. Today, Gray codes are widely used to simplify the identification and correction of errors in communication systems, as well as in the formation of feedback signals in control systems. The code received the name of Bell Gray Lab researcher Frank Gray. He patented (under number 2632058) and used this code in his impulse communication system.

Gray codes can be applied in solving the problem of Hanoi towers.
Let N be the number of disks. Let's start with the Gray code of length N, consisting of only zeros (that is, G ₀ ), and we will move along the Gray codes (go from G _i to G _{i + 1} ). We associate each i-th bit of the current Gray code with the i-th disk (the smallest disk corresponds to the smallest bit and the largest bit to the oldest bit). Since exactly one bit changes at each step, we can understand the change in bit i as the movement of the i-th disk. Note that for all disks except the smallest, at each step there is exactly one move option (with the exception of the start and final positions). There are always two options for the smallest disk, but there is a strategy for choosing the right course: for odd N, the sequence of movements of the smallest disk is f → t → r → f → t → r → ... (where f is the start bar, t is the final bar, r - remaining core), and for an even f → r → t → f → r → r → t → ....

Algorithm implementations

An example of a solution algorithm in C ++ :

  // Hanoi towers
 #include <iostream> 

 using namespace std ;

 void hanoi_towers ( int quantity , int from , int to , int buf_peg ) // quantity-number of rings, from-initial position of the rings (1-3), to-final position of the rings (1-3)
 { // buf_peg - intermediate peg (1-3)
	 if ( quantity ! = 0 )
	 {
		 hanoi_towers ( quantity - 1 , from , buf_peg , to );

		 cout << from << "->" << to << endl ;

		 hanoi_towers ( quantity - 1 , buf_peg , to , from );
	 }
 }

 int main ()
 {
         setlocale ( LC_ALL , "rus" );
	 int start_peg , destination_peg , buffer_peg , plate_quantity ;
	 cout << "Number of the first column:" << endl ;
	 cin >> start_peg ;
	 cout << "End column number:" << endl ;
	 cin >> destination_peg ;
	 cout << "The number of the intermediate column:" << endl ;
	 cin >> buffer_peg ;
	 cout << "Number of disks:" << endl ;
	 cin >> plate_quantity ;

	 hanoi_towers ( plate_quantity , start_peg , destination_peg , buffer_peg );
 return 0 ;
 }

An example of a solution algorithm in Pascal :

  program hanoibns ( input , output ) ;
 var n : integer ;
 procedure tower ( k : integer ; a , b , c : char ) ;
 begin
      if k > 1 then tower ( k - 1 , a , c , b ) ;
      writeln ( 'from' , a , 'to' , b ) ;
      if k > 1 then tower ( k - 1 , c , b , a )
 end ;
 begin
      read ( n ) ;
      tower ( n , 'A' , 'C' , 'B' )
 end .

An example of a solution algorithm in Python :

  def Hanoi ( n , A , C , B ):
     if n ! = 0 :
         Hanoi ( n - 1 , A , B , C )
         print 'Move the plate from' , A , 'to' , C
         Hanoi ( n - 1 , B , C , A )

Example solution algorithm in Java :

  public class Hanoi {
     public static void hanoiTowers ( int quantity , int from , int to , int buf_peg ) {
         if ( quantity ! = 0 )
         {
             hanoiTowers ( quantity - 1 , from , buf_peg , to );

             System  out .  println ( "" + from + "->" + to );

             hanoiTowers ( quantity - 1 , buf_peg , to , from );
         }
     }

     public static void main ( String [] args ) {
         int start_peg = 1 , destination_peg = 2 , buffer_peg = 3 , plate_quantity = 4 ;
         hanoiTowers ( plate_quantity , start_peg , destination_peg , buffer_peg );
     }
 }

An example of an iterative solution algorithm in C

  #include <stdio.h>   #include <math.h>   void carryingOver ( int , int , int );  main () { int number , countDisk , counter = 1 , count ;  printf ( "Enter the number of disks:" );  / * Tower of Hanoi * / scanf ( "% d" , & number );  while ( counter <= pow ( 2 , number ) - 1 ) { / * Start the iteration cycle * / if ( counter % 2 ! = 0 ) { / * On the odd move we will touch only the smallest disk * / printf ( "% 3d% d " , counter , 1 );  carryingOver ( number , counter , 1 );  / * Using this function, we determine the movement for a given disk * / } else { / * We determine the disk that needs to be moved on an even move * / count = counter ;  countDisk = 0 ;  while ( count % 2 == 0 ) { / * Disk to be moved * / countDisk ++ ;  / * is the number of division of the move number by 2 without a remainder * / count = count / 2 ;  } printf ( "% 3d% d" , counter , countDisk + 1 );  carryingOver ( number , counter , countDisk + 1 );  } counter ++ ;  } return 0 ;  } / * Function for determining the movement of disks * / void carryingOver ( int n , int i , int k ) { int t , axisX , axisY , axisZ ;  if ( n % 2 == 0 ) { / * Determine the order of the axes depending on the parity * / axisX = 1 ;  / * and not parity of the number of disks * / axisY = 2 ;  axisZ = 3 ;  } else { axisX = 1 ;  axisY = 3 ;  axisZ = 2 ;  } / * The move number can be represented uniquely * / / * as the product of a certain odd number by a power of two * / / * k will be the number of the disk we are moving * / t = (( i / pow ( 2 , k - 1 )) - 1 ) / 2 ;  if ( k % 2 ! = 0 ) { / * Determine the displacement of the disks for an odd move * / switch ( t % 3 ) { / * Choose the displacement depending on this condition * / case 0 : printf ( "% d ->% d \ n " , axisX , axisY );  break ;  case 1 : printf ( "% d ->% d \ n " , axisY , axisZ );  break ;  case 2 : printf ( "% d ->% d \ n " , axisZ , axisX );  break ;  } } else { / * Determine the disk movement for the even move * / switch ( t % 3 ) { case 0 : printf ( "% d ->% d \ n " , axisX , axisZ );  break ;  case 1 : printf ( "% d ->% d \ n " , axisZ , axisY );  break ;  case 2 : printf ( "% d ->% d \ n " , axisY , axisX );  break ;  } } }

There are visualization programs for solving this puzzle.

Options

With four or more rods.

Although the three-rod option has a simple recursive solution, the optimal solution to the four-rod tower of Hanoi has long been an unresolved problem.

Obviously, for any number of rods there is an algorithm for finding optimal solutions, it is enough to imagine the puzzle in the form of an undirected graph, matching the locations of the disks of the vertex and the edges with edges, and use any search algorithm (for example, breadth-first search ) to find the optimal solution. However, there is no effective strategy for determining the optimal solution for a large number of disks: the number of moves necessary to solve the puzzle with 10 rods and 1000 disks remains unknown.

There is a presumably optimal Frame – Stuart algorithm developed in 1941 ^[4] . The related frame-Stewart hypothesis states that the frame-stewart algorithm always finds the optimal solution. The optimality of the Frame – Stuart algorithm has been experimentally verified up to 30 disks on 4 rods ^[5] . In 2014, it was finally proved that the Frame – Stuart Algorithm is optimal for four rods ^[6] .

Other options for solving the Hanoi tower with four rods are discussed in a review article by Paul Stockmeier ^[7] .

Frame - Stuart Algorithm

The Frame-Stuart algorithm, which gives an optimal solution for four and a supposedly optimal solution for a larger number of rods, is described as follows:

Let be $n$ ${\ displaystyle n}$ - number of disks.
Let be $r$ ${\ displaystyle r}$ - the number of rods.
Define $T(n,r)$ ${\ displaystyle T (n, r)}$ as the smallest number of moves needed to transfer n disks using r rods.

The algorithm can be described recursively:

For some $k$ ${\ displaystyle k}$ , $1\leq k<n$ ${\ displaystyle 1 \ leq k <n}$ move the top $k$ ${\ displaystyle k}$ on the rod i , which is neither the initial nor the final rod, spending on it $T(k,r)$ ${\ displaystyle T (k, r)}$ moves.
Without using rod i , now containing the upper $k$ ${\ displaystyle k}$ drives transfer the remaining $n-k$ ${\ displaystyle nk}$ drives to the final rod using only the remaining $r-1$ ${\ displaystyle r-1}$ rods and spending on it $T(n-k,r-1)$ ${\ displaystyle T (nk, r-1)}$ moves.
Finally, move the top $k$ ${\ displaystyle k}$ drives on the final rod, spending on it $T(k,r)$ ${\ displaystyle T (k, r)}$ moves.

The whole process requires $2T(k,r)+T(n-k,r-1)$ ${\ displaystyle 2T (k, r) + T (nk, r-1)}$ moves. Value $k$ ${\ displaystyle k}$ is chosen so that the value of this expression is minimal. In the case of 4 rods, the optimal $k$ ${\ displaystyle k}$ equally $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ ${\ displaystyle n- \ left \ lfloor {\ sqrt {2n + 1}} \ right \ rceil +1}$ where $\left\lfloor \cdot \right\rceil$ ${\ displaystyle \ left \ lfloor \ cdot \ right \ rceil}$ is a function of the nearest integer . ^[eight]

Legends

A legend invented by Professor Luke says that in the Great Temple of Benares , under the cathedral, which marks the middle of the world , there is a bronze disk on which 3 diamond rods are fixed, one elbow in height and the thickness of a bee. Once upon a time, at the very beginning of time, the monks of this monastery were guilty before the god Brahma. Enraged, Brahma erected three high rods and placed 64 discs made of pure gold on one of them. Moreover, so that each smaller disk lies on a larger one.

As soon as all 64 disks are shifted from the rod to which Brahma put them during the creation of the world, to another rod, the tower and the temple will turn to dust and the world will die under thunder.

The number of shifts depending on the number of rings is calculated by the formula $2^{n}-1$ ${\ displaystyle 2 ^ {n} -1}$ .

The number of disks to be performed by the monks is 18,446,744,073,709,709,551,615 . If the monks, working day and night, did one movement of the disk every second, their work would last almost 585 billion years .

In Culture

In the story of Eric Frank Russell, “Your move” (Now Inhale, in another translation - “Survival Game”) ^[9] , in order to delay the time of execution by aliens, the protagonist chooses the game in the Tower of Hanoi with 64 discs as the last game. The announced rules are modified for two players - players must shift discs one at a time, the winner is the one who makes the last move. The hero calls such a game "arch malarki" and swears that the "clergy of the Benares Temple" on Earth play this game.

In the film " Rise of the Planet of the Apes, " the Tower of Hanoi is used as a test of intelligence in experimental subjects. The monkey collects a puzzle of four rings in twenty moves.

The Tower of Hanoi is one of the traditional puzzles in the video games of the Canadian company BioWare - in particular, “ Jade Empire ”, “ Star Wars: Knights of the Old Republic ” and “ Mass Effect ”. They are found in the quest Legend of Kyrandia II.

Notes

↑ ¹ ² Martin Gardner, Math puzzles and fun
↑ Petković, Miodrag. Famous Puzzles of Great Mathematicians. - AMS Bookstore, 2009 .-- P. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Concrete Mathematics: A Foundation for Computer Science. - Addison – Wesley, 1998. - P. 21. - ISBN 0201558025 .
↑ Solution to advanced problem 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E., and Ariel Felner. Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem (English) // IJCAI : journal. - 2007 .-- P. 2324-2329 .
↑ Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. Belg. Math. Soc. Simon Stevin . - 2014 .-- T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Variations on the Four-Post Tower of Hanoi Puzzle (Neopr.) // Congressus Numerantium. - 1994 .-- T. 102 . - S. 3-12 .
↑ University of Toronto CSC148 Slog (neopr.) (April 5, 2014). Date of treatment July 22, 2015.
↑ Russell, Eric Frank. Your move (unopened) // If . - 1994. - April. - S. 34–42 .

Links

sequence A007664 in OEIS
Konstantin Knop. Tower of Hanoi (neopr.) . Elements (October 22, 2012).
Online game Tower of Hanoi

[ReferenceA-1] ¹ ² Martin Gardner, Math puzzles and fun

[2] Petković, Miodrag. Famous Puzzles of Great Mathematicians. - AMS Bookstore, 2009 .-- P. 197. - ISBN 0-8218-4814-3 .

[3] Graham, Ronald. Concrete Mathematics: A Foundation for Computer Science. - Addison – Wesley, 1998. - P. 21. - ISBN 0201558025 .

[4] Solution to advanced problem 3819, American Mathematical Monthly , 1941.

[5] Korf, Richard E., and Ariel Felner. Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem (English) // IJCAI : journal. - 2007 .-- P. 2324-2329 .

[6] Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. Belg. Math. Soc. Simon Stevin . - 2014 .-- T. 21 . - S. 895-912 .

[7] Paul Stockmeyer. Variations on the Four-Post Tower of Hanoi Puzzle (Neopr.) // Congressus Numerantium. - 1994 .-- T. 102 . - S. 3-12 .

[Berkey_Colortran-8] University of Toronto CSC148 Slog (neopr.) (April 5, 2014). Date of treatment July 22, 2015.

[9] Russell, Eric Frank. Your move (unopened) // If . - 1994. - April. - S. 34–42 .