MrShoor November 4, 2013 at 21:30

Tower of hanoi on fingers

Having talked with some familiar programmers, I suddenly discovered that not everyone knows about the Tower of Hanoi, and among those who know, few people understand how this task is solved.
Wikipedia writes very strictly on the subject, on the case, and does not explain anything. Like, take it as a truism. Therefore, to understand how it is solved is immediately difficult. But the task is very simple, and yet interesting in programming and mathematically.

The article will have many pictures. An explanation of how to solve a problem recursively and how it is solved by binary search.
In general, the article is dedicated to those brave who are still afraid of the Tower of Hanoi, but want to stop being afraid of it.

Rules of the game

They are very simple. There is 1 pyramid with disks of different sizes, and 2 more empty pyramids. It is necessary to move disks from one pyramid to another. You can only transfer one drive per turn. Fold discs can only be smaller to larger.
So we have such a pyramid:

And we need to shift it to say on the middle axis.
If you start to solve a problem not from the beginning, but from the end - it turns out to be very simple. Let's think it over. To shift the pyramid to the second axis, we need to shift the lowermost disk, and this can only be done when the 4 upper disks are on the third axis:

In order to shift 4 disks to the third axis, it is essentially necessary to solve the same problem, but for 4- x drives. That is, on the third axis we can shift the 4th disk only when we have 3 disks on the second axis:

Feel the recursion?
Transferring a stack of 5 disks is:
1. Transferring a stack of 4 disks to an independent axis
2. Transferring a 5th disk to an axis we need
3. Transferring a stack of 4 disks to an axis we need

In turn, transferring a stack of 4 disks is :
1. Transferring a stack of 3 disks to an independent axis
2. Transferring a 4th disk to an axis we need
3. Transferring a stack of 3 disks to an axis we need

That's all.

Recursive implementation

After such a detailed description, it will not be difficult to implement this algorithmically.

Delphi implementation

So I described a module with turret types:

unit untHTypes;
interface
const MaxRingCount = 5;
type
  TTower = record
    RingCount: Integer;
    Rings: array [0..MaxRingCount-1] of Integer;
    procedure MoveRing(var AtTower: TTower);
  end;
  TTowers = array [0..2] of TTower;
procedure InitTowers(var towers: TTowers);
implementation
procedure InitTowers(var towers: TTowers);
var i: Integer;
begin
  towers[0].RingCount := MaxRingCount;
  towers[1].RingCount := 0;
  towers[2].RingCount := 0;
  for i := 0 to MaxRingCount - 1 do
  begin
    towers[0].Rings[i] := MaxRingCount - i;
    towers[1].Rings[i] := 0;
    towers[2].Rings[i] := 0;
  end;
end;
{ TTower }
procedure TTower.MoveRing(var AtTower: TTower);
begin
  Assert(RingCount > 0);
  Assert(AtTower.RingCount - 1 < MaxRingCount);
  if AtTower.RingCount > 0 then
    Assert(Rings[RingCount - 1] < AtTower.Rings[AtTower.RingCount - 1]);
  Dec(RingCount);
  AtTower.Rings[AtTower.RingCount] := Rings[RingCount];
  Rings[RingCount] := 0;
  Inc(AtTower.RingCount);
end;
end.

TTower is a structure describing a tower. In it, the RingCount stores the number of actually dressed rings on the tower. The size of the rings is stored in the Rings array from 1 to MaxRingCount. Since we have 3 towers, the TTowers = array [0..2] of TTower type was declared;
Also, from the tower, you can shift the upper ring to another using the MoveRing function. The function checks the correctness of the operation through Assert-s.
The tower solution itself is in the project file:

program Hanoy;
{$APPTYPE CONSOLE}
uses
  SysUtils,
  untHTypes in 'untHTypes.pas';
{$R *.res}
procedure SolveHanoy;
var towers: TTowers;
  function GetThirdIndex(index1, index2: Integer): Integer; //по двум имеющимся осям возвращает третью независимую ось
  begin                                                     //на которую временно можно переложить стек
    Assert(index1 <> index2);
    case index1 of
      0: if index2 = 1 then Result := 2 else Result := 1;
      1: if index2 = 2 then Result := 0 else Result := 2;
      2: if index2 = 0 then Result := 1 else Result := 0;
    else
      Assert(False,'wrong indeces');
    end;
  end;
  procedure MoveStack(stacksize: Integer; fromindex, atindex: Integer); //перемещает стек из пирамидок с одной оси на другую
  var thirdindex: Integer;
  begin
    if stacksize = 0 then Exit;
    thirdindex := GetThirdIndex(fromindex, atindex);     //подбираем независимую ось
    MoveStack(stacksize - 1, fromindex, thirdindex);     //перемещаем подстек (на 1 меньший) на независимую ось
    towers[fromindex].MoveRing(towers[atindex]);         //перемещаем последнее кольцо на нужную нам ось
    WriteLn(fromindex,'-',atindex);                      //  записываем в консоль наше действие
    MoveStack(stacksize - 1, thirdindex, atindex);       //вовзращаем подстек с независимой на нужную нам ось
  end;
begin
  InitTowers(towers);
  MoveStack(MaxRingCount, 0, 1);
end;
begin
  SolveHanoy;
end.

Algorithmic Complexity

We can easily calculate how many actions we need to move the pyramid.
If we move the stack from one disk, then we need 1 action.
If there is a stack of two, then 1 * 2 (move the stack twice from one disk) + 1 (move the last disk)
If out of three ((1 * 2) + 1) * 2 + 1
Out of five: ((((((1 * 2) + 1) * 2 + 1) * 2 + 1) * 2 + 1)
So each operation increases by 2 times + 1 number of movements. Having opened the brackets for n operations, we get: You

can get rid of the sum, because it is:

ps I got rid of the sum in my head, remembering the sum of the members of the infinitely decreasing geometric progression, but I hope the mathematicians will show how to correctly write down these transformations.
So, after all the transformations, it turned out :

That is, if we want something strange, for example, to record a solution to the Tower of Hanoi for 64 discs, then we will not have enough modern storage media. In fact, we don’t have to write anything anywhere. It’s the same as writing down all numbers from 0 to + infinity, so that you can use them later, because the solution to the Tower of Hanoi is a fractal.

Fractal nature

Yes Yes. The solution to the tower of Hanoi is fractal in nature. Let's get a look. Suppose we have each action written to a string. Then, for a tower of 6 disks, you can write it something like this:

Well, since this is a fractal, we can easily name any operation knowing only its serial number. And even more, we can precisely restore the position of all disks at the time of any operation.

Binary algorithm

So, we know the exact number of operations, and we also know the index of the operation for which we want to restore the state.
Suppose we have a tower of 6 disks (we move as usual, from the 1st to the middle axis), which means we have 2 ^ 6-1 = 63 operations. Suppose we need to restore the state for the 49th operation.
Divide the integer 63 by 2. It turns out 31. This is the index of the operation on which the 6th disk will be moved:

We have the 49th operation index. This means that the 6th disk already lies on the middle axis. In addition, since we are on the right side, the fifth disk lies either on the 3rd axis or on the 2nd. In order for us to work with the tower according to the same algorithm, we subtract 32 from the 49th operation and find the suboperation index. This is 17. To move a stack of 5 disks, 31 operations are needed, with the 5th disk moving to the 16th operation and from the 3rd axis to the 2nd.
So the number 17 lies to the right:

And this means that disk 5 is already moved to the second axis.
By analogy, we restore the position of the remaining disks.

Implementation (binary way)

I added a beautiful rendering of the turrets. Agree, it's boring to look at the console log. Therefore, the implementation has grown, and I will attach the full project (source + binary) at the end of the article. I’ll give you here

recursive function code in Delphi

procedure TfrmView.RestoreDisk(size, actionIndex, actionCount, fromAxe, atAxe: Integer);
var pivot: Integer;
    i: Integer;
    thirdAxe: Integer;
begin
  pivot := actionCount div 2;
  thirdAxe := GetThirdIndex(fromAxe, atAxe);
  if actionIndex = pivot then //попали в центр, значит знаем какой диск сейчас перекладывается
  begin                       //и можем восстановить весь стек дисков меньшего размера. Конец рекурсии
    FTowers[fromAxe].PutRing(size);
    for i := size - 1 downto 1 do
      FTowers[thirdAxe].PutRing(i);
    FAction.FromIndex := fromAxe;
    FAction.AtIndex := atAxe;
  end
  else
    if actionIndex < pivot then
    begin                             //значит выполняется стадия перекладывания подстека на независимую ось
      FTowers[fromAxe].PutRing(size); //и нижний диск еще не переложен
      RestoreDisk(size - 1, actionIndex, actionCount - pivot - 1, fromAxe, thirdAxe);
    end
    else
    begin                             //значит выполняется стадия перекладывания подстека с независимой на нужную ось
      FTowers[atAxe].PutRing(size);   //и нижний диск уже переложен
      RestoreDisk(size - 1, actionIndex - pivot - 1, actionCount - pivot - 1, thirdAxe, atAxe);
    end;
end;
procedure TfrmView.RestoreTowers;
var index: Integer;
begin
  ClearTowers(FTowers);
  index := tbOperation.Position;
  RestoreDisk(MaxRingCount, index, 2 shl (MaxRingCount - 1) - 1, 0, 1);
  Invalidate;
end;

Sierpinski Triangle

I would like to mention in passing an interesting feature. If all possible movements of the rings are collected in a graph, then for each node there will most often be 3 connections. All nodes and connections can be nicely arranged in the shape of a triangle. Sierpinski’s Triangle:

More on this on Wikipedia is here . Which in general is not surprising, because we already know the fractal nature of the solution;)

Total

I tried to show how sometimes it would seem that a seemingly not entirely obvious task can be solved. Moreover, with careful study, you can suddenly discover completely different interesting algorithms for solving the problem, which open up new possibilities. Look for different approaches, experiment, analyze. After all, we are programmers.
Thanks to those who read, and who liked the article. I attach a demo example in which you can use the trackbar and see how the turrets are shifted.

Example binary algorithm (exe + source code, Delphi)

Tags: