JAVA FILE 1

import java.util.*;

import java.io.*;

/**

* Maze represents a maze of characters. The goal is to get from the

* top left corner to the bottom right, following a path of 1's. Arbitrary

* constants are used to represent locations in the maze that have been TRIED

* and that are part of the solution PATH.

*

* @author Lewis and Chase

* @version 4.0

*/

public class Maze

{

private static final int TRIED = 2;

private static final int PATH = 3;

private int numberRows, numberColumns;

private int[][] grid;

/**

* Constructor for the Maze class. Loads a maze from the given file.

* Throws a FileNotFoundException if the given file is not found.

*

* @param filename the name of the file to load

* @throws FileNotFoundException if the given file is not found

*/

public Maze(String filename) throws FileNotFoundException

{

Scanner scan = new Scanner(new File(filename));

numberRows = scan.nextInt();

numberColumns = scan.nextInt();

grid = new int[numberRows][numberColumns];

for (int i = 0; i

for (int j = 0; j

grid[i][j] = scan.nextInt();

}

/**

* Marks the specified position in the maze as TRIED

*

* @param row the index of the row to try

* @param col the index of the column to try

*/

public void tryPosition(int row, int col)

{

grid[row][col] = TRIED;

}

/**

* Return the number of rows in this maze

*

* @return the number of rows in this maze

*/

public int getRows()

{

return grid.length;

}

/**

* Return the number of columns in this maze

*

* @return the number of columns in this maze

*/

public int getColumns()

{

return grid[0].length;

}

/**

* Marks a given position in the maze as part of the PATH

*

* @param row the index of the row to mark as part of the PATH

* @param col the index of the column to mark as part of the PATH

*/

public void markPath(int row, int col)

{

grid[row][col] = PATH;

}

/**

* Determines if a specific location is valid. A valid location

* is one that is on the grid, is not blocked, and has not been TRIED.

*

* @param row the row to be checked

* @param column the column to be checked

* @return true if the location is valid

*/

public boolean validPosition(int row, int column)

{

boolean result = false;

// check if cell is in the bounds of the matrix

if (row >= 0 && row

column >= 0 && column

// check if cell is not blocked and not previously tried

if (grid[row][column] == 1)

result = true;

return result;

}

/**

* Returns the maze as a string.

*

* @return a string representation of the maze

*/

public String toString()

{

String result = " ";

for (int row=0; row

{

for (int column=0; column

result += grid[row][column] + "";

result += " ";

}

return result;

}

}

JAVA FILE 2

import java.util.*;

/**

* MazeSolver attempts to recursively traverse a Maze. The goal is to get from the

* given starting position to the bottom right, following a path of 1's. Arbitrary

* constants are used to represent locations in the maze that have been TRIED

* and that are part of the solution PATH.

*

* @author Lewis and Chase

* @version 4.0

*/

public class MazeSolver

{

private Maze maze;

/**

* Constructor for the MazeSolver class.

*/

public MazeSolver(Maze maze)

{

this.maze = maze;

}

/**

* Attempts to recursively traverse the maze. Inserts special

* characters indicating locations that have been TRIED and that

* eventually become part of the solution PATH.

*

* @param row row index of current location

* @param column column index of current location

* @return true if the maze has been solved

*/

public boolean traverse()

{

boolean done = false;

int row, column;

Position pos = new Position();

Deque stack = new LinkedList();

stack.push(pos);

while (!(done) && !stack.isEmpty())

{

pos = stack.pop();

maze.tryPosition(pos.getx(),pos.gety()); // this cell has been tried

if (pos.getx() == maze.getRows()-1 && pos.gety() == maze.getColumns()-1)

done = true; // the maze is solved

else

{

push_new_pos(pos.getx() - 1,pos.gety(), stack);

push_new_pos(pos.getx() + 1,pos.gety(), stack);

push_new_pos(pos.getx(),pos.gety() - 1, stack);

push_new_pos(pos.getx(),pos.gety() + 1, stack);

}

}

return done;

}

/**

* Push a new attempted move onto the stack

* @param x represents x coordinate

* @param y represents y coordinate

* @param stack the working stack of moves within the grid

* @return stack of moves within the grid

*/

private void push_new_pos(int x, int y,

Deque stack)

{

Position npos = new Position();

npos.setx(x);

npos.sety(y);

if (maze.validPosition(x,y))

stack.push(npos);

}

}

JAVA FILE 3

import java.util.*;

import java.io.*;

/**

* MazeTester uses recursion to determine if a maze can be traversed.

*

* @author Lewis and Chase

* @version 4.0

*/

public class MazeTester

{

/**

* Creates a new maze, prints its original form, attempts to

* solve it, and prints out its final form.

*/

public static void main(String[] args) throws FileNotFoundException

{

Scanner scan = new Scanner(System.in);

System.out.print("Enter the name of the file containing the maze: ");

String filename = scan.nextLine();

Maze labyrinth = new Maze(filename);

System.out.println(labyrinth);

MazeSolver solver = new MazeSolver(labyrinth);

if (solver.traverse())

System.out.println("The maze was successfully traversed!");

else

System.out.println("There is no possible path.");

System.out.println(labyrinth);

}

}

JAVA FILE 4

/**

* @author Lewis and Chase

*

* Solution to Programming Project 4.6.

*/

public class Position

{

private int x;

private int y;

/**

* Constructs a position and sets the x & y coordinates to 0,0.

*/

Position ()

{

x = 0;

y = 0;

}

/**

* Returns the x-coordinate value of this position.

* @return int the x-coordinate of this position

*/

public int getx()

{

return x;

}

/**

* Returns the y-coordinate value of this position.

* @return int the y-coordinate of this position

*/

public int gety()

{

return y;

}

/**

* Sets the value of the current position's x-coordinate.

* @param a value of x-coordinate

*/

public void setx(int a)

{

x = a;

}

/**

* Sets the value of the current position's x-coordinate.

* @param a value of y-coordinate

*/

public void sety(int a)

{

y = a;

}

}

TEST FILE .txt

21 35

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1

For this assignment, you will extend the provided implementation of a stack based maze solver. This program loads a maze from a local text file and then checks if there is a path from position 0,0 to the bottom-right most position. Attached to this assignment are the four source files that implement this algorithm they are complete and ready to be run: Maze java Loads and stores a maze from a text file, then provides a several methods to manipulate the contents of the maze. MazeSolverjava Processes a Maze object (see above) to produce a boolean indicating if that maze is solvable or not. Maze Tester java The driver for the complete algorithm; loads a Maze and then runs MazeSolver on This class represents a 2D point in the maze (a x/y pair) Position java Also provided are three sample input mazes. Try them! testfile txt solvable small maze. o test file2.txt solvable large maze. testfile3.txt unsolvable large maze. For this assignment, you will extend the provided implementation of a stack based maze solver. This program loads a maze from a local text file and then checks if there is a path from position 0,0 to the bottom-right most position. Attached to this assignment are the four source files that implement this algorithm they are complete and ready to be run: Maze java Loads and stores a maze from a text file, then provides a several methods to manipulate the contents of the maze. MazeSolverjava Processes a Maze object (see above) to produce a boolean indicating if that maze is solvable or not. Maze Tester java The driver for the complete algorithm; loads a Maze and then runs MazeSolver on This class represents a 2D point in the maze (a x/y pair) Position java Also provided are three sample input mazes. Try them! testfile txt solvable small maze. o test file2.txt solvable large maze. testfile3.txt unsolvable large maze