## 652 - Eight

Moderator: Board moderators

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

### 652 - Eight

How do you solve this problem using BFS? Firstly, wouldn't the queue get too large for memory? Second, how do you prevent going into a loop? You cannot store the shortest path to each possible state...that would be someting like 10!, right? (I'm not very good with combinatorics)...

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
- There are 9! = 362880 configurations, so you can represent one with a single int. A queue of 362880 ints is not too large.
- You have a bool-array to tell whether you've visited a configuration already to prevent loops.
- You only store the predecessor of a configuration, not the whole path. After you're done, you reconstruct the path to your favourite node.

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
Hi Pochmann !
Would u pls give some hints how to handle the 2nd part,i.e. how to prevent the loops by bool-array. As a beginner, I couldn't find out any other way except linear-checking that would be judged as TimeLimitExceeded.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
You MUST get a unique number for each state. Probably one of the hardest parts of the problem is to limit the number.

Naturally, since there are 362880 different states, you want to number them 0 - 362879. Here's how:

x 1 2 3 4 5 6 7 8 = state 0
x 1 2 3 4 5 6 8 7 = state 1
....
1 2 3 4 5 6 7 8 x = state 46233
....
8 7 6 5 4 3 2 1 x = state 362879

Just imagine you have a set of permutations of x and 1 to 8, with x having the lowest digit value. State 0 will be the "lowest" permutation in the set, while the last state will be the "highest" permutation in the set. Hope you understand.

Good luck!

Regards,
lim z******

P.S. I am also encountering problems with this problem. The coding is really quite tedious.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
BTW, please remember that this problem is a mutliple-input problem. Be careful. Good luck!

Regards,
lim z******

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### 652 Eight (..need help..)

I tried to solve the problem by "BFS algorithm".

But it is difficult to deal with.

Is there any tricks in this problem?

thanks!

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Use IDA* algorithm.
Search for it in google for instance.

Good luck.

ER_N
New poster
Posts: 3
Joined: Thu May 08, 2003 6:03 pm

### 652 Whats wrong ?

Compile Error, but it work on my Borland C 3.1
[c]
#include <stdio.h>
#include <stdlib.h>
static int dx[] = {0, -1, 0, 1};
static int dy[] = {1, 0, -1, 0};
static char moveDescription[] = {'d', 'l', 'u', 'r'};
static int oppositeMove[] = { 2 , 3 , 0 , 1 };
static long int infinity = 2147483647;

int y0, x0;
int goalX[9], goalY[9];
int board[3][3];
int deepness;
char resultString[255];
char LenresultString = 0;
int minPrevIteration;

void initGoalArrays() {
for (int i=0; i<=7; i++) {
goalX[i+1] = i % 3;
goalY[i+1] = i / 3;
}
goalX[0] = 2; goalY[0] = 2;
}
void swap(int y1, int x1, int y2, int x2) {
int temp, value1, value2;
value1 = board[y1][x1];
value2 = board[y2][x2];
board[y1][x1] = value2;
board[y2][x2] = value1;
};
//-------------------------------------------------------------------------
char isSolvable (){
char a[] = {0,0,0,0,0,0,0,0};
char i,j,k = 0, Dp = 0;

for (i=0; i < 3; i++)
for (j=0; j < 3; j++) if(board[j]) {
a[k] = board[j];
k++;}

for (i=0; i < 7; i++)
for (j= i + 1; j < 8; j++) if (a > a[j]) Dp++;

if (!(Dp%2)) return 1;
return 0;
}
//-------------------------------------------------------------------------
int estimate() {
int manhattan = 0, i, j, value;
for (i=0; i < 3; i++) for (j=0; j < 3; j++) {
value = board[j];
if (value ) manhattan += abs(j-goalX[value]) + abs(i-goalY[value]);
}
return manhattan;
}
//---------------------------------------------------------------------------
//DFS f=g+h < deepness
char recSearch(int g, int previousMove, int x0, int y0)
{
int h = estimate();
if (h == 0) return 1;
int f = g + h;
if (f > deepness) {
if (minPrevIteration > f) minPrevIteration = f;
return 0;
}

for (int i = 0; i < 4; i++)
if (oppositeMove != previousMove) {
int newx = x0 + dx, newy = y0 + dy;
if ((newy < 3) && (newy >= 0) && (newx < 3) && (newx >= 0)) {
swap(y0, x0, newy, newx);
char res = recSearch(g+1, i, newx, newy);
swap(y0, x0, newy, newx);
if (res) {
LenresultString++;
int l;
for (l = LenresultString ; l > 0;l--)
resultString[l] = resultString[l-1];
resultString[0] = moveDescription;
return 1;
}
}
}
return 0;
}
//--------------------------------------------------------------------------
char idaStar() {
char res = 0;
deepness = estimate();
do {
minPrevIteration = infinity;
res = recSearch(0, -1, x0, y0);
if (res) break;
deepness ++;
} while (deepness < 100);
return res;
}
//------------------------------------------------------------------
int main() {
resultString[0] = '\0';
char buf[18],b;
int i,j = 0;
gets(buf);
for(i = 0; i < 17; i += 2){
if ((buf == 120) || (buf == 88 )) {
board[j/3][j%3] = 0; x0 = j%3; y0 = j/3; }
else board[j/3][j%3] = buf[i] - 48;
j++;
}
initGoalArrays();
if (isSolvable()) {
idaStar();
printf("\n");
puts(resultString);
} else{
printf("\n");
printf( "unsolvable");
}
return 0;
}[/c]
=)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If you post it as C, you get CE always because of your comments .... and beacause of declaration of variable in for loop

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
hello. i tried this problem to solve with BFS. there are only 9!/2 legal moves, so first i generate all the legal states, and the moves required to generate them. then i sort the states, and then for each input state perform a binary-search on the stored results to find the answer. this takes ~2 secs in the judge-machine. what i am getting is WA. any suggestions from anyone?

here's some sample I/O. are they correct?
input:

Code: Select all

``````12

x 8 7 6 5 4 3 2 1

6 8 7 x 5 4 3 2 1

8 x 7 6 5 4 3 2 1

6 8 7 3 5 4 x 2 1

6 8 7 5 x 4 3 2 1

8 5 7 6 x 4 3 2 1

8 7 x 6 5 4 3 2 1

2 1 8 5 4 3 7 6 x

2 1 x 5 6 8 7 3 4

2 1 8 5 x 6 7 3 4

2 4 1 5 6 8 x 7 3

1 7 8 2 5 4 x 6 3``````
output

Code: Select all

``````ddrruullddrruullddrruullddrr

rrddlluurrddlluurrddlluurrd

ddrruullddrruullddrruullddr

rrddlluurrddlluurrddlluurr

rrddlluurrddlluurrddlluurrdl

ddrruullddrruullddrruullddru

ddrruullddrruullddrruulldd

ddruuldrrdllurrdlulu

ddruuldrrdllurrdluuldd

ddruuldrrdlluruldrrdlu

drdrulldrrululdrur

drdrulurddluulddrurulldrur``````

i tried IDA* for this using the "manhattan" heuristic. but i got TLE. anything else i should try?

thanx.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
BFS should work, but it is rather slow. I sped up my program with A*, but making sure I do not repeat states.

ER_N
New poster
Posts: 3
Joined: Thu May 08, 2003 6:03 pm
But Now : Runtime Error (SIGSEGV) =((
[cpp]
#include <iostream.h>
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
char moveDescription[] = {'d', 'l', 'u', 'r'};
int oppositeMove[] = { 2 , 3 , 0 , 1 };
long int infinity = 2147483647;

int y0, x0;
int goalX[9], goalY[9];
int board[3][3];
int deepness;
char resultString[255];
char LenresultString = 0;
int minPrevIteration;
int abs ( int x) {
if ( x < 0) return x*(-1);
return x;
}

int initGoalArrays() {
for (int i=0; i<=7; i++) {
goalX[i+1] = i % 3;
goalY[i+1] = i / 3;
}
goalX[0] = 2; goalY[0] = 2;
return 0;
}

int swap(int y1, int x1, int y2, int x2) {
int temp, value1, value2;
value1 = board[y1][x1];
value2 = board[y2][x2];
board[y1][x1] = value2;
board[y2][x2] = value1;
return 0;
};

char isSolvable (){
char a[] = {0,0,0,0,0,0,0,0};
char i,j,k = 0, Dp = 0;

for (i=0; i < 3; i++)
for (j=0; j < 3; j++) if(board[j]) {
a[k] = board[j];
k++;}

for (i=0; i < 7; i++)
for (j= i + 1; j < 8; j++) if (a > a[j]) Dp++;

if (!(Dp%2)) return 1;
return 0;
}

int estimate() {
int manhattan = 0, i, j, value;
for (i=0; i < 3; i++) for (j=0; j < 3; j++) {
value = board[j];
if (value ) manhattan += abs(j-goalX[value]) + abs(i-goalY[value]);
}
return manhattan;
}

char recSearch(int g, int previousMove, int x0, int y0)
{
int h = estimate();
if (h == 0) return 1;
int f = g + h;
if (f > deepness) {
if (minPrevIteration > f) minPrevIteration = f;
return 0;
}

for (int i = 0; i < 4; i++)
if (oppositeMove != previousMove) {
int newx = x0 + dx, newy = y0 + dy;
if ((newy < 3) && (newy >= 0) && (newx < 3) && (newx >= 0)) {
swap(y0, x0, newy, newx);
char res = recSearch(g+1, i, newx, newy);
swap(y0, x0, newy, newx);
if (res) {

LenresultString++;
int l;
for (l = LenresultString ; l > 0;l--)
resultString[l] = resultString[l-1];
resultString[0] = moveDescription;
return 1;
}
}
}
return 0;
}

char idaStar() {
char res = 0;
deepness = estimate();
do {
minPrevIteration = infinity;
res = recSearch(0, -1, x0, y0);
if (res) break;
deepness ++;
} while (deepness < 100);
return res;
}

int main() {

resultString[0] = '\0';
char buf[255],b;
int i,j = 0;

cin.get(buf,255,'\n');
for(i = 0; i < 17; i += 2){
if (buf == 120) { board[j/3][j%3] = 0; x0 = j%3; y0 = j/3; }
else board[j/3][j%3] = buf - 48;
j++;
}
initGoalArrays();
if (isSolvable()) {
idaStar();
cout << resultString;
} else cout << "unsolvable";
return 0;
}
[/cpp]
=)

ER_N
New poster
Posts: 3
Joined: Thu May 08, 2003 6:03 pm
=)

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
I did it by BFS, too. When the queue becomes empty, then the puzzle is unsolvable.
It ran just in time(9.xx seconds) without other strategies. But there are many ways to speed up.
1) Check whether the puzzle is solvable before searching by the approach: http://mathworld.wolfram.com/15Puzzle.html
2) Using BFS, one should avoid entering the same state.
We can treat map 12345678x as #1, ...1234567x8 as #2, ...x87654321 as #362880(=9!),
calculate the number in a mathematical way and use a flag table to memorize whether the state was visited or not.
3) I think IDA* will be faster?..and can be applied to acm10181 (15 puzzle)