Do you have to use breadth first search?

In my (limited) experience, it's a pita, and noticeably slower than using depth first search, despite what you read in theory books.

I'm confident we can find the shortest path with it.

I'll post up a little example of it, in an edit to this, and see if you're not *really* tempted by it.

This is a DFS on a "simple" 8 digit slide puzzle.

Code:

/* Will solve via brute force, the 8 tile 2D "rubik's cube" puzzle, when finished
Adak, Nov. 2008
Status: just started 7/11/08
*/
#include <stdio.h>
void copyB(int);
int move1(int);
int move2(int);
int move3(int);
void showB(int);
int isSolved(int);
int b[2][4][20]; //b is shorthand for the board
int t[1][4]; //t is a temporary holding row
int line[20]; //the line of moves that are played
int main(void) {
int i, r, row, c, col, move, deep, depth, solved, reset, gar;
// test right shift
/* b[0][0][0] = 2; b[0][1][0] = 3; b[0][2][0] = 4; b[0][3][0] = 1;
b[1][0][0] = 7; b[1][1][0] = 6; b[1][2][0] = 5; b[1][3][0] = 8;
*/
// test row swap
/* b[0][0][0] = 8; b[0][1][0] = 7; b[0][2][0] = 6; b[0][3][0] = 5;
b[1][0][0] = 1; b[1][1][0] = 2; b[1][2][0] = 3; b[1][3][0] = 4;
*/
// test Rotate 4 inner tiles
/* b[0][0][0] = 1; b[0][1][0] = 3; b[0][2][0] = 6; b[0][3][0] = 4;
b[1][0][0] = 8; b[1][1][0] = 2; b[1][2][0] = 7; b[1][3][0] = 5;
*/
// test depth of 2, solution 1 + 2
/* b[0][0][0] = 7; b[0][1][0] = 6; b[0][2][0] = 5; b[0][3][0] = 8;
b[1][0][0] = 2; b[1][1][0] = 3; b[1][2][0] = 4; b[1][3][0] = 1;
*/
//test depth of 2, solution 2 + 3 no depth=2 solution found for 1+3
b[0][0][0] = 8; b[0][1][0] = 2; b[0][2][0] = 7; b[0][3][0] = 5;
b[1][0][0] = 1; b[1][1][0] = 3; b[1][2][0] = 6; b[1][3][0] = 4;
//test depth of , solution
/* b[0][0][0] = ; b[0][1][0] = 2; b[0][2][0] = 1; b[0][3][0] = 4;
b[1][0][0] = 8; b[1][1][0] = 7; b[1][2][0] = 6; b[1][3][0] = 5;
*/
printf("\n Starting position:\n");
showB(0);
//getch();
depth = deep = solved = reset = 0;
do {
move = 1; depth = 2;
while(1) { // this is the main loop, for now
++deep;
if(move == 1)
solved = move1(deep);
else if(move == 2)
solved = move2(deep);
else
solved = move3(deep);
if(solved)
break;
if(reset) { //depth was reset, move needs to reset to 1 again
move = 1;
reset = 0;
continue;
}
if(deep >= depth) {
line[deep-1] = 0;
deep = depth - 1;
if(++move > 3) {
deep -= 1;
move = line[deep] + 1;
if(move > 1)
reset = 1;
}
}
}
}while(!solved);
printf("\n\n\t Press Enter to Quit\n ");
gar = getchar(); gar++;
return 0;
}
void copyB(int d) { //copy the old board position, into the new depth
int r, c, temp;
for(r = 0; r < 2; r++)
for(c = 0; c < 4; c++)
b[r][c][d] = b[r][c][d-1];
}
int move1(int d) { //shifts all numbers one column to the right & wraps
int r, c, solved, temp;
solved = 0;
printf("\n Right shift:");
copyB(d);
//showB(d);
//++d;
for(r = 0; r < 2; r++) {
temp = b[r][3][d];
for(c = 2; c >-1 ; c--)
b[r][c+1][d] = b[r][c][d];
b[r][0][d] = temp;
}
showB(d);
line[d-1] = 1;
solved = isSolved(d);
return solved;
}
int move2(int d) { //swaps rows
int r, c, solved;
solved = 0;
printf("\n Swap rows:");
copyB(d);
//showB(d);
for(c = 0; c < 4; c++) {
t[0][c] = b[0][c][d];
b[0][c][d] = b[1][c][d];
b[1][c][d] = t[0][c];
}
showB(d);
line[d-1] = 2;
solved = isSolved(d);
return solved;
}
int move3(int d) { //turns the 4 inner tiles, clockwise
int r, c, solved, temp;
solved = 0;
printf("\n Rotate 4 inner tiles:");
copyB(d);
//showB(d);
temp = b[0][1][d];
b[0][1][d] = b[1][1][d];
b[1][1][d] = b[1][2][d];
b[1][2][d] = b[0][2][d];
b[0][2][d] = temp;
showB(d);
line[d-1] = 3;
solved = isSolved(d);
return solved;
}
void showB(int d) {
int r, c, tab;
printf("\n");
for(tab = 0; tab < d; tab++)
putchar('\t');
for(r = 0; r < 2; r++) {
for(c = 0; c < 4; c++)
printf(" %d", b[r][c][d]);
putchar('\n');
for(tab = 0; tab < d; tab++)
putchar('\t');
}
}
int isSolved(int d) {
int i, gar;
int done = 0;
if(b[0][0][d]==1 && b[0][1][d]==2 && b[0][2][d]==3 && b[0][3][d]==4)
if(b[1][0][d]==8 && b[1][1][d]==7 && b[1][2][d]==6 && b[1][3][d]==5) {
done = 1;
printf("\n\n\t\t It's solved!");
showB(d);
printf("\t Line: ");
for(i = 0; i < d; i++)
printf(" %d", line[i]);
//printf("\n\t Press Enter to Continue");
//gar = getchar(); ++gar;
}
return done;
}