Hanoi towers - a theoretical solution without recursion

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

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, and the rings differ in size and lie smaller on the larger. The task is to transfer a 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.

The classical solution to this problem with three rods suggests that for a given number of rings n, the number of shifts is calculated by the formula
.

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

In the Great Temple of Benares, under the cathedral marking 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 when creating the world, to another rod, the tower and the temple will turn to dust and the world will die under thunder.

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

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

Alexander Busarov MrShoor wrote a very informative post , perfectly complementing the corresponding Wikipedia article , with a very detailed program code, I recommend that you familiarize yourself 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 Wikipedia article:

Gray codes are used in solving the problem of Hanoi towers. Let N be the number of disks. We start with a Gray code of length N consisting of only zeros (that is, G (0)), 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 first 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). For the smallest disk, there are always two moves, but there is a move selection strategy that always leads to the answer: if N is odd,

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

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

(1) .
The remaining larger disks can be ignored, which is very convenient under the more general assumption of an infinite number of disks in the initial three-rod problem.

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

Due to the fractality of the solution, which was described in the sources mentioned above, it becomes obvious that due to the "nesting" of solutions into each other, the relationship between the binary code of the move number and the number of the moved disk is visible.

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

In the same Pascal / Delphi notation that MrShoor uses in his 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 the given weight was last moved:

.

The code for determining the num_move move number of the last disk move with weight i may look similar (with the condition that the Math module is enabled):

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 the way in the q_move variable, the number of disk movements with a weight i from the beginning of the game is obtained .

So, in the interim, we know how many times each disc has been moved during the game after each move. Now we will decide on where each disk moved.

As noted on Wikipedia, the movement of the upper disk is cyclical and, when choosing a certain destination rod t, if N is odd, then the sequence of movements of the smallest disk has the form 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 makes a similar cyclic movement during its own moves. Given this fact, it becomes obvious that, depending on the parity of the disk number, the cycle of moving the odd disk coincides with the cycle of moving the first disk, and the cycle of moving even disks differs in the order of the rods t and r.
In particular, knowing the number of q_move moves and the parity of the current disk number, you can simply divide by 3 the remainder to determine the last pivot where this disk was moved.

Therefore, having at the input the total number of disks N, the selected destination rod t and the current move number m, it is possible to restore the position of all disks in the optimal solution without resorting to recursive algorithms.

For those who are interested in variations of the Hanoi tower problem, in particular, cases of 4 or more rods, I suggest that you familiarize yourself with the experience of PapaBubaDiop , which develops this direction in the form of games, simultaneously 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 their own results.

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

UPD: Thank you all for your comments, comments and tips. An example of a script working according to the above algorithm is available at this link . The GMP library was used to support work with large numbers.