10 Replies - 24523 Views - Last Post: 01 February 2009 - 09:45 AM Rate Topic: -----

#1 Purity86  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 36
  • Joined: 28-January 08

Towers Of Hanoi

Post icon  Posted 13 March 2008 - 08:42 PM

I know this is a pretty common problem and i have tried looking everywhere on the internet on explaining the recursion behind the problem and i have found answers, but i am still confused. Does anyone have any tips on understanding this problem? I know the answer to the problem, i am just having a hard time figuring out how the answer actually works (im trying to put in a number an go through the steps in my head)

i can understand the basic steps. i need the bottom disc of stack 1 to be moved to the destination peg. So i need to move every disc but the last one to the temporary peg. Once i move the bottom disk to the destination peg, i have to move the other discs(currently on the temp peg) to the destination peg.

Solve(N, Src, Aux, Dst)
	if N is 0 
	  exit
	else
	  Solve(N-1, Src, Dst, Aux)
	  Move from Src to Dst
	  Solve(N-1, Aux, Src, Dst)


i just dont understand how this code follows the steps i wrote above, im trying to do a test run in my head and i get confused, any tips to grapple with this problem?

Is This A Good Question/Topic? 0
  • +

Replies To: Towers Of Hanoi

#2 bhandari  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 9
  • View blog
  • Posts: 754
  • Joined: 31-January 08

Re: Towers Of Hanoi

Posted 15 March 2008 - 11:10 AM

just try to write something. some classes which represent your buckets and something to represent discs and then we can discuss it here
Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,687
  • Joined: 16-October 07

Re: Towers Of Hanoi

Posted 15 March 2008 - 12:21 PM

I'm not fond of recursion solutions. It's nice that you can boil down the problem like that, but it may not be doing you any favors. I'd try to figure it out without the recursion first.

Consider, you have a class called Tower. Your solve might look something like.

void solve(Tower src, Tower aux, Tower dst) {
...
}



Note, there's no need for N, the Tower class should know how many discs it has, right? Tower could have methods like void moveAllTo(Tower dst) or just boolean moveTo(Tower dst) and int getDiscCount(). Now, write some classes. ;)

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#4 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Towers Of Hanoi

Posted 16 March 2008 - 09:57 AM

To solve the towers of Hanoi for least possible moves, you must first know the algorithm.
For 3 rings:
Tower 1 : Tower 2 : Tower 3
{1, 2, 3}__{ }__{ }
{2, 3 }__{ }__{1 }
{3 }__{2 }__{1 }
{3 }__{1, 2 }__{ }
{ }__{1, 2 }__{3 }
{1 }__{2 }__{3 }
{1 }__{ }__{2, 3 }
{ }__{ }__{1, 2, 3}

These aren't very visual ways to describe the movement, but it's an OK illustration for these purposes. Lets start with the algorithm for 3 rings. Your first goal is to move all of the rings to the third tower. You can't move all three at the same time (one of the constraints of the problem), so you break down your problem into a smaller, more manageable size. Your new goal is to move the top two rings to the buffer tower. You still can't move two rings at once, so you break down the problem even more. Your goal is now to move the smallest ring to the destination tower. This is allowed so you go ahead and do it. Mission 3 is accomplished, so you go back to mission 2: getting the 2 smallest rings onto the buffer ring. The medium sized ring is now movable and the buffer tower is empty, so you move the medium size peg to the middle ring and the small ring on top of it. Mission 2 is now complete. Onto to goal from the very beginning. The third ring can be (and so is) moved to the destination peg. A new goal arises now: get the smaller two rings onto the destination ring. This can't be done so the problem is broken down: move the smallest ring onto the buffer tower (the empty tower is now the buffer tower). This is completed, the medium sized ring is moved onto the destination tower, followed by the smallest ring.

I guess the way I'd describe the recursion is like the building of a house where each step in constructing the house is dependent on the previous step. Like this:

Build the house
_install the roof
__build walls to support the roof
___create a foundation for the walls
etc.

The recursion creates a sort of list of things to complete like so:
move all rings to the destination tower
__move the smallest two rings to the buffer tower
______move the smallest ring to the destination
____move the medium sized ring to the buffer tower
____move the smallest ring to the buffer tower
__move the biggest ring to the destination tower
__move the smallest two rings to the destination tower
______move the smallest ring to the empty tower
____move the medium-sized ring to the destination tower
____move the smallest ring to the destination tower

This post has been edited by potator: 16 March 2008 - 10:02 AM

Was This Post Helpful? 1

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,687
  • Joined: 16-October 07

Re: Towers Of Hanoi

Posted 16 March 2008 - 02:09 PM

View Postpotator, on 16 Mar, 2008 - 12:57 PM, said:

To solve the towers of Hanoi for least possible moves...


Nice description.


View Postbaavgai, on 15 Mar, 2008 - 03:21 PM, said:

I'd try to figure it out without the recursion first.


I take this back. :P Since you already have the basic recursive function, I'd go with it. I tried flattening this out and it gets ugly. Since I noted the use of objects, here's what my solution methods looked like.

class TowerSolver {
	private void solveRecursive(int n, Towers towers, Towers.TowerPos src, Towers.TowerPos dst, Towers.TowerPos storage) {
		if (n == 0) { return; }
		solveRecursive(n - 1, towers, src, storage, dst);
		towers.moveDisk(src, dst);
		solveRecursive(n - 1, towers, storage, dst, src);
	}
	
	public void solve(Towers towers) {
		solveRecursive(towers.getTower(Towers.TowerPos.First).size(), towers, Towers.TowerPos.First, Towers.TowerPos.Third, Towers.TowerPos.Second);
	}
}



Obviously, there's some more code for this. I have a Tower class, that really just extends a stack. A Towers class that manages three Tower objects and also contains an enum. I'm not going to offer them here, but they're not particularly complex. Your turn.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#6 Purity86  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 36
  • Joined: 28-January 08

Re: Towers Of Hanoi

Posted 16 March 2008 - 06:26 PM

Thanks for the Help guys i think i am finally starting to get how recursion works :)
Was This Post Helpful? 0
  • +
  • -

#7 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Towers Of Hanoi

Posted 16 March 2008 - 08:45 PM

Yeah, you should check out the recursion tutorial. It was written by a pretty neat guy.
Was This Post Helpful? 0
  • +
  • -

#8 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Towers Of Hanoi

Posted 27 March 2008 - 09:04 PM

So I mulled this around in my head for a few days and punched it out on the computer in a coupla hours. Here is the final recursive product:
import java.util.Scanner;

public class main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("Input the number of rings");
		int rings = s.nextInt();
		move(rings, 1, 3, 2);
	}
	public static void move(int rings, int source, int destination, int buffer){
		if(rings > 0){
			move(rings - 1, source, buffer, destination);
			System.out.println("Move ring " + rings + " from peg " + source + " to " + destination + ".");
			move(rings - 1, buffer, destination, source);
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,687
  • Joined: 16-October 07

Re: Towers Of Hanoi

Posted 28 March 2008 - 06:34 AM

View Postpotator, on 28 Mar, 2008 - 12:04 AM, said:

So I mulled this around in my head for a few days and punched it out on the computer in a coupla hours. Here is the final recursive product:


Yay for WikiPedia? Look a whole lot like the Javascript version. :P
Was This Post Helpful? 0
  • +
  • -

#10 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Towers Of Hanoi

Posted 14 April 2008 - 05:48 AM

View Postbaavgai, on 28 Mar, 2008 - 06:34 AM, said:

Yay for WikiPedia? Look a whole lot like the Javascript version. :P


no, I actually wrote this. I serious about spending hours on this.
Was This Post Helpful? 0
  • +
  • -

#11 baby_red  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 01-February 09

Re: Towers Of Hanoi

Posted 01 February 2009 - 09:45 AM

tnx :)



View PostPurity86, on 13 Mar, 2008 - 07:42 PM, said:

I know this is a pretty common problem and i have tried looking everywhere on the internet on explaining the recursion behind the problem and i have found answers, but i am still confused. Does anyone have any tips on understanding this problem? I know the answer to the problem, i am just having a hard time figuring out how the answer actually works (im trying to put in a number an go through the steps in my head)

i can understand the basic steps. i need the bottom disc of stack 1 to be moved to the destination peg. So i need to move every disc but the last one to the temporary peg. Once i move the bottom disk to the destination peg, i have to move the other discs(currently on the temp peg) to the destination peg.

Solve(N, Src, Aux, Dst)
	if N is 0 
	  exit
	else
	  Solve(N-1, Src, Dst, Aux)
	  Move from Src to Dst
	  Solve(N-1, Aux, Src, Dst)


i just dont understand how this code follows the steps i wrote above, im trying to do a test run in my head and i get confused, any tips to grapple with this problem?

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1