FortKnox's Journal: The 8-Puzzle Problem

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.

phone # ?

[heliocentric]

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

Welcome to my personal hell

[bofkentucky]

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.

this might help

[Eye of the Frog]

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

Solutions

[Eye of the Frog]

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

What is the "8-puzzle" problem?

[johndiii]

n/t

BFS

[ryanr]

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?

Re:BFS

[jawtheshark]

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".

Re:BFS

[FortKnox]

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 ;-)

reminds me ...

[Triumph The Insult C]

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 ...

Data structures

[Tet]

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