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 Depth-First Search algorithm
• have implemented both a recursive and an iterative Depth-First Search maze solver

Depth-First Search

Depth-First 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 “Depth-First” 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 depth-first 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, a y value, and a Point parent node
• Points also have an equals method that compares two points based on their x and y values
• A Maze is primarily composed of multiple 2D arrays
  • north[][], west[][], east[][], and south[][] keep track of if there is a wall to the North, West, East, or South of coordinates x, y (i.e. if north[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 1-indexed.

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)

Recursive Depth-First Search

Now that we have some helper methods, we’re ready to write our first DFS! It is easier to write a Depth-First 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, call selectPoint(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 the Maze 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.

Iterative Depth-First 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, call selectPoint(point).
• The DRAW_WAIT field at the top of the Maze 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.

Checking the Results 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. Sometimes, we will ask you to think about questions that you’ll review with the person who checks you off. For this lab, please answer the following questions: