C++

CISP 430 Assignment 4 Spring 2019 Recursive Maze Algorithm Implementation Write a program to find all solutions to the maze shown. 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 Resources: There is a Visual Basic executable version you may want to use to check your answers. All the C++ code for this lab is available in the class notes except for the recursive algorithm details which you have to write. Requirements: 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 recursive build algorithm similar to that in the N-Queens problem. (Also posted). 3) You MUST use the maze txt data provided in the demos for submission of final solutions. 4) Your program must find and output ALL the TEXT solutions to the maze. Turn in: 1) Complete paper source code listings. 2) Paper output captures of ALL SOLUTIONS AS TEXT STRINGS OF ORDERED PAIRS. Documentation standards: Follow the requirements in the syllabus regarding assignment

#include "stdio.h"

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

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

int maze[SIZE][SIZE] = { // the maze

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 cellOk(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);

}

/*

Page 21 of 81

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.

*/

bool build(int maze[SIZE][SIZE], Cell sol[SIZE*SIZE])

{

// a handy debug function

#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

// ...

}

/*

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 havebeen tried

}

return 0; // make compiler happy

}

/*

Checks if a cell is a valid move. Invalid moves are cells

that are blocked with a wall, or with a cell that is

part or the present path.

*/

int cellOk(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

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

}