Multicore Initiative

Solutions

reu:cs180_recursion_lab

CS180 Recursion Lab Assignment

Lab Overview

Write a recursive program that solves a random maze that our Maze class generates (you will not be given the source code for the Maze class, only an object file from which you can execute it). The maze is nothing but a 2-D character array, in which you cannot step on some cells, while you can step on others. This randomly generated maze is assured to have a solution. Your solution should consists of a sequence of moves, that the robot can execute, e.g. DOWN/TOP/LEFT/RIGHT. You will store your moves in a vector, instead of storing DOWN as a whole you may store just D, same goes for TOP as T, LEFT as L and RIGHT as R. You will then call a boolean method called verifyPath(Vector path) from the Maze class to verify if your solution is correct. If the method returns true then you can go and program your robot to trace this path out. The robot programming has to be done without hardcoding the moves!

Example

Possible Solution

This is a randomly generated maze (in which you cannot step on '#'s), that has many solutions from 'S' to 'E'. One solution is DDDDRDDDRRRDRRRRDR (from S to E) and there exist many more. As long as you can find a solution to get from 'S' to 'E' and can display as given above then you are good.

Robot Solution Execution Synopsis

The robot should trace out the solution path that you get by solving the maze. As in the case of the above example, the solution path is DDDDRDDDRRRDRRRRDR. The most important thing when making the robot trace the path is visualizing it's orientation as if it was in the maze (as NORTH/SOUTH/EAST/WEST). If your robot is facing the north direction of the maze then maze's right turn is the same as robot's right turn but if your robot is facing the south direction of the maze then maze's right turn is robot's left turn. The robot for instance in the above example is initially facing the north direction of maze, first it turns by 180 degrees to position itself in the south direction and then goes straight 4 times, it then turns LEFT(or 90 degrees anti-clockwise) and goes straight once, remember that it is now in the EAST direction, it then takes right turn (90 degrees clockwise) to get into south direction and then goes straight 3 times, it then turns left(90 degrees anti-clockwise) and goes straight 3 times, it then turns 90 degrees clockwise to position itself south and goes straight once and again turns left(90 degrees anti-clockwise) to position itself in the EAST and goes straight 4 times before it again turns 90 degrees clockwise to position itself south and goes straight once and finally turns left (or 90 degrees anti-clockwise) and goes straight once to reach the end point. You will have to keep a track of direction that robot is virtually facing as if it was in the maze and accordingly you would make turns that come out from your solution path.

Skeleton Code

import java.util.Vector;

/**
*
* @author Zeeshan Siddiqui
*
* Lab 14 and the final one for Spring 2009
*
* char[][] getMaze() This returns the maze generated in a 2-D array format
* boolean isLegalMove(int x,int y) This returns true if the cell you are stepping is legal or not
* boolean verifyPath(Vector<String> pathList> This returns true if your solution path is correct and solves the maze
*
*/

public class Main {

Vector<String> directions; //You will store your directions in this vector (directions are sequence of D/T/L/R)
Maze maze = new Maze(10,10);// Arguments are Width, Height of the maze; ARBITRARY, AS LONG AS THE MAZE IS EXTREME IN SIZE
char[][] MAZE = maze.getMaze(); //Maze in the form of a 2-D Character Array

/**
* @param args the command line arguments
*
*/

//Call this method to print the randomly generated maze
void printMaze(){
maze.printMaze();
}

//Used to check if your path is correct. Use it!
boolean verifyPath(Vector<String> pathList){
return maze.verifyPath(pathList);
}

/**Your methods to solve the maze, get the solution path as a sequence of D/T/L/R stored in directions**/