Tower of hanoi on fingers

    imageHaving 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:
    image
    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:
    image
    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:
    image
    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
    image
    can get rid of the sum, because it is:
    image
    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 :
    image

    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:
    image
    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:
    image
    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:
    image
    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:
    image
    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)

    Also popular now: