Page 1 of 1
10085 - The most distant state
Posted: Tue Oct 07, 2003 5:18 pm
by sidky
I solved this problem with simple bfs and it took me almost 10 seconds. But i saw that many people have solved that in 0.000 seconds. Can anyone please help me how can i attain such speed?
Posted: Wed Oct 08, 2003 2:53 pm
by junjieliang
This might be a spoiler, but... skip this part if you don't want to know.
Precalculation
Notice that the answer depends ONLY on when the empty slot is, that is if the empty slot is in the lower left corner (as in sample input), the path is ALWAYS "UURDDRULLURRDLLDRRULULDDRUULDDR". So you will only have 9 different states to precalculate, after which you do some simply array manipulation.
Posted: Tue Oct 05, 2004 2:52 pm
by CC
consider the symmetry effect
so there are only three status ( corner, mid-boundary and central)
input and output give two, the last is to be precalculated
8-Puzzle
Posted: Wed Apr 11, 2007 10:52 pm
by lonelyone
Hi all:
I know there are many algorithm can be used to solve this problem quickly.
But somehow I wanna use DFS to solve this problem.
Problem Description:
Given a board state, I wanna use DFS to find the shortest path from Init state to Goal state(123456780).
Obviously, use DFS it should visit all possible branches(9!).
But the speed is not the serious problem, the most serious problem is the memory usage of DFS. It should memorize some information to maintain a stack. For example, zero position, path, board state, etc. So if I use recurtion and the stack is maintained by Computer. My program would crash because of stack overflow.
And then I use customize stack to simulate it. However, I encounter a problem that there are many same substates, some of them are at different depth. Then how should I do?
Below is my code, but it is wrong.
Anyone would help me out, or help me to revise it, or give me your code of DFS version. I will appreciate you alot.
You may use the test case below.
Obviously, there is one shortest solution, it is RDD.
Lonely
Re: 8-Puzzle
Posted: Thu Apr 12, 2007 9:54 am
by mf
lonelyone wrote:Given a board state, I wanna use DFS to find the shortest path from Init state to Goal state
DFS can't help you here. When you want
shortest path, use BFS.
And then I use customize stack to simulate it. However, I encounter a problem that there are many same substates, some of them are at different depth.
That's exactly why you got all those stack overflows and excessive memory usage.
If you don't skip previously-visited states, DFS visits something like O(4^depth) states, and in the worst case shortest solution needs 31 moves.
Use some date structure to remember which states were already visited, and when there's a move from current state to one of those, just ignore it.
Re: 8-Puzzle
Posted: Thu Apr 12, 2007 7:03 pm
by lonelyone
First of all, thanks for your kindness and response.
I wanna know why in the worst case shortest solution only needs 31 moves.
Can you explain it in some details.
Lonely
Re: 8-Puzzle
Posted: Thu Apr 12, 2007 7:52 pm
by mf
lonelyone wrote:I wanna know why in the worst case shortest solution only needs 31 moves.
I've solved problem
10085 (with BFS), and my program says so.
Re: 10085 - The Most Distant State
Posted: Sat Nov 19, 2011 5:00 pm
by datahaven
The discussion above is very dependent on how you interpret the problem statement.
There is nowhere in the problem statement that says that the integers on the tiles have to be either in the range 1-8 or, more importantly, unique numbers.
1 1 1
1 1 1
0 1 1
has a most distant state of
1 1 0
1 1 1
1 1 1
UURR
(or many other similar possible move combinations)
which your precalculated solution would fail on if you consider all states with a space in the same position to be the same.
Of course the large number of very quick pre-calculated solutions might suggest that the judge isn't testing this case and that it is actually the problem that is badly worded.
Adrian
Re: 10085 - The most distant state
Posted: Thu Feb 05, 2015 4:30 pm
by just_yousef
my code with map<string,int> was too slow so i tried to use hashing but i always get a path mush longer than the answer
this is my code
Code: Select all
#include<bits/stdc++.h>
using namespace std;
int t, dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }, state[10], par[1000000],
vist[1000000], id;
char move[5] = "URDL";
struct node {
int state[10], pos, dir;
} arr[1000003];
int hash(int *a) {
int ans = 0;
for (int i = 0; i < 9; ++i)
ans = ans * 10 + a[i];
return ans % 1000003;
}
void print_path(int x) {
if (x == -1)
return;
print_path(par[x]);
putchar(move[arr[x].dir]);
}
int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
for (scanf("%d", &t); t--;) {
int pos = -1;
for (int i = 0; i < 9; ++i) {
scanf("%d", &state[i]);
if (state[i] == 0)
state[i] = 9, pos = i;
}
int hs = hash(state), x;
vist[hs] = ++id;
arr[hs].pos = pos;
memcpy(arr[hs].state, state, sizeof state);
memset(par, -1, sizeof par);
queue<int> que;
que.push(hs);
while (que.size()) {
x = que.front();
que.pop();
for (int i = 0; i < 4; ++i) {
int a = arr[x].pos / 3 + dx[i], b = arr[x].pos % 3 + dy[i];
if (a < 0 || b < 0 || a > 2 || b > 2)
continue;
memcpy(state, arr[x].state, sizeof arr[x].state);
swap(state[arr[x].pos], state[a * 3 + b]);
hs = hash(state);
if (vist[hs] == id)
continue;
vist[hs] = id;
que.push(hs);
arr[hs].pos = a * 3 + b;
memcpy(arr[hs].state, state, sizeof state);
par[hs] = x;
arr[hs].dir = i;
}
}
static int cas = 1;
printf("Puzzle #%d\n", cas++);
for (int i = 0; i < 9; ++i) {
if (arr[x].state[i] == 9)
arr[x].state[i] = 0;
printf("%d%c", arr[x].state[i], (i + 1) % 3 == 0 ? '\n' : ' ');
}
print_path(x);
puts("");
}
return 0;
}
Re: 10085 - The most distant state
Posted: Thu Feb 05, 2015 9:26 pm
by brianfry713
After each test case output an empty line.
Re: 10085 - The most distant state
Posted: Thu Feb 05, 2015 9:35 pm
by just_yousef
no my problem in the first place that it produces answers with longer path.
and i don't know why ??