10181 - 15-Puzzle Problem

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Backtrack

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

MLE

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

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

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

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

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

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

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

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:

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!

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

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


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

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!

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

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)

^_^

:D

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

10181 15-puzzle: I need a clarification

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?
superfathy

ahsanlatif
New poster
Posts: 10
Joined: Sat Jan 14, 2006 4:52 pm
Location: Lahore

10181 -- 15 Puzzle -- Test data required

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
New poster
Posts: 3
Joined: Sun May 14, 2006 11:01 pm

10181 - 15 Puzzle

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! :)

Post Reply

Return to “Volume 101 (10100-10199)”