# CompSci 18S - Spring 2008 - Solving a Maze (Recursion)

Classwork 13 (10 pts)
April 14, 2008

For group work, please turn in one sheet of paper with all the names of those who participated in your group.

## Problem

We will address solving a maze using a Maze class. The maze is a 2D structure with walls and blank areas (no walls) where you can walk, with a wall all the way around the complete structure. There is a starting position inside the maze and there is a pile of gold that needs to be found.

We will use a 2-D array of Colors to store the maze, here are the instance variables of the class.

// the maze data private Color[][] myMaze; // starting point of the solution private Point myStart; // true if the gold has been found, false otherwise private boolean isSolved;
• Yellow - Gold
• Green - Wall
• Black - blank
• Magenta - Start
• Blue - path , show part of path that has been checked. And in code we will use contants to refer to them. // colors that represent different states of the maze public static final Color WALL = Color.GREEN; public static final Color BLANK = Color.BLACK; public static final Color PATH = Color.BLUE; public static final Color GOLD = Color.YELLOW; public static final Color MARKER = Color.MAGENTA;

## Problem

Assume the maze has already been inialized. Your task is solve the maze using recursion. You will stay on the blank areas and as you check a square on the path, you should change it's color to Blue.

Do not worry about painting the maze. If you change a color in the maze, then it should automatically be painted for you.

public void solve () { isSolved = false; myMaze[myStart.x][myStart.y] = BLANK; solveRecursively(myStart.x, myStart.y); } private void solveRecursively (int row, int col) {

## Coding

You can download 18SMaze from the 18S snarf site. You will need to write the one method solveRecursively in the Maze class, which has been started for you.