10181  15Puzzle Problem
Moderator: Board moderators
Backtrack
Is there a way to solve this problem with backtrack?
What I need to do to avoid repeating states?
Thanks!
JP.
What I need to do to avoid repeating states?
Thanks!
JP.
MLE
Hi!
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?
Thanks,
JP!
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?
Thanks,
JP!

 Learning poster
 Posts: 57
 Joined: Sun Sep 29, 2002 12:00 pm
 Location: in front of the monitor :)
 Contact:
i'll try to explain. consider the following tree:
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.
Code: Select all
A

B(1) C(1)
 
. . D
. . 
. . .
.
.
E

C(2) B(2)

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

 New poster
 Posts: 2
 Joined: Sun Jan 30, 2005 2:23 am
10181 15puzzle: I need a clarification
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?
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?
superfathy

 New poster
 Posts: 10
 Joined: Sat Jan 14, 2006 4:52 pm
 Location: Lahore
10181  15 Puzzle  Test data required
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,
Ahsan
Is there any thing critical, tricky in this problem.
Thank You,
Ahsan
10181  15 Puzzle
Hello
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/easytoread descriptions of IDA*
I'm working on this problems for 2 days now and I'm kinda stuck....
Thanks in advance for any help!
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/easytoread descriptions of IDA*
I'm working on this problems for 2 days now and I'm kinda stuck....
Thanks in advance for any help!