Thread: Shortest Path Maze Solver (Breadth Search Help)

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

Yes a breadth-first search is essentially going to find the shortest path, but it will be very slow!
To speed it up, rather than examining all paths of length n before those of length n+1, you have a heuristic that biases it towards following those paths that are getting you measurably closer to the goal. This is the basic idea behind the algorithm called A*. That algorithm is what you need to read up on.

BFS is a really fun exercise. You could have really wowed your professor if you had let them pick which method they wanted to use from a menu.

Anyway, back to BFS:

Code:

add the starting point to the first list
while not at the exit 
    for each room in one list
        if not exit
            add its neighbors to the other list
        else
            return the shortest path
    swap lists

Quzah.