Computer Science Canada

Towers of Hanoi Question
Author:  whoareyou [ Fri Mar 22, 2013 4:12 pm ]
Post subject:  Towers of Hanoi Question
Hello,

I've been looking through the solution to the Towers of Hanoi problem for a long time, and even tracing the function using the call stack output on http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html.

I understand the first call, MoveTower(5, A, B, C), but in the second call and the calls thereafter, the destination and temporary peg switch. Why is this?
Author:  jbking [ Fri Mar 22, 2013 5:16 pm ]
Post subject:  Re: Towers of Hanoi Question
Because to make that move requires one to make other moves first. Remember the rules of which disks can be moved and when.
Author:  whoareyou [ Fri Mar 22, 2013 5:27 pm ]
Post subject:  RE:Towers of Hanoi Question
I still don't get it Sad. Can you explain in more detail?
Author:  Panphobia [ Sat Mar 23, 2013 1:13 pm ]
Post subject:  Re: Towers of Hanoi Question
move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc n
Author:  whoareyou [ Sat Mar 23, 2013 6:12 pm ]
Post subject:  RE:Towers of Hanoi Question
I still can't see why the destination and temporary pegs keep switching.
Author:  Panphobia [ Sat Mar 23, 2013 6:54 pm ]
Post subject:  Re: Towers of Hanoi Question
Java:
public static void Towers(int n, int from, int to, int temp){
        if(n==0)return;
        Towers(n-1,from,temp,to);
        System.out.println("Move top disc from "+from+" to "+to);
        Towers(n-1,temp,to,from);
    }

if you passed Towers(3,1,2,3);
it would look like this through the output
code:
Move top disc from 1 to 2
Move top disc from 1 to 3
Move top disc from 2 to 3
Move top disc from 1 to 2
Move top disc from 3 to 1
Move top disc from 3 to 2
Move top disc from 1 to 2

and then like this graphically, with the actual pegs
code:
(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (A -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)
Author:  whoareyou [ Sat Mar 23, 2013 6:58 pm ]
Post subject:  RE:Towers of Hanoi Question
I realize that the algorithm is actually doing that and I can follow what the algorithm is doing. But my question is WHY is it necessary to switch the destination and temporary pegs. I know that it does it in the algorithm, but why does it make sense to do that?
Author:  Panphobia [ Sat Mar 23, 2013 7:08 pm ]
Post subject:  RE:Towers of Hanoi Question
Basically, you do not want the exact same peg to keep on having a disc being added to it, that would defeat the purpose of the towers of hanoi, just search on how the Lucas' Tower/Towers of Hanoi is played, you know there are always 2^n-1 amount of moves for the least amount of moves, and to play optimally, what needs to be done? where do the discs need to be put? see if I instead used the function
code:
public static void Towers(int n, int from, int to, int temp){
        if(n==0)return;
        Towers(n-1,from,to,temp);
        System.out.println("Move top disc from "+from+" to "+to);
        w++;
        Towers(n-1,from,to,temp);
    }

with the same values being passed I would get this
code:
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy