I will send all the instructions and required file once the question is accepted

This needs to be done within 15 hours

Depth First Search

This assignment uses Depth first search to find the solution to a maze.

There is a lot of background reading in this README, covering enumerations, 2D arrays, and depth first search. Please read the README fully to make sure you understand the concepts used in this homework.

Learning Goals

You will learn:

• Enumerations and complex data type
• 2D arrays
• More recursion
• Depth first search

Background

Enumerations

An enumeration data type specifies a set of constant (integer) values that are all distinct. You can either set the constant values yourself:

<code>typedef enum Month {
  JANUARY = 1,
  FEBRUARY = 2,
  MARCH = 3,
  APRIL = 4,
  MAY = 5,
  JUNE = 6,
  JULY = 7,
  AUGUST = 8,
  SEPTEMBER = 9,
  OCTOBER = 10,
  NOVEMBER = 11,
  DECEMBER = 12
} Month;
</code>

Or you can let the compiler choose the values for you:

<code>typedef enum Day {
  SUNDAY,
  MONDAY,
  TUESAY,
  WEDNESDAY,
  THURSDAY,
  FRIDAY,
  SATURDAY
} Day;
</code>

(Note that by convention we make the constants in the enumeration ALL CAPS)

You can then use these values as constants throughout your program. If you define a variable as having an enumeration type, you’re saying that you want its values to be restricted to those constants:

Month birthmonth = AUGUST;

Enumerations are a convenient way of defining a set of constants that are related to each other. This will let us use specific constants throughout our program without having to change all of them if we decide to change the values of the constants.

In this assignment, we are using two enumerations. The first defines the “types” of maze squares: a wall, an empty space, the starting point, and the ending point:

<code>typedef enum SquareType {
    WALL = '#',
    SPACE = '.',
    START = 's',
    END = 'e'
} SquareType;
</code>

(Note that we’re taking advantage of the fact that C treats characters as integers of the appropriate ASCII value).

Throughout your code, when you want to see whether a particular value is a wall, you should test if it is equal to WALL, not #. That way, if we later want to change what walls look like in our maze, it will be easy.

The second enumeration defines the possible directions you can move in your path:

<code>typedef enum PathType {
    NORTH = 'n',
    SOUTH = 's',
    EAST = 'e',
    WEST = 'w'
} PathType;
</code>

Complex Structures

Up until now, we have mostly dealt with structures whose fields are simple data types or arrays. But we can also have the fields of a structure be another type like a structure or an enumeration. Consider the types we will use to define our maze (in maze.h):

<code>typedef struct MazeSquare {
    SquareType type;
    bool visited;
} MazeSquare;
</code>

This is a structure that represents a single square in the maze. It has a particular type (using the enumeration type from above), and a flag that lets us know whether we’ve visited this square before or not (useful for checking if your path has loops).

<code>typedef struct MazePos {
    int xpos;
    int ypos;
} MazePos;
</code>

This is a simple structure that captures the location of a particular square in a maze.

<code>typedef struct Maze {
    MazeSquare * * maze; //2D array holding maze
    int width; //Number of columns in maze
    int height; //Number of rows in maze
    MazePos start; //Location of 's'
    MazePos end; //Location of 'e'
} Maze;
</code>

This structure represents an entire maze. It has a width and height, it uses the MazePos structure to capture the starting position in the maze and the ending position in the maze, and it uses a 2D Array of MazeSquares to represent the maze grid itself.

2D Arrays

What are two-dimensional arrays? If you know how many rows and columns you want your array to have, you can define a 2D array easily:

<code>float matrix[10][20]; //a 10x20 matrix
</code>

But what if you don’t know how many rows and columns you need? We’ll have to use dynamic memory allocation, just like we did when we needed arrays of unknown size.

To allocate a 2D array, we will build an array of arrays. We will have an array (representing the rows of the 2D array) where each element of the array is another array. Allocating 2D arrays is tricky, since we don’t know how many rows and columns we need. We have to do it in two steps.

First, we allocate the array of rows. Because each entry needs to be an array of floats itself, the type of this array is a pointer to a pointer to a float:

<code>float * * matrix = malloc(nrows * sizeof(float *));
</code>

This creates an array of nrows pointers to floats. Second, for each of those pointers we allocate an array of floats:

<code>for (int i = 0; i < nrows; i++) {
  matrix[i] = malloc(ncols * sizeof(float));
}
</code>

We can now use matrix as a normal 2D array. To access the 2nd row and 5th column, we can write matrix[1][4].

Freeing a 2D Array

To deallocate a 2D array, we reverse the steps. First, we free each of the rows, then we free the array that points to all the rows.

<code>for (int i = 0; i < nrows; i++) {
  free(matrix[i]);
}
free(matrix);
</code>

Note that we can’t do this in the other order! If we free(matrix) first, we will have no way of getting the addresses of the row arrays we need to free.

2D Array Coordinates vs. Cartesian Coordinates

Note that 2D arrays (and matrices) work very differently than Cartesian coordinates. Suppose you have a 2D grid of letters:

<code>a b c d
e f g h
i j k l
</code>

Then your 2D grid has 4 columns (width = 4) and 3 rows (height = 3) You should thus create a 2D array with 3 rows and 4 columns (note that with arrays we list the rows first, then the columns).

The coordinate system we use for 2D arrays (and matrices) is different than Cartesian coordinates.

In Cartesian coordinates, (0, 0) is at the bottom left of the grid (the letter ‘i’). In 2D arrays (and matrices), [0][0] is at the top left of the grid (the letter ‘a’).

In Cartesian coordinates, we list the x position first and then the y position. For 2D arrays (and matrices), we list the y position (the row) first and then the x position (the column).

In Cartesian coordinates, incrementing the “y” position moves up. In 2D arrays (and matrices), incrementing the row number moves down (the first row is row 0, the second row is row 1, etc.).

So in Cartesian coordinates, (2, 3) would represent the letter ‘b’, but in 2D arrays, [2][3] would represent the letter ‘l’.

Depth first search

Depth first search is one of the most common search strategies and it is one that lends itself to recursion. Suppose you are standing in the middle of a maze (sort of like you are in this assignment!) and want to figure out where the exit is. How might you find your way out?

Here is one strategy: start walking through the maze. Each time you arrive at a choice of directions, pick one and keep walking. If you reach a dead end, or get to a part of the maze you’ve seen before, back up to the last place you made a choice and make a different one. Eventually, you will either find the exit of the maze or explore the entire maze and decide that there is no way out.

Consider trying to find your way out of this maze:

<code>.#.#
...#
e#..
#s.#
</code>

Assume that at each square, we try to go north, then south, then east, then west.

We start at s, and try to go N. We hit a wall, so we back up and try to go S. We go out of bounds, so we try to go E, which succeeds. We’re now in this situation, where the * shows where we are:

<code>.#.#
...#
e#..
#s*#
</code>

We try to go N, which succeeds. We try to go N again, which succeeds. We try to go N again, which succeeds. We’re now in this situation:

<code>.#*#
...#
e#..
#s.#
</code>

We try to go N again, which fails (out of bounds). We try to go S, which fails (we’ve already been to that square!), E, which fails (we hit a wall), then W, which fails (we hit a wall). Since we don’t have anywhere to go from here, we back up to the last place we made a choice:

<code>.#.#
..*#
e#..
#s.#
</code>

Now we try to go N (fails: already been to that square); S (fails: already been to that square); E (fails: wall); then W (succeeds):

<code>.#.#
.*.#
e#..
#s.#
</code>

Now we try to go N (fails: wall); S (fails: wall); E (fails: already been there); and W (succeeds):

<code>.#.#
*..#
e#..
#s.#
</code>

We then go N, which succeeds:

<code>*#.#
...#
e#..
#s.#
</code>

From here, there is no successful move to make, so we back up to the last place we made a choice:

<code>.#.#
*..#
e#..
#s.#
</code>

and try the next choice, S, which gets us to the exit!

The reason we call this a depth-first search is that we try each possible path until we can’t keep moving forward, then we back up one choice and try again, and so forth. Other searches may not explore a single path all the way to the end before trying a different path.

Depth First Search with Recursion

Depth first search can be readily solved with recursion. Each recursive call “visits” a single square in the maze and explores each of the possible paths leading out from that square. The goal of a sequence of recursive calls is to explore a specific path through the maze, and each time you call the recursive function, you’re making the path one step longer and visiting one more square of the maze.

You should interpret your recursive function as implementing the following logic: “Given all the squares I have visited so far, can I exit the maze by adding this square to the solution path?”” If the answer is no, that means the current square is not part of the solution path, and the recursive method should return false. If the answer is yes, that means the current square is part of the solution path, and you should add the square to the current path and return true.

The base case for a square is that the square represents the end of a path:

1. It has been visited already — the path can’t be extended this way, so return false
2. It is a wall — this path fails, so return false.
3. It is out of bounds — this path fails, so return false.
4. It is the exit — this path succeeds, so return true and add this square as the last square in the path

The recursive case for a square is that it doesn’t fall into one of the above four categories: it is an empty square that you haven’t visited before. In that case, the recursive case tries to make the path one step longer by visiting one more square in the maze: recursively call your search method four times, once for each of the four directions you could possibly move.

So what do you do with the return value of the four recursive calls you make?

1. If one of them returns true, that means the direction that call explores is on the solution path, which also means the current square is on the solution path. Add the current square to the solution path, and return true.
2. If the recursive call returns false, that means that direction doesn’t work, so move on to the next recursive call.
3. If all the recursive calls return false, that means the current square can’t be on the solution path, so return false.

(Don’t forget to mark the current square as visited when the recursive method returns!)

Note that this recursive function follows the usual pattern: it calls itself and assumes those calls do the right thing.

What do you need to do?

In this assignment, you only need to write one method, depthFirstSolve in solver.c. depthFirstSolve is called by solveMaze, as you can see in the code, and is meant to be the recursive method that implements the logic described above. It takes four arguments:

1. Maze * m: the maze you are trying to solve. Maze is declared in maze.h. Functions to read in the maze (readMaze) and free the maze (freeMaze) are defined in maze.c. Pay careful attention to the comments for the readMaze declaration in maze.h; they explain in detail what the
2. MazePos curPos: the current square in the maze being “visited.”
3. char * path: a character array containing the current path. The path is a null-terminated string using n, s, e, and w as directions to move. So, for example, the string "wwnes" represents a string that moves west twice, then north, then east, then south. We recommend PathType enum in path.h to represent the individual characters of the string.
4. int step: a counter telling you how far along the current path you are.

and returns a boolean: true means that the current square being visited by depthFirstSolve is part of the solution, and false means that current square is not part of the solution.

One tricky bit here is figuring out how to update path correctly. Two hints: (i) step tells you how far along in the current path you are; and (ii) if you successfully exit the maze on the nth step, path[n] should be .

It is important that you get the format of the path correct so it is written out properly. Because the search order means that different people may find different solution paths, the way we will grade your code is by generating a solution path, then using the checkPath function to check that it is a valid solution to the maze.

Warning: Don’t be misled by the fact that you only have to write one method. This assignment will probably have the highest ratio of time spent thinking about what code to write to amount of code written of any assignment so far. Recursive code is often quite short — the instructors’ version of depthFirstSolve has about 25 lines of code — but takes a while to get right. Start thinking about your solution now, and don’t be afraid to ask questions on Piazza or in office hours to make sure your logic is right.

Testing your code

Depending on the order you choose to do your recursion (do you decide to look North first, or South first, etc) you can get a different path than someone else if a maze has many paths to the exit! How can you test if your path is correct? You can use the same path checker that we will use to verify if the path you create in HW9 is valid. To do this, you read in the maze and the proposed solution path from input files, and call checkPath to see if it is right. There is commented-out code in hw9.c that shows how to do this.

We have provided several mazes for you. maze1, maze3 and maze4 have valid solutions, while maze2 and maze5 do not.

What do you need to turn in?

Turn in your version of solver.c, with your implementation of depthFirstSolve. You do not need to modify any other files.