10085 - The most distant state

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

10085 - The most distant state

Post by sidky » Tue Oct 07, 2003 5:18 pm

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?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Oct 08, 2003 2:53 pm

This might be a spoiler, but... skip this part if you don't want to know.








Precalculation :wink:
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.

CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am

Post by CC » Tue Oct 05, 2004 2:52 pm

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

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

8-Puzzle

Post by lonelyone » Wed Apr 11, 2007 10:52 pm

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.

Code: Select all

..cut
You may use the test case below.
Obviously, there is one shortest solution, it is RDD.

Code: Select all

1
1 0 2
4 5 3
7 8 6
Lonely
Last edited by lonelyone on Thu Apr 12, 2007 10:04 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 8-Puzzle

Post by mf » Thu Apr 12, 2007 9:54 am

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.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Re: 8-Puzzle

Post by lonelyone » Thu Apr 12, 2007 7:03 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 8-Puzzle

Post by mf » Thu Apr 12, 2007 7:52 pm

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. :)

datahaven
New poster
Posts: 4
Joined: Thu Nov 10, 2011 3:17 am

Re: 10085 - The Most Distant State

Post by datahaven » Sat Nov 19, 2011 5:00 pm

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

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10085 - The most distant state

Post by just_yousef » Thu Feb 05, 2015 4:30 pm

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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10085 - The most distant state

Post by brianfry713 » Thu Feb 05, 2015 9:26 pm

After each test case output an empty line.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10085 - The most distant state

Post by just_yousef » Thu Feb 05, 2015 9:35 pm

no my problem in the first place that it produces answers with longer path.
and i don't know why ??

Post Reply

Return to “Volume 100 (10000-10099)”