ACM PKU Eight Puzzle
Moderator: Board moderators
ACM PKU Eight Puzzle
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
For anyone that has got accepted in this problem, please help me! I got WAs so many... what else I might miss? I just used A* with priority_queue. It works for all TC I created myself....
For anyone that has got accepted in this problem, please help me! I got WAs so many... what else I might miss? I just used A* with priority_queue. It works for all TC I created myself....
Re: ACM PKU Eight Puzzle
Just do a simple breadth-first search.
You can find some I/O from the original ACM contest here:
http://www.acm.inf.ethz.ch/ProblemSetAr ... hCen/1998/
You can find some I/O from the original ACM contest here:
http://www.acm.inf.ethz.ch/ProblemSetAr ... hCen/1998/
Re: ACM PKU Eight Puzzle
DId you mean that I should do BFS from final state to ALL reachable states?
Oh one more, how did you mark a state as visited?
Oh one more, how did you mark a state as visited?
Re: ACM PKU Eight Puzzle
There's only about 9!/2 = 181440 reachable states. 1 second is more than enough time to check them all.fushar wrote:DId you mean that I should do BFS from final state to ALL reachable states?
Convert permutation into an integer in any way, and store them in std::set<int>.Oh one more, how did you mark a state as visited?
(Or a boolean array, if you're not lazy, and the range of integers is small enough)
Re: ACM PKU Eight Puzzle
Oh, I see. So if the queried state is not visited, then I should output "unsolvable". Right?
Anyway thanks for your help. I'll try to recode my solution.![:wink:](./images/smilies/icon_wink.gif)
Anyway thanks for your help. I'll try to recode my solution.
![:wink:](./images/smilies/icon_wink.gif)
Re: ACM PKU Eight Puzzle
Uh, I just used plain BFS without heuristic, and got TLE....
Re: ACM PKU Eight Puzzle
My old BFS solution for UVa's problem 652 gets accepted at pku, running 0.438 seconds.
It doesn't use STL, though as I was coding in C - it converts each permutation into its sequential number (from 0 to 9!-1) and uses a boolean array to mark visited states.
It doesn't use STL, though as I was coding in C - it converts each permutation into its sequential number (from 0 to 9!-1) and uses a boolean array to mark visited states.
Re: ACM PKU Eight Puzzle
How did you do the conversion?
Re: ACM PKU Eight Puzzle
Like this:
Code: Select all
int fact[10]; // a table of factorials
int encode(int a[9]) {
int c[10], i, k, r;
for (i = 0; i < 9; i++) c[i] = i;
for (r = 0, k = 0; k < 9; k++) {
r += c[a[k]] * fact[8 - k];
for (i = a[k]; i < 9; i++) c[i]--;
}
return r + 1;
}
void decode(int a[9], int r) {
int c[10], i, k;
for (i = 0; i < 9; i++) c[i] = i;
for (r--, k = 0; k < 9; k++) {
i = r / fact[8 - k];
r %= fact[8 - k];
a[k] = c[i];
for (; i < 9; i++) c[i] = c[i + 1];
}
}
Re: ACM PKU Eight Puzzle
Hey thank you so much.......!!!!!
Re: ACM PKU Eight Puzzle
I'm so tired getting WAs, what's wrong with my code?
Code: Select all
Deleted AC code
Last edited by fushar on Tue Apr 21, 2009 5:23 pm, edited 1 time in total.
Re: ACM PKU Eight Puzzle
Your program prints \0 character at the beginning of output:
Code: Select all
user@localhost:/tmp$ g++ -o p p.cc && ./p >output
2 3 4 1 5 x 7 6 8
user@localhost:/tmp$ hexdump -C output
00000000 00 75 6c 6c 64 64 72 75 72 64 6c 6c 75 72 64 72 |.ullddrurdllurdr|
00000010 75 6c 64 72 0a |uldr.|
00000015
user@localhost:/tmp$
Re: ACM PKU Eight Puzzle
What a silly bug..
Just changed
to
and got AC!!!!!!!
Thanks mf!!
Just changed
Code: Select all
if (x != -2)
{
trace(P[x]);
printf("%c", M[x]);
}
Code: Select all
if (P[x] != -2)
{
trace(P[x]);
printf("%c", M[x]);
}
Thanks mf!!
Re: ACM PKU Eight Puzzle
is this a Known Algorithm? can you explain more why to code like this ?:)mf wrote:Like this:Code: Select all
int fact[10]; // a table of factorials int encode(int a[9]) { int c[10], i, k, r; for (i = 0; i < 9; i++) c[i] = i; for (r = 0, k = 0; k < 9; k++) { r += c[a[k]] * fact[8 - k]; for (i = a[k]; i < 9; i++) c[i]--; } return r + 1; } void decode(int a[9], int r) { int c[10], i, k; for (i = 0; i < 9; i++) c[i] = i; for (r--, k = 0; k < 9; k++) { i = r / fact[8 - k]; r %= fact[8 - k]; a[k] = c[i]; for (; i < 9; i++) c[i] = c[i + 1]; } }
Last edited by Angeh on Wed Sep 02, 2009 12:17 am, edited 1 time in total.
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
Re: ACM PKU Eight Puzzle
It's just a simple algorithm to convert a permutation into its index (from 0 to 9!-1) and vice versa.