Write a program to solve the Hanoi towers problem using uninformed search techniques: BFS, DFS and IDS.

Question

0.00/5 (No votes)

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 
    Queue q=new LinkedList();
    q.add(this.rootNode);
    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);
            q.add(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 4:46am

meshosho

Updated 16-Apr-10 10:15am

Deeksha Shenoy

v5

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2010-04-16T05:04:00

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.

Posted 16-Apr-10 5:04am

OriginalGriff

Comments

Qasid Ali 8-May-21 16:27pm

Solve tower of hanoi problem for 3 discs with code and example

OriginalGriff 9-May-21 2:04am

OK, done it.
Took three minutes and fourteen seconds, including testing.

Now what?

William Winner · Answer 2 · 2010-04-16T10:54:00

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.

[Added]
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.

William Winner · Answer 3 · 2010-04-16T06:08:00

OriginalGriff didn't make people ignore your question, your question did.

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.

Write a program to solve the Hanoi towers problem using uninformed search techniques: BFS, DFS and IDS.

3 solutions

Solution 1

Solution 4

Solution 3

Add your solution here

Preview 0