10181 - 15-Puzzle Problem

jpfarias · Post by **jpfarias** » Wed Jun 25, 2003 1:31 am

Is there a way to solve this problem with backtrack?

What I need to do to avoid repeating states?

Thanks!

JP.

jpfarias · Post by **jpfarias** » Thu Jun 26, 2003 2:04 pm

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!

Adil · Post by **Adil** » Fri Jun 27, 2003 7:42 pm

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 · Post by **jpfarias** » Sat Jun 28, 2003 12:01 am

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!

Adil · Post by **Adil** » Sat Jun 28, 2003 6:54 pm

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 · Post by **jpfarias** » Sat Jun 28, 2003 10:16 pm

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 · Post by **jpfarias** » Mon Jun 30, 2003 2:20 pm

What search do you use?

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

JP!

Adil · Post by **Adil** » Mon Jun 30, 2003 6:18 pm

i used IDA* with adjustments as mentioned by wyvmak.

jpfarias · Post by **jpfarias** » Mon Jun 30, 2003 6:51 pm

Hi, again!

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

Thanks,

JP!

dumb dan · Post by **dumb dan** » Tue Oct 05, 2004 5:34 pm

http://en.wikipedia.org/wiki/A-star_search_algorithm

hank · Post by **hank** » Tue Mar 22, 2005 12:45 pm

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.

Thanks in advance!

hank · Post by **hank** » Wed Mar 23, 2005 6:04 pm

Hi,

I got accepted now.

1.705 seconds and memory cost 452

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

^_^

superfathy · Post by **superfathy** » Thu Sep 22, 2005 6:30 am

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?

ahsanlatif · Post by **ahsanlatif** » Fri Feb 17, 2006 3:46 am

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 · Post by **masta_lu** » Tue Jul 04, 2006 7:57 pm

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!

OJ Board

10181 - 15-Puzzle Problem

Backtrack

MLE

10181 15-puzzle: I need a clarification

10181 -- 15 Puzzle -- Test data required

10181 - 15 Puzzle