Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can we view the hanoi tower algorithm as the following way?

  1. Mar 4, 2014 #1
    the well known hanoi tower algorithm is as follow:
    Code (Text):

    public static void hanoi(int n,int a,int b,int c)
      (
        if(n>0)
       (
        hanoi(n-1,a,c,b);
        move(a,b);
        hanoi(n-1,c,b,a);
       )
     )
     
    my problem is : can we handle this algorithm in this method?
    we can regard three places as one place which means that three places' case is the basic case, then we can solve the problem of nine places where three places are regarded as one place, and so on, we can solve the case of 27 places then to the case of places. if we realized that when we move three places, it means that we move 7 times which time we move one place, in this way we can solve the problem with remainder.
     
    Last edited by a moderator: Mar 5, 2014
  2. jcsd
  3. Mar 5, 2014 #2
    The algorithm that you're showing will work for any number of discs (as specified by "n").
    When you say "place", I think you're referring to the number of stacks you are allowed to use. Since 3 stacks is sufficient, why do more the 3 stacks? The whole point of the puzzle is to manage with only the minimum.

    Perhaps you are looking to make optimal use of more than three stacks? I can't quite catch what you're trying to do.
     
  4. Mar 5, 2014 #3
    thank you for your help!
    my problem is : can we handle this algorithm in this method?
    we can regard three plates as one plate which means that three plates' case is the basic case, then we can solve the problem of nine plates where three plates are regarded as one plate, and so on, we can solve the case of 27 plates then to the case of plates. if we realized that when we move three plates, it means that we move 7 times which time we move one plate, in this way we can solve the problem with remainder.
    here is the stacks,not the place. i make a mistake, sorry!
    yes i want to search the optimal path of n stacks,such that:
    a0*3^0+a1*3^1+a2*3^2+......+an*3^n
     
  5. Mar 5, 2014 #4
    I see. So you're sticking with three stacks - but you're looking to generate the "move" sequence differently.
    We'll call your new method HanoiTriples. It would take these arguments:

    HanoiTriples(n3Power,a,b,c)
    Where:
    -> n3Power: indicates the number of plates as a power of 3. For example n3Power==0 indicates one plate, n3Power==1 indicates 3 plates.
    -> a: Specifies the "move from" pile.
    -> b: Specifies the "move to" pile.
    -> c: Specifies the other pile.

    I think you could make that work. Of course, if the number of discs was 2, 4, 5, or 6 instead of 1, 3, 9, or 27, then you would have to use Hanoi() instead of HanoiTriple().
     
  6. Mar 5, 2014 #5
    I change my mind, it won't work.
    Here's the algorithm we're talking about:
    Code (Text):

    HanoiTriples(n3Power,a,b,c)
    {
      if(n3Power<1) {
        Move(a,b);
      } else {
        HanoiTriples(n3Power-1,a,b,c);
        HanoiTriples(n3Power-1,a,c,b);
        HanoiTriples(n3Power-1,b,c,a);
        HanoiTriples(n3Power-1,a,b,c);
        HanoiTriples(n3Power-1,c,a,b);
        HanoiTriples(n3Power-1,c,b,a);
        HanoiTriples(n3Power-1,a,b,c);
      }
    }
     
    The problem is with the rule that big plates can't be put onto little plates - and when you're dealing with sets of three, sometime the bottom plate in the group of three will be bigger than the top plate is pile "c".
     
  7. Mar 6, 2014 #6
    thank you for your advice!
    but i don't think it is a problem like hanoi-triple!
    this problem is about the sequence of the plates we move!even though we move one plate each step,but in general,there exists a special regular of the sequence we move.
    if we view three plates as one ,the new sequence of the algorithm will appear in the former case that when we move one plate every step! eventually,if we view nine plates as one,the new sequence will appear in the case that when we move three plates each step!
     
  8. Mar 6, 2014 #7
    I'm pretty sure I understand you correctly - and the code that I posted above does that.
    I don't have the time right now, but later today I will post some JavaScript code which demonstrates what happens when you try to move a stack of 9 plates using your method.

    But meanwhile, consider this: When you are moving 1 plate from stack "A" to stack "B", stack "C" is left alone. But when you move a group of 3 plates from "A" to "B", stack "C" is temporarily used to hold some of the plates. That temporary use is where the problem comes in.
     
  9. Mar 6, 2014 #8
    So copy this into a file, give it an *.html file name, and open it up in your favorite browser.
    It treats everything in a group of nine made up of groups of threes made up of single plates - but in the process it occasionally puts a big plate only a little plate.

    If this isn't the algorithm you mean, feel free to modify the code to suit you purpose and let it run.

    Code (Text):

    <html>
    <head>
    </head>
    <body>
    <table id="HanoiTable">
    <tr><td align="center" width="150">&nbsp;</td><td align="center" width="150">&nbsp;</td><td align="center" width="150">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td align="center">&nbsp;</td><td align="center">&nbsp;</td><td align="center">&nbsp;</td></tr>
    <tr><td bgcolor="black" colspan=3>&nbsp;</td></tr>

    </table>

    <script>

    var HanoiTable = document.getElementById("HanoiTable");
    var HanoiDrawIndex = 0;
    var HanoiDrawCount = 0;
    var HanoiDrawList = Array();

    var HanoiRings=9;

    var Towers=[
      [0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0]
    ];

    function HanoiTriples(n3Power,a,b,c)
    {
      if(n3Power<1) {
        HanoiMove(a,b);
      } else {
        HanoiTriples(n3Power-1,a,b,c);
        HanoiTriples(n3Power-1,a,c,b);
        HanoiTriples(n3Power-1,b,c,a);
        HanoiTriples(n3Power-1,a,b,c);
        HanoiTriples(n3Power-1,c,a,b);
        HanoiTriples(n3Power-1,c,b,a);
        HanoiTriples(n3Power-1,a,b,c);
      }
    }

    /*
    function Hanoi(n,a,b,c)
    {
      if(n>0) {
        Hanoi(n-1,a,c,b);
        HanoiMove(a,b);
        Hanoi(n-1,c,b,a);
      }
    }
    */

    function HanoiMove(a,b)
    {
      nA = a-1;
      nB = b-1;

      var nRing=0;
      //
      // Remove top ring from tower a.
      nRing = 0;
      nASize = Towers[nA][0];
      if(nASize>0) {
        nRing = Towers[nA][nASize];
        Towers[nA][nASize] = 0;
        Towers[nA][0] = nASize-1;
        HanoiSetDraw(a,nASize,0,false);
      }
      //
      // Place it onto tower b.
      if(nRing>0) {
        nBSize = Towers[nB][0]+1;
        Towers[nB][0] = nBSize;
        Towers[nB][nBSize] = nRing;
        HanoiSetDraw(b,nBSize,nRing,true);
      }
    }

    function HanoiSetDraw(tower,level,ringsize,delay)
    {
      var Move=Array();
      Move.tower=tower;
      Move.level=level;
      Move.ringsize=ringsize;
      Move.delay=delay;
      HanoiDrawList[HanoiDrawCount] = Move;
      HanoiDrawCount++;
    }

    function HanoiDraw()
    {
      while(HanoiDrawIndex<HanoiDrawCount) {
        Move = HanoiDrawList[HanoiDrawIndex];
        HanoiDrawIndex++;
        HanoiCell = HanoiTable.rows[9-Move.level].cells[Move.tower-1];
        HanoiCell.innerHTML = "&nbsp;"+(Array(Move.ringsize+1).join("="));
        if(Move.delay) break;
      }
    }


    Towers[0][0]=HanoiRings;
    for(n=1;n<=HanoiRings;n++) {
      Towers[0][n] = HanoiRings-n+1;
      HanoiSetDraw(1,n,Towers[0][n],false);
    }


    setInterval(HanoiDraw,250);

    HanoiTriples(2,1,2,3);

    </script>

    </body>
    </html>
     
     
  10. May 11, 2014 #9

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    There is a unique minimal-move solution to the problem and the standard recursive algorithm does that. In effect, it treats moving n-1 disks as a single set (a recursive call for moving n-1 disks). Your suggestion of treating 3 disks as a special case seems like a step backward that introduces unnecessary complications. The only way that it could get a different answer is if it makes unnecessary moves that it undoes later.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Can we view the hanoi tower algorithm as the following way?
  1. World view (Replies: 1)

Loading...