import java.util.ArrayList; import java.util.Scanner; import java.util.Random; import java.io.*; @SuppressWarnings("unchecked") public class A5Q2Template { // A global variable for the BEST solution public static ArrayList bestSolution = null; // A global Random object for choosing a random direction static Random rnd = new Random(); //---------- main method ----------------------- public static void main(String[] args) throws Exception { /* Reads in a maze from the file TestMaze.txt. The first line * must contain n - the size of the maze (which must be square). * Then there must be n lines of n characters each, where X is * a valid place to go, and any other character is a "wall". * The starting point is always (0,0) and the goal point is * always (n-1,n-1). */ boolean[][] theMaze; Scanner inputFile = new Scanner(new File("TestMaze.txt")); int n = Integer.parseInt(inputFile.nextLine()); theMaze = new boolean[n][n]; for(int row=0; row(), start, goal, theMaze); if(bestSolution==null) System.out.println("You can't get there from here."); else{ System.out.println("The path of size "+bestSolution.size()+" is: "+bestSolution); displayProgress(bestSolution, start, goal, theMaze); } }//main //---------- a global variable to define the ways you can move --------- //The four directions that you can try to move in the maze private static Coord[] directions = {new Coord(-1,0), new Coord(1,0), new Coord(0,-1), new Coord(0,1)}; private static int numDir = 4; //------------ the maze solver --------------------------- public static void solve(ArrayList path, Coord currentSpot, Coord goal, boolean[][] maze){ /* Attempts to solve the given maze by getting to a goal spot, * from a currentSpot, which has been reached by the given path. * It will set the global variable bestSolution to the shortest solution * ever found. It will return nothing. */ //Make a copy of the path, because... ArrayList newPath = (ArrayList)(path.clone()); newPath.add(currentSpot); //...you shouldn't touch the original parameter! displayProgress(path,currentSpot,goal,maze); //Draws the graphics if(currentSpot.equals(goal)){ // We have found a solution. // If this is the first solution found, or it is shorter than // the previous solution, update the global parm bestSolution // Else, redraw the graphics to show the backtracking. } else { // add/modify code here to choose a random starting direction for(int i=0; i path, Coord currentSpot, Coord goal, boolean[][] maze){ int nRows = maze.length; int nCols = maze[0].length; double rowStep = 1.0Rows; double colStep = 1.0Cols; StdDraw.show(0); StdDraw.clear(); StdDraw.rectangle(0.5,0.5,0.5,0.5); for(int row=0; row=maze.length || col=maze[0].length) return false; //It's "off the edge" in some direction else return maze[row][col]; }//validSpot public String toString(){ return "("+row+","+col+")"; } }//Coord class 

StdDraw can be found at

http://introcs.cs.princeton.edu/java/stdlib/StdDraw.jav

TestMaze:

11 XX.XXXXXX.X .X.X.X..XXX XXXX.XX.X.X X..XXX...XX XXX.XX.XXX. X.X.XX...XX X.X..XXX..X .XXXX..XXXX XX.X..X.X.. .X.XXX..XXX XX.X.X.XX.X