OJ Board

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

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

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!

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

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 could find a description at http://www.delphiforfun.org/Programs/15puzzle_2.htm or at AIMA
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.

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

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.

yes, there's such a way. if you search the web.
if i remember correctly, i used the following:
let X = determine number of inversions + the row number of the empty square (numbered as row 1 to row 4)
if X is odd, no solution
if X is even, do the search

Thanks!
But I still can't pass the 10-second 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.

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.

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 8-puzzle (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*?

[/b]i think the book of shahani(alg in c++) will work...
although i havn't enough time yet to solve it..
but i read it and think that it works very first...
what about your opinions???
--
anupam

I don't have that book. Could you maybe post a short paragraph from it? Oh does anyone have any reference online...

Thanks anyway