10181  15Puzzle Problem
Moderator: Board moderators

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
10181  15Puzzle Problem
can i know the following without doing full search????
If the given initial configuration is not solvable you just need to print the line “This puzzle is not solvable.”
Thanks
If the given initial configuration is not solvable you just need to print the line “This puzzle is not solvable.”
Thanks
Miguel & Marina

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
Read description for problem 652.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing `x' tile, of course).

 New poster
 Posts: 27
 Joined: Thu Feb 14, 2002 2:00 am
Hi, how can I use this information? I've implemented A* with the Manhattan Distance heuristic and it still gives time limit.
Your help is welcome
Regards!
Your help is welcome
Regards!
Ivan Golubev wrote:Read description for problem 652.Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing `x' tile, of course).

 Learning poster
 Posts: 83
 Joined: Wed Feb 27, 2002 2:00 am
 Location: Taiwan
Hi, uzioriluzan:
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me?
Thanks in advance.
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me?
Thanks in advance.

 New poster
 Posts: 27
 Joined: Thu Feb 14, 2002 2:00 am
You could find a description at http://www.delphiforfun.org/Programs/15puzzle_2.htm or at AIMA
Regards!
Regards!
LittleJohn wrote:Hi, uzioriluzan:
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me?
Thanks in advance.
10181 : 15 PUZZLE  HELP PLZ! PLZ!! PLZ!!!
Somebody told me that 15 puzzle is a very good program to learn IDA* Search.I read about IDA* Search in a book but found no way to code it.
Can somebody plz send me a solution of 15 puzzle using IDA* Search in C or C++?
My email address is <laboni_inobal@yahoo.com>
I would be very very grateful if anyone extends his/her helping hand.
Bye
Can somebody plz send me a solution of 15 puzzle using IDA* Search in C or C++?
My email address is <laboni_inobal@yahoo.com>
I would be very very grateful if anyone extends his/her helping hand.
Bye

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
10181 15puzzle
Hi,
I know we have to use IDA* to solve this problem, but is there a way to find out if a starting state can be solved without searching through everything? I remember reading something about some invariant number or such...
Thanks.
I know we have to use IDA* to solve this problem, but is there a way to find out if a starting state can be solved without searching through everything? I remember reading something about some invariant number or such...
Thanks.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
Thanks!
But I still can't pass the 10second limit .
Here's what I'm doing:
First check if the starting configuration is solvable. Then run IDA* using a heap with Manhattan distance heuristic. I hash the states that's I've been to to make sure I don't repeat calculations.
Is there any way to speed the algorithm further? I can run up to 25 moves (WA in 1.687s), so there must be some input that requires at least > 25 moves.
I also noticed a lot of people who solved this problem used very little memory (compared to mine). Is there a different algorithm to solve this problem?
Thanks to anyone who can help me.
But I still can't pass the 10second limit .
Here's what I'm doing:
First check if the starting configuration is solvable. Then run IDA* using a heap with Manhattan distance heuristic. I hash the states that's I've been to to make sure I don't repeat calculations.
Is there any way to speed the algorithm further? I can run up to 25 moves (WA in 1.687s), so there must be some input that requires at least > 25 moves.
I also noticed a lot of people who solved this problem used very little memory (compared to mine). Is there a different algorithm to solve this problem?
Thanks to anyone who can help me.
I'm not sure about the speed either, as my program doesn't run fast.
but, for IDA*, i suppose a stack is enough, not a heap.
i used Manhattan distance heuristic too (quite standard?)
i guess if you adjust/tune your scoring functions, say F() = number of steps + 80* estimated steps, it may terminate faster, although with a less optimal solution, then can pass the 10s limit.
but, for IDA*, i suppose a stack is enough, not a heap.
i used Manhattan distance heuristic too (quite standard?)
i guess if you adjust/tune your scoring functions, say F() = number of steps + 80* estimated steps, it may terminate faster, although with a less optimal solution, then can pass the 10s limit.
Thanks a lot, wyvmak.
I got stuck with the TLE thing for this problem. And now after using F(x)=G(x)+4/3*H(x) I get AC. My solution took 5sec+ though.
I got stuck with the TLE thing for this problem. And now after using F(x)=G(x)+4/3*H(x) I get AC. My solution took 5sec+ though.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
First, I think I meant A* on my algorithm above (the one using heap)
Secondly, just to clarify, A* and IDA* should both run faster than BFS? I wrote 3 programs, using A*, IDA*, and BFS to solve the 8puzzle (p652). The first 2 got TLE, BFS got AC in 6+ sec. Which is why I think I'm coding wrongly .
Does anyone have any good information on the internet on A* and IDA*?
Secondly, just to clarify, A* and IDA* should both run faster than BFS? I wrote 3 programs, using A*, IDA*, and BFS to solve the 8puzzle (p652). The first 2 got TLE, BFS got AC in 6+ sec. Which is why I think I'm coding wrongly .
Does anyone have any good information on the internet on A* and IDA*?

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore