Towers of Hanoi - a theoretical solution without recursion

The task of the Towers of Hanoi is one of the very first tasks that are offered to novice programmers, mainly to illustrate the concept of recursive solutions. This article provides a method that allows you to theoretically, without recursion, indicate the optimal solution for the current course.

The 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, with the rings differing in size and smaller on the larger one. The task is to transfer the pyramid of eight rings for the smallest number of moves to another rod. It is allowed to transfer only one ring at a time, and you cannot put a larger ring on a smaller one.

The classical solution of this problem with three rods assumes that for a given number of rings n the number of rearrangements is calculated by the formula
.

An additional attraction to this task is given by the accompanying legend:

In the Great Temple of the city 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 high and the thickness of a bee. Long ago, at the very beginning of time, the monks of this monastery were guilty before the god Brahma. Enraged, Brahma erected three tall rods and on one of them laid 64 discs made of pure gold. And so that each smaller disk lies on a larger one. As soon as all 64 disks are shifted from the rod, on which Brahma laid them while creating the world, to another rod, the tower together with the temple will turn into dust and the world will perish under the thunder of thunder.

In the meantime, the newcomer is invited to evaluate the complexity of this decision in order to impress with the result: the number of disk movements that the monks have to make is equal to 18,446,744,073,709,551,615 . If the monks, working day and night, did one second disk movement every second, their work would last 584 billion years.

The essence of the solution is reduced to the understanding that to move the current disk, it is necessary to solve the problem of transferring all previous disks to a free core, moving the required disk and then moving back all previous smaller disks to the desired core. Thus, the solution of the problem is reduced to the previous solutions, which illustrates the recursion mechanism.

Alexander Busarov MrShoor has written a very informative post that perfectly complements the corresponding article in Wikipedia , with a very detailed program code, I recommend to get acquainted with its implementation of recursion.

In the same post there is a description of the fractal nature of the algorithm. I will try to continue this direction, revealing the application of the Gray code for this particular task.

I will quote from the corresponding article in Wikipedia:

Gray codes are used in solving the problem of the Hanoi Towers. Let N be the number of disks. We start with the Gray code of length N, consisting of only zeros (that is, G (0)), and we will move along Gray codes (from G (i) go to G (i + 1)). Let us assign each first bit of the current Gray code to the first disk (with the smallest bit corresponding to the smallest disk, and the oldest bit to the largest one). Since at each step exactly one bit changes, we can understand the change in bit I as the movement of the I-th disk. Note that for all discs except the smallest, at each step there is exactly one course option (with the exception of the starting and final positions). For the smallest disk, there are always two options for the move, however, there is a strategy for selecting the move, which always leads to the answer: if N is odd, then the sequence of movements of the smallest disk is f-> t-> r-> f-> t-> r-> (where is f-starting rod, t-final rod, r-remaining rod), and if N is even, then f-> r-> t-> f-> r-> t-> ...

The optimal solution of the problem is reduced to determining the position of the disks after the next move. At the very beginning (at zero stroke) all the disks are on the same starting rod f. The numbering of the scales of the disks is carried out from number 1 in ascending order. It is required to describe the position of the disks on the course with the number m .

Obviously, with the optimal solution after move m, the number of disks moved n will be no more than

(1) .
The remaining disks of a larger size can be disregarded, which is very convenient given the more general assumption of an infinite number of disks in the initial problem with three rods.

Further, having defined the number of disks moved, we will determine their position.

In view of the fractality of the solution, which was described in the sources mentioned above, it becomes obvious that, thanks to the “nesting” of the solutions into each other, the connection between the binary code of the move number and the number of the disk being moved is seen.

In particular, during this move, the disk whose weight " i " correlates with the maximum power of two in the binary decomposition of the number m of the current move minus one moves:
(2) .

In the same Pascal / Delphi notation that MrShoor uses in its code, this can be written as follows:

i:=0; deg2value:=1; while ((m mod deg2value) = 0) do begin i:=i+1; deg2value:=deg2value*2; end; 

Thus, for each of the disks with weight i, we can determine the move j on which the disk of a given weight was last moved:

.

The code to determine the num_move stroke number of the last disk move with weight i may look similar (with the condition for enabling the Math module):

 deg2value:=Power(2,i-1); q_move:=m div deg2value; if (q_move mod 2) = 0 then q_move:=q_move-1; num_move:=q_move * deg2value; q_move=(q_move+1) div 2; 

It is worth paying attention to the fact that along with the q_move variable, the number of disk movements with weight i from the beginning of the game is obtained.

So, in the interim, we know how many times each disc was moved during the game after each turn. Now we will decide on where each of the disks moved.

As noted in Wikipedia, the movement of the upper disk is cyclical and, when choosing a specific destination bar t, if N is odd, then the sequence of movements of the smallest disk is f-> t-> r-> f-> t-> r-> ... (where f-starting rod, t-final rod, r-remaining rod), and if N is even, then f-> r-> t-> f-> r-> t-> ...

Recalling the fractality, you can see that if you discard the upper part of the previous disks, the current disk also performs a similar cyclical movement during its own moves. Taking into account this fact, it becomes obvious that, depending on the parity of the disk number, the cycle of movement of the odd disk coincides with the cycle of movement of the first disk, and the cycle of movement of even disks differs in the order of the rods t and r.
In particular, knowing the q_move displacement number and the parity of the current disk number, it is possible by simple division by 3 of the remainder to determine the last rod where the given disk was moved.

Therefore, having the total number of disks N at the input, the selected destination rod t and the number of the current stroke m, you can restore the position of all disks at the optimal solution without resorting to recursive algorithms.

For those who are interested in variations of the task of the Tower of Hanoi, in particular, cases of 4 or more rods, I suggest to get acquainted with the experience of PapaBubaDiop , developing this direction in the form of games, while trying to monetize some versions on different platforms.

I hope that for those readers who are interested in theoretical solutions that are more optimized for such problems with a large amount of input data and computational resources, this publication will be useful in the future as a basis for your own results.

The style and language are a bit dry and are more suitable for academic work, so please do not judge it very harshly, especially considering the attempt to straighten karma and get out of the minus. All the best and bright, Happy New 2017 Year: success and success in all good!

UPD: Thank you all for the comments, comments and tips. An example of a script that works according to the above algorithm is available at this link . A GMP library was used to handle large numbers.