OJ Board

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

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

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.
Thanks in advance.

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.

BTW, please remember that this problem is a mutliple-input problem. Be careful. Good luck!

Regards,
lim z******

Can you give me some tips about this problem?

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

But it is difficult to deal with.

Is there any tricks in this problem?

thanks!

Use IDA* algorithm.
Search for it in google for instance.

Good luck.

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]

If you post it as C, you get CE always because of your comments .... and beacause of declaration of variable in for loop

DM

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: output
i tried IDA* for this using the "manhattan" heuristic. but i got TLE. anything else i should try?

thanx.

BFS should work, but it is rather slow. I sped up my program with A*, but making sure I do not repeat states.

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]

Could you see http://acm.uva.es/board/viewtopic.php?t=2903

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)

hello. thanx to everyone, i did get AC after all.

my solution with IDA* takes ~0.5 secs and with BFS, it takes ~3.7 secs. so yes, it seems IDA* is faster.

thanx again.