12,758,782 members (36,332 online)
Rate this:
See more:
Write a program to solve the Hanoi towers problem using uninformed search techniques: BFS, DFS and IDS.
I wrote the code of the three dfs, ids,bfs, and Hanoi Towers but I don't know how to mix one of the techniques with Hanoi towers problem .

This my first question on this nice site.
Here is my code in bfs:
```public void bfs()
{
//BFS uses Queue
printNode(this.rootNode);
rootNode.visited=true;
while(!q.isEmpty())
{
Node n=(Node)q.remove();
Node child=null;
while((child=getUnvisitedChildNode(n))!=null)
{
child.visited=true;
printNode(child);
}
}
//Clear visited property of nodes
clearNodes();
}```

And this for Hanoi:

```public class Hanoi {
public static void hanoi(int n, String from, String temp,
String to) {
if (n == 0) return;
hanoi(n-1, from, to, temp);
System.out.println("Move disc " + n +
" from " + from + " to " + to);
hanoi(n-1, temp, from, to);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
hanoi(N, "A", "B", "C");
}
}```

I will do this first the Hanoi is the tree with all possible solutions
and make the bfs trace the Hanoi nodes.

Thank you :)
Posted 16-Apr-10 5:46am
Updated 16-Apr-10 11:15am
v5

Rate this:

## Solution 4

You're going to have some serious trouble in school my friend.

You're not understanding the problem as it was given to you. By your first sentence, you're supposed to find a solution the Tower of Hanoi problem using BFS, DFS, and IDS algorithms.

You apparently took that to mean, implement the recursive solution as shown on wikipedia's entry for Tower of Hanoi and then you're somehow trying to figure out how to include the different algorithms into it.

As far as I can tell, here is what you're supposed to do.

Assume you have no knowledge of the way to solve the problem. You only know that you have 3 pegs, you can only move one disc at a time, and you cannot move a larger disc onto a smaller disc.

Now, implement the Breadth-First Search algorithm to find the solution.

So, how would you do that? The question is trying to get you to implement each algorithm to find the solution.

For BFS, how does the algorithm work? Well, you start with the root node. Then, you build the child nodes of that root node and link them as neighbors. So, to start, you have two moves that you can make...move the top disc to the middle, or to the opposite end. So, look at the first child. Does that solve it? If not, look at the next child. Does that solve it?

If none of the children solve it, look at the first child and add in it's children. Look at them. Wikipedia has a good animation to show the steps to take (Animated_BFS.gif[^])

So, implement this algorithm to solve the problem. The BFS doesn't know anything about the tree until it builds the children. You don't build the whole tree and then search through it. That's why it's called an uninformed search.

I'll do it for you...if you pay me. \$60 per hour of my time sounds reasonable.

Just to add to this, a Breadth-First Search is crazy memory intensive if you are trying to re-create the path. For example, if there are 6 disks on the tree, the solution takes (2^6)-1 moves to solve or 63 moves to solve. That means that with a BFS search, there would be 63 different levels...not including the root.

It's a ridiculous number of nodes at the 63rd level and if you want to be able to follow the path, you have to keep track of everything. Just as an example for any number of disks.

At the beginning, there are 2 moves.
After the 1st move, there are 6 moves.
After the 2nd move, there are 18 moves.

It works out to 0.9643e^(1.0995((2^x)-1) where x is the number of disks. With 6 disks, that's a total of 1.14*10^30 moves to keep track of. I ran out of memory trying to solve a problem with only 4 disks.

So, good luck with that.
v2
Rate this:

## Solution 1

This is not a homework service; no-one here will do your work for you.

Do not ask "Please provide the code to ..." as it shows you are not trying to help yourself. All you will get is ignored, abused, or told to try rentacoder (where they make you pay for software).

If you have a specific problem, ask about it. People will try to help.
Rate this:

## Solution 3

He's right...we don't do homework...we help with problems when you get stuck...specific coding problems like..."I'm getting an error on this line." or "I've tried to implement it, but I'm not getting the result I expected."

Are you sure that you're supposed to combine the searches? It seems to me like your professor wants you to implement three solutions to the problem...one using each method...not one single answer combining all three techniques. That wouldn't make sense.

If the class is going over search algorithms, then it's useful to see how to solve a single problem using different algorithms which seems to be what your professor wants.

If you don't think so, check with your professor. Because I seriously doubt you're supposed to combine them.

Top Experts
Last 24hrsThis month
 Graeme_Grant 191 Bryian Tan 190 OriginalGriff 170 ppolymorphe 159 Richard Deeming 150
 OriginalGriff 4,327 Peter Leow 3,249 ppolymorphe 2,683 Karthik Bangalore 2,574 Graeme_Grant 2,377