Modify the following program to find all solutions to a LARGE maze.

Base your program on the code for the 10 x 10 matrix provided below. But modify the following source code to work for a 100 x 100 matrix of your design. Also, OPTIMIZE your algorithm to search for the best path first, instead of the default east west north south approach. Your program may use hard-coded array initialization to define the maze. The output should be a character string of the form:

A solution was found at: (1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) (3, 5) (3, 6) (2, 6) (1, 6) (1, 7) (1, 8) (2, 8) (3, 8) (4, 8) (4, 7) (5, 7) (6, 7) (6, 6) (7, 6) (8, 6) (8, 7) (8, 8)

A solution was found at: (1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) (3, 5) (3, 6) (2, 6) (1, 6) (1, 7) (1, 8) (2, 8) (3, 8) (4, 8) (4, 7) (5, 7) (6, 7) (6, 6) (7, 6) (7, 5) (8, 5) (8, 6) (8, 7) (8, 8) etcfor all possible solutions, except of course for your large custom matrix instead of the 10 x 10 solutions shown above.

1) You MUST base your solution on the supporting code structure and functions provided. (Although you may translate it into another language if you wish). 2) You must use a 100 x 100 matrix. 3) You must optimize your code so that it tries the best direction first. 4) Your program must find and output ALL the TEXT solutions to the maze.

Source Code is as follow:

#include using namespace std;

#define SIZE 10 //#define DEBUG

// GLOBAL DATA

// a cell type containing a row and column position // and the compass direction most recently moved struct cell_type { int row; int col; int dir; // the most recent compass direction, 'n', 's', 'e', 'w', 0 }; typedef struct cell_type Cell;

// the solution represented as an array of Cells Cell sol[SIZE * SIZE];

// the maze int maze[SIZE][SIZE] = { 1,1,1,1,1,1,1,1,1,1, 1,0,0,0,1,1,0,0,0,1, 1,0,1,0,0,1,0,1,0,1, 1,0,1,1,0,0,0,1,0,1, 1,0,0,1,1,1,1,0,0,1, 1,1,0,0,0,0,1,0,1,1, 1,0,0,1,1,0,0,0,0,1, 1,0,1,0,0,0,0,1,1,1, 1,0,0,0,1,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1 };

// FUNCTION PROTOTYPES void build(int); void printSolution(int); int is_safe(int); int getNextCell(int);

int main(void) { // set starting position and direction sol[0].row = 1; sol[0].col = 1; sol[0].dir = 0;

// start recursive solution build(0); }

/* A recursive function to determine a path through the maze. Called for each cell in the solution array. Finds the next valid cell to move to, then calls itself for the next cell. Inside the function, all possible moves for the current cell are tried before the function returns. */ void build(int n) { // loop while there are more possible moves while (getNextCell(n)) {

#ifdef DEBUG printf("Iteration: %d\tAt: (%d, %d)\t Trying: (%d, %d) ", n, sol[n].row, sol[n].col, sol[n + 1].row, sol[n + 1].col); #endif // check if this possibility is a valid move if (is_safe(n)) {

// is the next possibility the end of the maze? if (sol[n + 1].row == SIZE - 2 && sol[n + 1].col == SIZE - 2) // print the solution so far printSolution(n + 1); else // get the next move build(n + 1); } } }

/* Outputs the current solution array. */ void printSolution(int n) { int i;

printf(" A solution was found at: "); for (i = 0; i <= n; i++) printf("(%d, %d) ", sol[i].row, sol[i].col); printf(" "); }

/* Determines the next cel to try. Increments the position of the next cell and increments the direction of current cell. Directions are tried in the order east, south, west, north. */ int getNextCell(int n) { // set initial position and direction for the next cell sol[n + 1].row = sol[n].row; sol[n + 1].col = sol[n].col; sol[n + 1].dir = 0;

// try all positions; east, south, west, north // increment direction of current cell // increment postion of next cell switch (sol[n].dir) { case 0: sol[n].dir = 'e'; sol[n + 1].col++; return 1; case 'e': sol[n].dir = 's'; sol[n + 1].row++; return 1; case 's': sol[n].dir = 'w'; sol[n + 1].col--; return 1; case 'w': sol[n].dir = 'n'; sol[n + 1].row--; return 1; case 'n': return 0; // all directions have been tried } return 0; // make compiler happy }

/* Looks ahead to checks if a candidate cell is a safe move. Unsafe moves are cells that are blocked with a wall or current path. */ int is_safe(int n) { int i;

// check if cell is a border cell if (maze[sol[n + 1].row][sol[n + 1].col]) return 0;

// check if we are attempting to cross our own path for (i = 0; i < n; i++) // if where we want to go is somewhere we've been... if (sol[n + 1].row == sol[i].row && sol[n + 1].col == sol[i].col) return 0;

return 1; }