11163 - Jaguar King

[paulmcvn]

Could anyone give me an idea for this problem?

[Per]

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]

Could you please post links with more info about IDA*? it is kind of a hard one to find in google.

[Observer]

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.

[Vexorian]

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]

I think something like the famous "Manhattan distance" (as in solving 15-puzzle) should do.

[Observer]

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.

[rio]

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]

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?

[rio]

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]

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.

[sclo]

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]

You could think this problem as a cylindrical 4xN puzzle.
One roll has four pieces.

Numbering the position from 0 :
Position 0 adjacents to 1(same roll), 3(same roll) and 4(adjacent roll).
Position 5 adjacents to 4(same roll), 6(same roll), 1(adjacent roll) and 9(adjacent roll).

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]

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]

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

Thanx in advance.

Edit: ACCEPTED.