## 11163 - Jaguar King

Moderator: Board moderators

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

### 11163 - Jaguar King

Could anyone give me an idea for this problem?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### Re: 11163 Jaguar King

paulmcvn wrote:Could anyone give me an idea for this problem?
I used IDA* search. The judge I/O is very kind, there are many cases where my solution is hopelessly slow.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I haven't attempted this problem, but the idea is pretty much the same as an old problem called "Constrained Exchange Sort" (can't remember the number). Or maybe 15-puzzle. The key is to find a good heuristic function h(x). I think it shouldn't be hard.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
first problem I get into where I have to use heuristics, awesome, anyways thanks. Now that I think about it a good heuristic is possible because of the pretty odd jump rules.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I think something like the famous "Manhattan distance" (as in solving 15-puzzle) should do.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Oh... my IDA* gets TLE... Manhattan distance isn't very good in some cases......

What good heuristics do you guys have? How long does your program take to solve the following cases?

Code: Select all

``````12
1 11 12 10 9 8 7 6 5 4 3 2
16
9 11 12 10 5 8 7 6 13 4 3 2 1 14 15 16
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27 29 30 31 32 33 34 35 36 38 37 40 39
0
``````
Thanks.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I used IDA* with Manhattan distance.

For your test case 1 ~ 3, my code takes 0.125 sec, and doesn't come back with the 4th case.
The 4th test case might be invalid(not reachable from init sequence), or just a hard case.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thank you.

I think the 4-th case is valid, since the following case is solvable:

Code: Select all

``````8
1 2 3 4 6 5 8 7``````
I think your program must be very well optimized. My third case (with N = 28) should give Manhattan distance = 4, which is waaaay less than the minimum number of moves... Or do you also consider the moves the "king" shall take to reach the "wrongly placed ones" in your heuristic function?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I think your program must be very well optimized. My third case (with N = 28 ) should give Manhattan distance = 4, which is waaaay less than the minimum number of moves... Or do you also consider the moves the "king" shall take to reach the "wrongly placed ones" in your heuristic function?
I'm not considering the move of king (becuase it becomes very complex). I also got Manhattan distance = 4 for the 3rd case, so I think our heuristic function is same.

So I think the problem is in your IDA* implementation.
Heres the optimization I did. If you haven't tried yet, I think its worth trying.

1.If the kings position moved from a to b, don't move back (b to a) at the next step.
2.Don't calculate the whole heuristic value every time. Just calculate the difference.

ADD : If you feel my post SPOILic, tell me. I'll edit it.
----
Sory for my poor English..

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Yes, there were some flaws in my old code, so it didn't work as I expected... I've got Accepted. Thanks~

Right now my code doesn't have the "optimizations" you mentioned implemented well, so my runtime is slow (> 3 sec). Will try to improve that.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I think I don't understand how to use manhattan distance heristic properly as I'm getting non optimal solutions.

consider

Code: Select all

``````4
4 2 3 1
``````
If I use the definition of manhattan distance, then it is |4-1|+|2-2|+|3-3|+|1-4|, which is 6, and it is much over the optimal solution.

I think I need to modify it so that I don't count the king, and that I allow for steps of size at most 4 in one move, but it makes the heristic too complicated.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
You could think this problem as a cylindrical 4xN puzzle.
One roll has four pieces.

Numbering the position from 0 :

The Manhattan distance of position i, j could be defined as below.

Code: Select all

``````int Md(int i, int j) {
int a = abs(i/4 - j/4);   // need moves to the same roll
int b = abs(i%4 - j%4);
if (b == 3) b = 1;  // in the same roll, distance 3 == 1,
return a + b;
}
``````
I didn't calculated the kings Manhattan distance as I didn't calculate the Manhattan distance of the hole in 15-puzzle.
----
It is too hard to explain this problem with my poor English. I hope you understand my English.
ADD: Am I SPOILing ? If you feel so, tell me. I'll edit my post.

Rings
New poster
Posts: 3
Joined: Sat Aug 09, 2008 1:01 pm

### Re:

Observer wrote:Oh... my IDA* gets TLE... Manhattan distance isn't very good in some cases......

What good heuristics do you guys have? How long does your program take to solve the following cases?

Code: Select all

``````12
1 11 12 10 9 8 7 6 5 4 3 2
16
9 11 12 10 5 8 7 6 13 4 3 2 1 14 15 16
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27 29 30 31 32 33 34 35 36 38 37 40 39
0
``````
Thanks.
I got WA...
Who can give me these tests' answers,I need help...

EDIT: I find a mistake,AC now.

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

### Re: 11163 - Jaguar King

I am getting WA.
Please someone give the answers of these test case , stated above.