10085  The most distant state
Moderator: Board moderators

 New poster
 Posts: 50
 Joined: Wed Nov 06, 2002 1:37 pm
 Location: Planet Earth, Universe
 Contact:
10085  The most distant state
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?

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
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.
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.
8Puzzle
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
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.
Code: Select all
..cut
Obviously, there is one shortest solution, it is RDD.
Code: Select all
1
1 0 2
4 5 3
7 8 6
Last edited by lonelyone on Thu Apr 12, 2007 10:04 pm, edited 1 time in total.
Re: 8Puzzle
DFS can't help you here. When you want shortest path, use BFS.lonelyone wrote:Given a board state, I wanna use DFS to find the shortest path from Init state to Goal state
That's exactly why you got all those stack overflows and excessive memory usage.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.
If you don't skip previouslyvisited 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: 8Puzzle
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
I wanna know why in the worst case shortest solution only needs 31 moves.
Can you explain it in some details.
Lonely
Re: 8Puzzle
I've solved problem 10085 (with BFS), and my program says so.lonelyone wrote:I wanna know why in the worst case shortest solution only needs 31 moves.
Re: 10085  The Most Distant State
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 18 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 precalculated solutions might suggest that the judge isn't testing this case and that it is actually the problem that is badly worded.
Adrian
There is nowhere in the problem statement that says that the integers on the tiles have to be either in the range 18 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 precalculated solutions might suggest that the judge isn't testing this case and that it is actually the problem that is badly worded.
Adrian

 New poster
 Posts: 50
 Joined: Tue Dec 17, 2013 11:01 pm
Re: 10085  The most distant state
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
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;
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10085  The most distant state
After each test case output an empty line.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 50
 Joined: Tue Dec 17, 2013 11:01 pm
Re: 10085  The most distant state
no my problem in the first place that it produces answers with longer path.
and i don't know why ??
and i don't know why ??