Page 2 of 3


Posted: Wed Jun 25, 2003 1:31 am
by jpfarias
Is there a way to solve this problem with backtrack?

What I need to do to avoid repeating states?




Posted: Thu Jun 26, 2003 2:04 pm
by jpfarias

Man, I've tried to solve this one but I'm in trouble...

I've used BFS and hash to store configurations I've seen and I'm getting MLE and some SIGSEGV :(

Can anyone tell me some tips on A* or IDA*, by pointing some sites or even describing the algorithm?



Posted: Fri Jun 27, 2003 7:42 pm
by Adil
hi. when i visit a new state, i just checked that a state cannot be an ancestor of itself. i used a stack of depth 52 to keep track of this.

hope this helps.

Posted: Sat Jun 28, 2003 12:01 am
by jpfarias

I didn't understand very well what you mean. Can you show an example or try to explain it better?

I really don't know how to store only 52 configurations!!! My queue goes as big as 60000 when it reachs the 45-50 steps.



Posted: Sat Jun 28, 2003 6:54 pm
by Adil
i'll try to explain. consider the following tree:

Code: Select all

    B(1)              C(1)
  ---|---          ----|----
  .     .              D
  .     .              |
  .     .              .
                  C(2)    B(2)
in this tree, A, B, C, D, E are different states. C(1) is the first occurance of state C. C(2), B(1) and B(2) have similar meanings. A is the initial state.

now i expand from state A to B(1) and expand B(1), and dont get a solution there. so i again start from A and go to C(1). expanding from C(1), if i reach the same state again, here C(2), then i don't expand from there. but if i reach B(2), then although it was expanded earlier, i expand it again since B(2) is not on the path from A to E. so i only have to store which states have been visited on the current path from the root to the current state.

i hope it is clear enough now.

Posted: Sat Jun 28, 2003 10:16 pm
by jpfarias
I think I've get it. I'll try to implement it when I get to linux (I'm using windows right now...)

Thanks a lot for your help!


Posted: Mon Jun 30, 2003 2:20 pm
by jpfarias
What search do you use?

I'm now using DFS with max depth 46 and it can't solve in time...


Posted: Mon Jun 30, 2003 6:18 pm
by Adil
i used IDA* with adjustments as mentioned by wyvmak.

Posted: Mon Jun 30, 2003 6:51 pm
by jpfarias
Hi, again!

Can you point me with some site with good info on IDA* or A* similar algorithms?



Posted: Tue Oct 05, 2004 5:34 pm
by dumb dan

Posted: Tue Mar 22, 2005 12:45 pm
by hank

My code can't pass the time limit.
I use IDA* algorithm.

Can somebody help me?
or you can give me some tips and hints.

Thanks in advance!

Posted: Wed Mar 23, 2005 6:04 pm
by hank

I got accepted now.

1.705 seconds and memory cost 452

IDA* and F(x)=G(x)+4/3*H(x)



10181 15-puzzle: I need a clarification

Posted: Thu Sep 22, 2005 6:30 am
by superfathy
What should I do if the initial configuration is in the correct order?
I mean what is the output of the program if the initial configuration is:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

My program (which has got WA) prints an empty line. So, can anybody help?

10181 -- 15 Puzzle -- Test data required

Posted: Fri Feb 17, 2006 3:46 am
by ahsanlatif
I got WA for this problem but it works for all of my test data. I need some test data for this problem.

Is there any thing critical, tricky in this problem.

Thank You,

10181 - 15 Puzzle

Posted: Tue Jul 04, 2006 7:57 pm
by masta_lu

I am trying to solve Problem 10181 because I wanted to learn more about A*. But I always get TLE. I can solve the example problem from the problem definition, but when I try to solve a more complicate problem my Programm runs forever. Just a short informal description of what I do (the code is really messy).

- Create a "Peudo Hash Table" for the already visited states C
- Create a prority queue Q
- Get first state from Q
(which is cheapest of all states in Q according to f(n) = g(n) + h(n))
and remove it from Q
- Check if it is A goal state ( h(n) == 0 )
- If not, create all successors and insert state in C
- for each succesor
- check if it is in C
- if not, push it in Q
- continue from start

o Q is initialiyed with the start state
o state is a class I defined which stores the current layout of the puzzle as
an [4][4] array, the path as a string, the current step cost and has
memberfunctionss for comparing to other states (so I can use the STL
prority queue)
o The psuedo hash table is also a class I defined my own. It has a
list<state>[16][16][16][16] "hashing" the states by 4 elements of the
puzzle (upper left, right, lower left, right). The "insert" function only
inserts a state if it is not alread in the array.
o h(n) is manhatten distance sum of the tiles of the puzzle

I think I did a pretty straight forward implementation of A* on a graph with a consistent heuristic....
I read that you cannot solve this problem using A* but you have to use IDA*... I cannot find a "good" description of IDA* anywhere :( or, one that I understand....
I think my hash class is, well, "not so good" but I have no idea how I could efficently store already visited states... but I think I have to store those, or there will be "loops"....

Can someone please help? Is there something wrong in the "code" I posted? Or do you know a webpage with a good/detailed/easy-to-read descriptions of IDA*

I'm working on this problems for 2 days now and I'm kinda stuck....

Thanks in advance for any help! :)