15 puzzle problem

[lucy1234]

hello, i need to do 15 puzzle algorithm in C as a part of my assignment.Can i please get help for this??
thanku,
lucy.

[Adak]

Sure! Why not?

Here's the thing -- you have to contribute idea's and sometimes, code into this. I'm not going to just post up a program for you, and I hope you don't want to be a "code leech".

So, what does your instructor say to use for an algorithm to solve this? No sense posting on and on about Depth First Search (DFS), if your instructor wants you to use another type of search.

So what, Arshad and Lucy, does your instructor, require for this assignment? What does he suggest you use?

And post up some code, that shows you have some "skin" in the program.

I use DFS for about everything, (and know very little about other types of searches), but others may be along with a broader knowledge, to match your needs.

Welcome to the forum: Arshad, Aliakseis, and Lucy! :)

[jephthah]

Adak,

such a generous welcome you've given arshad and aliakseis to our humble forum.

i know they've been waiting patiently for 3-1/2 years for someone like you to come along, address their needs, and see that they are comfortable.

my only concern is that you've been around here since June of 2008. now tell me what, exactly, has taken you so long to see to these people?? :icon_frown: you really should apologize for making them wait

[Adak]

Well, J, I thought they were people.

You thought they were Zombies.

Now, I guess they were ghosts - gone from this thread, like magic.

And they say the paranormal is a bunch of hokum! ;)

[lucy1234]

hello adak,
thanku so much for replying an directing. well, my instructor wants me to do in best way possible so that the algorithm runs with best time efficiency..so what do u do suggest for the run time of the algorithm to be least and efficient output..bfs or any other method? coming, to the the code..since you told , i would work on it and show my work and guess we can go furthur?? hoping for best ..thanku for the warm welcome too..
lucy

Sure! Why not?

Here's the thing -- you have to contribute idea's and sometimes, code into this. I'm not going to just post up a program for you, and I hope you don't want to be a "code leech".

So, what does your instructor say to use for an algorithm to solve this? No sense posting on and on about Depth First Search (DFS), if your instructor wants you to use another type of search.

So what, Arshad and Lucy, does your instructor, require for this assignment? What does he suggest you use?

And post up some code, that shows you have some "skin" in the program.

I use DFS for about everything, (and know very little about other types of searches), but others may be along with a broader knowledge, to match your needs.

Welcome to the forum: Arshad, Aliakseis, and Lucy! :)

[Freaky_Chris]

Lucy,

What Adak is suggesting is that rather than us telling you the bet way to do things you should research the algorithm, see what searches are a possibility then decide whether you want to be CPU intensive or stack hungry.

You make some descisions about it, try and write up a program, or even write the program with multiple search algorithms and then runs some tests against them to see which out perform others.

As Adak said, we won't do the work for you, but we are more than welcome to help you with problems. But at the moment, you don't have a problem.

Regards,
Chris

[Adak]

Then you should Google this up, and see what is the best algorithm to use for this. To solve puzzles like this, I use DFS and logic, and that's it, with rare (very rare), exceptions.

When it comes to run-time, I use the "one sip" rule:
If the program is done in the time it takes me get one sip of a beverage, then I'm completely happy, and don't give a rat's patootie about it's BIG O complexity.

I have a program that processes about 500,000 records, and I don't care if it takes it 12 seconds to do it. It gets the 2 sip rule. ;)

Anyway, check around. This is an old puzzle, so I'm sure there's some info on the best algorithm to use for it, someplace on the net.

I have looked into how my program moves the tiles, and it certainly is not making the least number of moves, so that's bad. On the good side though, it doesn't spend hardly any time trying to search through a large search tree, looking for how to move next.

I haven't seen that program in awhile, so I'll have to dig it up.

See J! That's where I need the Zombies! Nobody digs up the dead, like Zombies dig up the dead! ;)

Google around and see what a good algorithm is for this, (I wouldn't recommend BFS for this).

ttyl

[0x69]

You can always try random walk algorithm:

While (PUZZLE_NOT_SOLVED) {
tiles = 4 tiles around hole;
tile = RANDOM_TILE_FROM(tiles);
MOVE_TILE(tile);
}

This algorithm is very inefficient and not ensures that solution will be found. And it is just pseudocode. But hey, you are supposed to do homeworks yourself.
p.s. Next hints.
Also you can always try brute-force search. If you want something more efficent you must use effective algorithm such as A*, or some recursive search and/or other graph search algorithm.

[0x69]

Other solution idea - this problem is well-designed for genetic programming. So you can use genetic programming (GP) algorithm. GP output should be hole moving instructions array in the form :
{UP,DOWN,NOP,UP,LEFT,RIGHT,NOP,UP,NOP,...}
Definitions:
UP-move hole up
DOWN-move hole down
LEFT - move hole left
RIGHT-move hole right
NOP - no operation
Actually you can skip NOP command from GP output, but in that case you must program GP algorithm in such way that it accepts variable-length instruction set. But this is harder to do, so I recommend to use fixed length instruction set, just some instructions mark as NOP (do nothing).

After writing GP part you should write interpreter of GP output. Interpeter must accept hole moving instructions array, and do *real* movements of tiles.

Problems - GP algorithm also not ensures that it will get exact solution. So it can be that it is not what you (your professor) want(s).
Google on GP, or start here-
http://en.wikipedia.org/wiki/Genetic_programming

[WaltP]

It's called a breadth-first search.
From your starting position (which is the first entry in the solution array), generate and test every possible move in the next free array locations. Keep track of the parent (array[0]).
Move to the next position (array[1]) and generate all moves from that position. Keep this up. You will need a huge array.
If there is a solution, this will find it. But it's fairly slow and memory intense.

[Imran Javed]

imii..!

hi..
My home task is to go through the codes of all the algorithms thoroughly that are used to solve 8 tile puzzle problem and to understand them. Can anyone help me..
I need algos of dfs, bfs, uniform cost and iterative deepening..

[Adak]

That's a BIG task!

I understand that, now. Do you understand that we are not a repository for that information?

Wikipedia has a lot of info on this, and Google has a ton, so do dig in. Here's a start:
http://en.wikipedia.org/wiki/Depth-first_search_with_iterative_deepening

note that there is ANOTHER entry on Wikipedia, just for regular DFS. I'm sure it has one for BFS, as well.

DFS (plain) is not guaranteed to find the solution with the fewest moves, whereas BFS always will. The beauty of DFS is that it needs a lot less memory to search a large space, and with ID added to it, it finds good shallow search tree answers, (maybe not ideal, but good). Overall DFS with ID is the best of the general searchers, imo.

I have some simple DFS code around. I'll post up something - may not be for a tile game, however - probably Tic-Tac-Toe.

Lots of info on Google for this - DFS is used in chess, checkers, almost exclusively, with ID or IID.

What we need from you, to pursue more details, is:

1) Code you have a question about or a problem, with.
2) That question.

If you can't provide #1 and #2 above, then this forum really can't help you out very much.

I'll post up that code as soon as I'm back from a meal.

[Adak]

The TTT game was a bust - it's not in C.

This is a pretty short and clear discussion of both DFS and BFS:
http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm

[ithelp]

Here is one puzzle for you.

write a program to put too many knots in a thin thread and then write another program to untie all the knots from the thread.

[Imran Javed]

you said that you will post the codes after you return from meal..
So far i haven't seen the code of this task (8 tile puzzle) then how can i say that i have this problem..
Please help me out.when you will post the codes and then if i face any problem then i will be able to refer to some particular problem how can i tell before hand..
I really need help..

[Adak]

The code I was referring to was for Tic-Tac-Toe. There were two problems:

1) One version used OOP style, and is in C++.

2) Tic-Tac-Toe #2 uses alpha-beta version of DFS, and I'm unable to locate the file. (It may have been lost in a HUGE virus attack I had awhile back).

The second link I posted, has both DFS and BFS code in C, although it's not set up for your 8 tile puzzle.

Either you want to start working on your program, or you don't. If you will start working on your own 8 tile puzzle program, I will be able to help you. So far, I don't even know if your "8 tile puzzle" is the SAME 8 tile puzzle (has the same movement rules), as the puzzle that I'm familiar with.

Can the 4 center tiles in your puzzle be rotated clockwise or counter clockwise?

Please don't look at me as someone to give you the code you need - I'm not here for that, and neither is this forum. We're here to help YOU fix YOUR code.

Please list all the moves possible in your 8 tile puzzle.

Do you have a general outline of your program's functions yet? If so, post it, and let's get down to some specifics with your program.

[froward]

hi everyone,

my instructor gave me the 15 tiles problem with following specifications..

"impliment 15-tile problem with A*search & IDS(iterative deepening search,use thee MISPLACED tiles and MANHATTEN DISTANCE heuristics.Find out the solution & no of nodes expanded.. randomly generate the initial state. program in c will be appreciated"..

,any help i can get with this...

thanks

[Adak]

The first thing to know about the 15 tiles puzzle program is that half of the random boards will be completely unsolvable. That was the gimmick when the puzzle was marketed in the 1940's and 50's. It was sold with the puzzle in an initial position that it could NOT be solved.

(That may be why your prof only wants 3 tiles out of place - so it can be solved, but I'm not sure.)

The smart ass even tried to patent that puzzle, that way, but the patent office said he couldn't patent it unless he could show it was solvable (they were onto him).

Lots of info on the net about the 15 tiles puzzle, including applets that let you play, etc. Lots on info on the A* search, some on ID as well. Haven't googled for Manhattan Distance, but it was mentioned in Donald Knuth's tile solving puzzle program. It's on his program's site. No idea what algo he used, however.

More on Google, I'm sure.

A few people have posted here about this puzzle, but they quickly wander off when they see that we don't have "the codez" for them to call their own. I have a 15 tile puzzle program, but it's VERY different, and has no search - quite explicit and fast.

If you need help with ID, the best place to go to would be the Open Chess forum, in the programming sub-forum. They use ID ALL the time (although it's usually with DFS). They're at:
http://www.open-chess.org/

Absolutely some top-class programmer's there.

Allow a LOT of time for this assignment, imo.