Recursive Maze Algorithm Implementation

/* A recursive algorithm to determine all possible paths through a maze. Dan Ross, circa 2000-2020 */ #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 The maze given in the source code has 64 total "playable" cells with 43 open cells. Let's call this an "Openness" of 43/64=67%. Create about 10 more mazes with various Openness's between 5% and 90%. Run your program(s) for each maze, and count the total number of solutions and the total execution time. Format your output into a table with 3 columns: Openness | Execution time | Number of Solutions. Plot the results on 2 graphs. Graph 1 would be execution time (y) vs density (x). Graph 2 would be number of solutions ( y ) vs density (x). Compare the curves to known time complexities. Then comment on everything in the conclusions. Mazes could be manually generated or randomly generated, but they should look "random". Big Oh Analysis: In your submission document, include a conclusions section with comments on the time complexity. Also comment on any implementation issues, memory issues, or anything else you encountered during development. Resources: There is a Visual Basic executable version you can use to check your understanding of the algorithm. This exe requires the supporting maze.txt input file. All the starter C/C++ code for this lab is available in the posted 88 maze.cpp file. Requirements: 1) You MUST base your solution on the supporting code structure and functions provided. 2) Your program(s) must find and output ALL the TEXT solutions for each maze. 3) You MUST produce the plots requested above. There is a video posted on how to use Excel to plot stuff, but you can use other tools too. Turn in: 1) Complete source code listings. 2) Partial console output screen captures of solutions. (1,1)(1,2) etc. 3) The graphs. 4) Comments on your analysis and conclusions. 5) An APPENDIX with full text output for all solutions