Setup
Register for the lab using grinch
: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.
Goals and Outcomes
By the end of this lab, you will…
 have more experience working with trees and recursion
 understand the DepthFirst Search algorithm
 have implemented both a recursive and an iterative DepthFirst Search maze solver
DepthFirst Search
DepthFirst Search (DFS) is a powerful algorithm for traversing (or searching) through tree or graph data structures. Essentially, the idea of the algorithm is this:
 Begin at the root node of the tree (or any point on a graph)
 Explore each path as “deep” as you can before backtracking and exploring a different path
 In a tree, this means keep following consecutive branches until you reach a leaf before backtracking
This search is “DepthFirst” because it travels as deep as it can into the graph before it backtracks at all; you keep exploring deeper into the graph until you can`t explore any deeper. For example, in a depthfirst search on a binary tree, all children of the left of a node should get explored before any children of the right of the node (or vise versa).
In this lab we will be implementing both a recursive and an iterative DFS to solve mazes!
Maze Interface
Mazes can be seen as generalized trees; each point in the maze represents a node in the tree, and each “child” point that you can move to from that point represents the branches from that node.
A leaf node, then, is a point that has no free spaces around it other than its parent point.
In this lab, we will be working with a simple maze and point interface and implementing DFS solvers to complete mazes.
You can find the full implementations in Maze.java
and Point.java
, but here`s what you really need to know:
 Each Point node has a
x
value, ay
value, and aPoint
parent
node 
Point
s also have anequals
method that compares two points based on theirx
andy
values  A Maze is primarily composed of multiple 2D arrays

north[][]
,west[][]
,east[][]
, andsouth[][]
keep track of if there is a wall to the North, West, East, or South of coordinates x, y (i.e. ifnorth[4][3]
is false, you can move North from(4, 3)
to(4, 4)
)  Mazes also have a boolean done that can be used to track if the end of the maze has been found, as well as a Point end that represents the end of the maze

 The maze starts at the bottom left
(1, 1)
, and ends at the center. All point coordinates are 1indexed.
getChildren Helper Method
Let’s start by writing a helper method that interacts directly with the maze interface.
It would be very convenient to have a method that returns an array of all of the children of a given Point
(i.e. all of the points that we can move to from a given point).
public static Point[] getChildren(Point point)
Returns a Point
array containing all children of a given point.
You will need to interact with the north[][]
, east[][]
, south[][]
, and west[][]
arrays to decide where you can move from the given point.
Also, make sure to set each new point’s parent to the current point!
Task 0.
Implement getChildren
in Maze.java
.
Recursive DepthFirst Search
Now that we have some helper methods, we’re ready to write our first DFS! It is easier to write a DepthFirst Search recursively, so we will start with that. Before we get started, here’s a few things you should know:
 When you want to “move” to a Point
point
, callselectPoint(point)
. This will draw the new point on the maze as well as log the move made.  The
DRAW_WAIT
field at the top of theMaze
class controls how long to wait between drawing selected points. Changing this field to be larger slows down the solver, and may make it easier to see what is going wrong while debugging (although you’ll want to decrease it again when you are ready to run through all of the tests).  You should use your
getChildren()
method to find where you can move from a given point  Your solution must be recursive! Think about how recursion relates to the structure of the maze (or any tree, for that matter)
 Make sure to call
selectPoint(point)
when you want to select a point. You must select the starting point(1, 1)
. 
Do not call
selectPoint()
when backtracking. You do not need to do anything when backtracking other than select the next point to move to.  Remember to stop the search when you reach the target Point
end
and update thedone
field to reflect that you’ve found it.
Task 1.
Implement solveDFSRecursive
in Maze.java
.
Iterative DepthFirst Search
It is also possible to implement the DFS algorithm iteratively! The stack data structure fits perfectly for this task; we can iteratively implement DFS by continuously pushing all children of the current node on to the stack, then popping off the top of the stack to be the new current node. Because the next level of children gets pushed on top of the other children from the previous level, we explore deeper and deeper into the tree before we backtrack to other children! Here are a few quick notes:
 Just like before, when you want to “move” to a
Point point
, callselectPoint(point)
.  The
DRAW_WAIT
field at the top of theMaze
class can still be increased or decreased to change the speed of the solver  You may find your
getChildren
method helpful to use, but you are not required to do so  Your solution must be iterative. Using a stack will make this much easier!
 Make sure to call
selectPoint(point)
when you want to select a point. You must select the starting point(1, 1)
. 
Do not call
selectPoint()
when backtracking. You do not need to do anything when backtracking other than select the next point to move to.  Remember to stop the search when you reach the target Point
end
and update thedone
field to reflect that you’ve found it.
Task 2.
Implement solveDFSIterative
in Maze.java
.
Checking the Results on gitlab
Task 3. Check to make sure you are passing all the tests on gitlab.
Getting Checked Off
At the end of every lab, you will need to call over a member of course staff to review your work. For you to receive credit for the lab, a staff member must check you off!