Question

In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze. To ensure consistency of design, start your solution with maze_start.c.

The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the escape hatch or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm finds a dead end, it retraces its path until it reaches a position from which there is an untried path. The backtracking algorithm always tries all directions from any position, and always in the same order.

The input to the algorithm is a maze with walls (represented by '1' characters) and open passage ways (represented by '0' characters). The starting position of the mouse is represented by 'm' and the escape from the maze by 'e'. Your program will read the maze in from standard input. The first line of the input will contain the number of rows and the number of columns in a maze. Thus, the input might look like the following:

6 5
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
    

The maze will always have a wall around the outside, so you need not be concerned about the mouse falling off the maze as it explores all directions.

The backtracking algorithm keeps a list of positions that are the beginnings of paths it has yet to try. From the current position, the algorithm adds any untried open neighbouring positions (if there are any), always looking forward, backward, left and right from the current position. At each step, the algorithm gets the next position from the list and adds into the list the untried neighbouring positions. Finally, the algorithm must mark each visited position with a period ('.') to avoid revisiting positions — so that it will not loop forever trying the same routes.

The backtracking algorithm works as follows:

read in the maze;
initialize the list;
goalCell = the position of the escape hatch in the maze;
startCell = the initial position of the mouse in the maze;
currentCell = startCell;
while currentCell is not the goalCell
  mark currentCell as visited;
  add to the list the unvisited open neighbours of currentCell;
  if the list is empty
    the mouse is trapped: we tried all routes and failed to find an escape;
  else
    get the next cell from the list and make it currentCell;
end while;
the mouse can escape the maze: we reached the goal cell.
    

To support the backtracking algorithm you will need to implement a linked list. To work correctly, all you need is to always add a cell at the top of the list and always get the next cell from the top of the list (no traversals or ordering required — what we are actually building is called a stack).

Your program must print out the maze after each cell is visited, showing which cells have already been visited. Finally, your program will print out a message indicating whether an escape was found or that the mouse is trapped. Sample output can be found in the file testMazeOutput.txt.

To develop your program, you can use the input file testMaze.txt, which contains the above maze.

maze_start.c.:

#include
#include
#include

//-------------------------------------------------------------------------------------
// CONSTANTS and TYPES
//-------------------------------------------------------------------------------------

#define MAX_DIMENSION 20

// constant definitions for the different cell states
const char WALL    = '1';
const char SPACE   = '0';
const char VISITED = '.';
const char MOUSE   = 'm';
const char EXIT    = 'e';

typedef enum BOOL { false, true } Boolean;

struct CELL
{
int row;
int column;
};
typedef struct CELL Cell;

typedef struct CELL_NODE CellNode;
struct CELL_NODE
{
Cell     cell;
CellNode *next;
};

//-------------------------------------------------------------------------------------
// VARIABLES
//-------------------------------------------------------------------------------------

CellNode *top = NULL;

// a 2D array used to store the maze
char maze[MAX_DIMENSION][MAX_DIMENSION];
int mazeRows;
int mazeCols;

// holds the location of the mouse and escape hatch
Cell mouse;
Cell escape;

//-------------------------------------------------------------------------------------
// PROTOTYPES
//-------------------------------------------------------------------------------------

// basic cell manipulation

// returns true if the cells are at the same position in our maze
Boolean equalCells(const Cell cell1, const Cell cell2);
// returns a new cell object
Cell makeCell(const int row, const int col);
// returns true if the cell is within our maze
Boolean validCell(const Cell theCell);

// routines for managing our backtracking

// returns true if there are no more cells to try
Boolean noMoreCells();
// returns the next cell to try for a path out of the maze
Cell nextCell();
// introduces a new cell to try
void addCell(const Cell cell);

void printMaze();
void loadMaze();

// returns true if there's a solution to the maze
Boolean solveMaze();

// our invariant checker
void checkState();

//-------------------------------------------------------------------------------------
// FUNCTIONS
//-------------------------------------------------------------------------------------

int main( int argc, char *argv[] )
{
    loadMaze();

    if ( solveMaze() )
      printf( "The mouse is free!!!!\n" );
    else
      printf( "The mouse is trapped!!!!\n" );
   
    printf( "\nEnd of processing\n" );
   
return EXIT_SUCCESS;
}

//////////////////////////////////////////////
// Cell routines
//////////////////////////////////////////////

//////////////////////////////////////////////
// List routines
//////////////////////////////////////////////

//////////////////////////////////////////////
// Maze routines
//////////////////////////////////////////////

testMazeOutput.txt.:

100e1
11101
1m101
10001
11111

11111
100e1
11101
1.101
10001
11111

11111
100e1
11101
1.101
1.001
11111

11111
100e1
11101
1.101
1..01
11111

11111
100e1
11101
1.101
1...1
11111

11111
100e1
11101
1.1.1
1...1
11111

11111
100e1
111.1
1.1.1
1...1
11111

The mouse is free!!!!

End of processing

testMaze.txt:

6 5
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1