×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

The 8-Puzzle Problem

FortKnox (169099) writes | more than 9 years ago

User Journal 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'.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.

12 comments

phone # ? (1)

heliocentric (74613) | more than 9 years ago | (#10784085)

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

Picard says: (0)

Anonymous Coward | more than 9 years ago | (#10784133)

There are four lights!

Welcome to my personal hell (1)

bofkentucky (555107) | more than 9 years ago | (#10784144)

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 (1)

Eye of the Frog (152749) | more than 9 years ago | (#10784211)

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 might just write something up quick for fun. I miss school for those little brain teaser problems. It's fun not to do "real world" problems sometimes.

Solutions (1)

Eye of the Frog (152749) | more than 9 years ago | (#10785603)

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 in either version, it'll print out each step between the solution and the starting point.

Don't expect any high quality programming here.....this was just for fun. :) There's probably better faster ways to do it.

BFS (1)

ryanr (30917) | more than 9 years ago | (#10784789)

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 (1)

jawtheshark (198669) | more than 9 years ago | (#10785203)

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". ;-) (this of course, assuming you're the root of the tree, but who isn't root these days?)

Re:BFS (1)

FortKnox (169099) | more than 9 years ago | (#10787467)

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 ... (1)

Triumph The Insult C (586706) | more than 9 years ago | (#10785216)

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 (1)

Tet (2721) | more than 9 years ago | (#10785702)

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 you need to know what they are and how they work so you can make an informed decision. I'd say that choosing the wrong data structure is probably the second most common coding error in real world programming (after memory/pointer problems). It can make the difference between a great bit of a code and an awful one.

I wish I'd been taught about skip lists at University. But the skip list paper had only just been published when I was doing my algorithms and data structures courses (as in a couple of months earlier), and I didn't find out about it until much later...

There are a couple of saws in the IT world that I've found to hold a lot of truth:

  • You can't be a good sysadmin without a decent knowledge of regular expressions.
  • You can't be a good coder without a decent knowledge of data structures.

use a queue? (-1)

shitface (121619) | more than 9 years ago | (#10786560)

I think/believe all you need is to just throw the children nodes of the current node into a queue and use the queue to dictate the next node examined.
Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...