Catch up on stories from the past week (and beyond) at the Slashdot story archive

 



Forgot your password?
typodupeerror
User Journal

Journal FortKnox's Journal: The 8-Puzzle Problem 12 12

My wife's friend (church guy) is in need of help programming the '8-puzzle problem' for a college class. He is going to stop over tomorrow night (Thursday). I looked at the problem, could come up with the solution, but the teacher wants him using a 'breadth first tree search'.

I hate being limited in what I can do and have no idea where to start. I guess I'll have to remind myself what the breadth first tree search is.... man, I dunno why they teach these kids these things... not like we use'm in the real world. If there were no stipulations, I'd be able to knock this sucker out.... any ideas? I just need some overview of what the algorithm should do... I can code it out if I knew what the algorithm should be like... I may even be able to figure the algorithm out if I knew how the tree and problem were related... any help is appreciated.
This discussion has been archived. No new comments can be posted.

The 8-Puzzle Problem

Comments Filter:
  • i can't type, but i can call ya

    if you want hit my gmail accout

    basicailly breath fisst is to search at a level in the logic tree ENTIRELY before going on to the next rung
  • JAPH enrolls in Intro to C/C++, gets frustrated with the limited text processing tools to work with, get's a B but submits parallel solutions in Perl that run faster with smaller code, just to be that smartass.
  • Take a look at this page: http://www.cogs.susx.ac.uk/users/christ/crs/sai/le c06.html [susx.ac.uk]

    It gives an idea of how to setup the tree. Look at the "Successors in the 1-dimensional representation" section specifically. Doing the breadth first search should be easy. Just search 1 level down, then 2 levels, then 3 levels, etc. I would suggest creating the tree as you search. Creating the whole tree and then searching would be a waste. Let me know if you need clarification, I see I'm pretty vague on some things. I
    • I think my curiousity won over my tiredness. I have an example with both OO concepts and straight recursion/non-OO. The reason I did the non-OO one is that I was running out of memory around 12 levels deep. I'm currently running a pass that's on level 21 and still running. I'll let that go through the night and see what comes up. Here's the two versions:

      http://plasticfrog.info/code/PuzzleSolve.java
      h ttp://plasticfrog.info/code/PuzzleSolveB.java

      PuzzleSolveB is the non-OO version. When the solution is found
  • by ryanr (30917) *
    Breadth First Search:

    You're given a tree (usually non-looping) and a starting node. Some nodes are considered siblings or peers (on the same horizontal plane, if you wish to think of it that way) and some are descendants or children, and are considered below. You use a recursive algorithm to walk the tree. In a BFS, you do siblings before children. In a Depth First Search (DFS), you do children first.

    Ring any bells yet?
    • Right on... That is exactly it :-)

      Don't complain FortKnox: I have to re-learn that crap for an upcoming exam. It is plainly and utterly boring because you've all seen it before and you know it doens't matter because you know where to find it if you need it. (Being a Java programmer doesn't help: all basic data structures are there and you don't have to bother anymore)

      Oh, and as for easy remembering "Breadth first search" think of it this way: "if you have bad breath, the closest people faint first".

    • Perfect! Exactly what I needed to know. So taking this advice and what shithead said (the -1 score in this JE), my solutions that I wrote (just to make sure I did it right) is actually using what was asked.

      Stupid engineering training... teaching me to use stuff that's correct and not realizing it ;-)
  • of the days in os class reading about the history of computers and what not. like i hadn't read the story 40 times before in the other classes ...
  • I dunno why they teach these kids these things... not like we use'm in the real world.

    They teach them so that the pupil can learn the pros and cons of each data structure and traversal method, precisely so that they can choose which is the right one for a given situation in the real world. We very definitely do use them in the real world. True, the actual code for manipulating them is all in libraries these days, and it's rare to be writing a linked list or AVL tree implementation in the real world. But y

"Summit meetings tend to be like panda matings. The expectations are always high, and the results usually disappointing." -- Robert Orben

Working...