## 10181 - 15-Puzzle Problem

Moderator: Board moderators

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### Backtrack

Is there a way to solve this problem with backtrack?

What I need to do to avoid repeating states?

Thanks!

JP.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### 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!

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Hi,

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.

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:

Code: Select all

``````             A
---------|---------
B(1)              C(1)
---|---          ----|----
.     .              D
.     .              |
.     .              .
.
.
E
----|----
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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
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!

JP!

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
What search do you use?

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

JP!

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
i used IDA* with adjustments as mentioned by wyvmak.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Hi, again!

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

Thanks,

JP!

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Hi,

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.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Hi,

I got accepted now.

1.705 seconds and memory cost 452

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

^_^

superfathy
New poster
Posts: 2
Joined: Sun Jan 30, 2005 2:23 am

### 10181 15-puzzle: 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?
superfathy

ahsanlatif
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

masta_lu
New poster
Posts: 3
Joined: Sun May 14, 2006 11:01 pm

### 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/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!