Recursive Maze Solver Help Refresh your knowledge of File I/O. Use recursion to
ID: 3878786 • Letter: R
Question
Recursive Maze Solver Help
Refresh your knowledge of File I/O.
Use recursion to find a path through a maze.
Practice throwing and handling exceptions.
Description
This assignment creates a maze that has a leprechaun in search of a pot of gold at the end of a rainbow. Some squares are empty while others are blocked by trees. Your code must find the path between the leprechaun and the pot of gold, without running into any trees or going outside the maze.
I need help implementing the following methods in the MazeSolver class:
loadMaze
main
findPath
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;
public class MazeSolver {
/**
* Exception thrown when path is complete
*/
public static class MazeSolvedException extends Exception {
private static final long serialVersionUID = 1L;
MazeSolvedException() {
super("Found the pot of gold!");
}
}
/**
* Stores the user interface
*/
private static UserInterface gui;
/**
* Data structures for maze
*/
private static char[][] maze;
/**
* This is the starting point for your program.
* This method calls the loadMaze method to read the maze file. <p>
* <ol>
* <li> Implement the {@link MazeSolver#loadMaze(String)} method first,
* if correctly implemented the user interface should display it correctly.
* <li> After the <b>//YOUR CODE HERE! comment</b> write code to find the row and column of the leprechaun,
* which is then used for the initial call to {@link MazeSolver#findPath(int, int)}.
* <li> Since code has been provided to CALL the method {@link MazeSolver#findPath(int, int)},
* no other code in the main method is needed.
* </ol>
* @param args set run configurations to either choose or change the maze you are using
* @throws FileNotFoundException exception thrown when program unable to recognize file name
*/
public static void main(String[] args) throws FileNotFoundException {
// Load maze from file
loadMaze(args[0]);
// Find leprechaun in maze
int currentRow = -1;
int currentCol = -1;
// YOUR CODE HERE!
// Instantiate graphical user interface
gui = new UserInterface(maze);
try {
// Solve maze, using recursion
findPath(currentRow, currentCol);
// Impossible maze, notify user interface
gui.sendStatus(CallbackInterface.SearchStatus.PATH_IMPOSSIBLE, -1, -1); // Cannot solve
} catch (MazeSolvedException e) {
// Maze solved, exit normally
}
}
/**
* Reads a maze file into the 2-dimensional array declared as a class variable.
*
* @param filename the name of the maze file.
* @throws FileNotFoundException exception thrown when program unable to recognize file name
*/
static void loadMaze(String filename) throws FileNotFoundException {
}
/**
* This method calls itself recursively to find a path from the leprechaun to the pot of gold. <p>
* It also notifies the user interface about the path it is searching. <p>
* Here is a list of the actions taken in findPath, based on the square it is searching:
* <p>
* <ul>
* <li> If the row or column is not on the board, notify the user interface calling
* sendStatus with PATH_ILLEGAL, and return false.
* <li> If maze[row][col] == 'G', then you have found a path to the pot of gold, notify the user
* interface by calling sendStatus with PATH_COMPLETE and throw the MazeSolvedException to terminate execution.
* <li> If maze[row][col] == 'S', then the current square is already part of a valid path,
* do not notify the user interface, just return false.
* <li> If maze[row][col] == 'W', then the current square is already part of an invalid path,
* not notify the user interface, just return false.
* <li> If maze[row][col] == '#', then the current square contains a blocking tree,
* do not notify the user interface, just return false.
* <li> If current square contains a space or 'L', notify the user interface by calling sendStatus with PATH_VALID,
* then recursively call findPath with the row and column of the surrounding squares,
* in order: UP, RIGHT, DOWN, and LEFT.
* <li> If any of the recursive calls return true, return true from the current invocation of findPath,
* otherwise notify the user interface by calling sendStatus with PATH_INVALID, and return false.
* </ul>
*
* @param row the current row of the leprechaun
* @param col the current column of the leprechaun
* @return true for a valid path, false otherwise
* @throws MazeSolvedException exception thrown when maze is complete
*/
public static boolean findPath(int row, int col) throws MazeSolvedException {
// YOUR CODE HERE!
return false;
}
}
Explanation / Answer
MazeSolver.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class MazeSolver {
/**
* Exception thrown when path is complete
*/
public static class MazeSolvedException extends Exception {
private static final long serialVersionUID = 1L;
MazeSolvedException() {
super("Found the pot of gold!");
}
}
/**
* Stores the user interface
*/
private static UserInterface gui;
/**
* Data structures for maze
*/
private static char[][] maze;
/**
* This is the starting point for your program.
* This method calls the loadMaze method to read the maze file. <p>
* <ol>
* <li> Implement the {@link MazeSolver#loadMaze(String)} method first,
* if correctly implemented the user interface should display it correctly.
* <li> After the <b>//YOUR CODE HERE! comment</b> write code to find the row and column of the leprechaun,
* which is then used for the initial call to {@link MazeSolver#findPath(int, int)}.
* <li> Since code has been provided to CALL the method {@link MazeSolver#findPath(int, int)},
* no other code in the main method is needed.
* </ol>
* @param args set run configurations to either choose or change the maze you are using
* @throws FileNotFoundException exception thrown when program unable to recognize file name
*/
public static void main(String[] args) throws FileNotFoundException {
// Load maze from file
loadMaze(args[0]);
// Find leprechaun in maze
int currentRow = -1;
int currentCol = -1;
// YOUR CODE HERE!
// Instantiate graphical user interface
gui = new UserInterface(maze);
try {
// Solve maze, using recursion
findPath(currentRow, currentCol);
// Impossible maze, notify user interface
gui.sendStatus(CallbackInterface.SearchStatus.PATH_IMPOSSIBLE, -1, -1); // Cannot solve
} catch (MazeSolvedException e) {
// Maze solved, exit normally
}
}
/**
* Reads a maze file into the 2-dimensional array declared as a class variable.
*
* @param filename the name of the maze file.
* @throws FileNotFoundException exception thrown when program unable to recognize file name
*/
static void loadMaze(String filename) throws FileNotFoundException {
// YOUR CODE HERE!
File f = new File(filename);
Scanner scan;
String line;
int height;
int length;
try {
scan = new Scanner((f));
length = scan.nextInt();
height = scan.nextInt();
maze = new char[height][length];
scan.nextLine();
while (scan.hasNext()) {
for(int y = 0; y < height; y++) {
line = scan.nextLine();
for(int x = 0; x < length; x++) {
maze[y][x] = line.charAt(x);
}
}
}
scan.close();
} catch(Exception e) {
e.printStackTrace();
}
}
/**
* This method calls itself recursively to find a path from the leprechaun to the pot of gold. <p>
* It also notifies the user interface about the path it is searching. <p>
* Here is a list of the actions taken in findPath, based on the square it is searching:
* <p>
* <ul>
* <li> If the row or column is not on the board, notify the user interface calling
* sendStatus with PATH_ILLEGAL, and return false.
* <li> If maze[row][col] == 'G', then you have found a path to the pot of gold, notify the user
* interface by calling sendStatus with PATH_COMPLETE and throw the MazeSolvedException to terminate execution.
* <li> If maze[row][col] == 'S', then the current square is already part of a valid path,
* do not notify the user interface, just return false.
* <li> If maze[row][col] == 'W', then the current square is already part of an invalid path,
* not notify the user interface, just return false.
* <li> If maze[row][col] == '#', then the current square contains a blocking tree,
* do not notify the user interface, just return false.
* <li> If current square contains a space or 'L', notify the user interface by calling sendStatus with PATH_VALID,
* then recursively call findPath with the row and column of the surrounding squares,
* in order: UP, RIGHT, DOWN, and LEFT.
* <li> If any of the recursive calls return true, return true from the current invocation of findPath,
* otherwise notify the user interface by calling sendStatus with PATH_INVALID, and return false.
* </ul>
*
* @param row the current row of the leprechaun
* @param col the current column of the leprechaun
* @return true for a valid path, false otherwise
* @throws MazeSolvedException exception thrown when maze is complete
*/
public static boolean findPath(int row, int col) throws MazeSolvedException {
// YOUR CODE HERE!
for(int y = 0; y < maze.length; y++) {
for(int x = 0; x < maze[0].length; x++) {
if(maze[y][x] == 'L') {
row = y;
col = x;
}
}
}
if(row < 0 || row > maze.length || col < 0 || col > maze[0].length){
gui.sendStatus(CallbackInterface.SearchStatus.PATH_ILLEGAL, row, col);
return false;
}
if(maze[row][col] == 'G'){
gui.sendStatus(CallbackInterface.SearchStatus.PATH_COMPLETE, row, col);
throw new MazeSolvedException();
}
if(maze[row][col] == 'S'){
return false;
}
if(maze[row][col] == 'W'){
return false;
}
if(maze[row][col] == '#'){
return false;
}
if(maze[row][col] == 'L' || maze[row][col] == ' '){
gui.sendStatus(CallbackInterface.SearchStatus.PATH_VALID, row, col);
findPath(row, col - 1);
if (findPath(row, col - 1) == true) {
findPath(row, col - 1);
}
findPath(row + 1, col);
if (findPath(row + 1, col) == true) {
findPath(row + 1, col);
}
findPath(row, col + 1);
findPath(row - 1, col);
if(findPath(row,col) == true) {
return true;
} else {
gui.sendStatus(CallbackInterface.SearchStatus.PATH_INVALID, row, col);
return false;
}
}
return false;
}
}
UserInterface.java
import java.awt.Color;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.GridLayout;
import java.awt.Image;
import java.awt.Insets;
import java.util.ArrayList;
import java.util.Random;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.SwingConstants;
import javax.swing.UIManager;
import javax.swing.border.Border;
import javax.swing.border.LineBorder;
public class UserInterface implements CallbackInterface {
// Maze variables
public char maze[][];
private int leprechaunRow;
private int leprechaunCol;
// User interface
private JFrame frame;
private JPanel panel;
private JPanel mazePanel;
private Image leprechaun, potofgold, success, shamrock, wrongway;
private Image treeone, treetwo, treethree, treefour;
private ArrayList<JButton> buttons;
// Main program
public UserInterface(char[][] maze) {
// Store maze data
this.maze = maze;
// Store initial position of leprechaun
for (int row = 0; row < maze.length; row++) {
for (int col = 0; col < maze[0].length; col++) {
if (maze[row][col] == 'L') {
leprechaunRow = row;
leprechaunCol = col;
}
}
}
// Setup graphics
setupGraphics();
}
// Process status
public void sendStatus(SearchStatus eStatus, int row, int col) {
System.err.println("Solver reported " + eStatus + " at row " + row + ", column " + col);
// Update squares, based on status
if (eStatus == SearchStatus.PATH_INVALID) {
maze[row][col] = 'W';
} else if (eStatus == SearchStatus.PATH_VALID) {
maze[row][col] = 'S';
} else if (eStatus == SearchStatus.PATH_COMPLETE) {
maze[row][col] = 'C';
}
// Update board, if necessary
if (eStatus != SearchStatus.PATH_ILLEGAL) {
updateBoard();
}
// Display success dialog, and exit
if (eStatus == SearchStatus.PATH_COMPLETE) {
ImageIcon icon = new ImageIcon("images/Success.jpg");
Image image = icon.getImage().getScaledInstance(200, 200, Image.SCALE_SMOOTH);
icon = new ImageIcon(image);
JOptionPane.showMessageDialog(frame, "Congratulations, you found the pot of gold!",
"Maze Success", JOptionPane.WARNING_MESSAGE, icon);
// Exit application
frame.dispose();
}
// Display failure dialog, and exit
else if (eStatus == SearchStatus.PATH_IMPOSSIBLE) {
ImageIcon icon = new ImageIcon("images/Failure.jpg");
Image image = icon.getImage().getScaledInstance(200, 200, Image.SCALE_SMOOTH);
icon = new ImageIcon(image);
JOptionPane.showMessageDialog(frame, "Sorry, you cannot find the pot of gold!",
"Maze Failure", JOptionPane.WARNING_MESSAGE, icon);
// Exit application
frame.dispose();
}
}
// Update board
private void updateBoard() {
// Seed random generator
Random random = new Random(12345678);
for (int row = 0; row < maze.length; row++) {
for (int col = 0; col < maze[0].length; col++) {
int index = (row * maze[0].length) + col;
// Update button
JButton button = buttons.get(index);
if (leprechaunRow == row && leprechaunCol == col) {
button.setIcon(new ImageIcon(leprechaun));
} else if (maze[row][col] == 'G') {
button.setIcon(new ImageIcon(potofgold));
} else if (maze[row][col] == 'S') {
button.setIcon(new ImageIcon(shamrock));
} else if (maze[row][col] == 'W') {
button.setIcon(new ImageIcon(wrongway));
} else if (maze[row][col] == 'C') {
button.setIcon(new ImageIcon(success));
} else if (maze[row][col] == '#') {
switch (random.nextInt(4)) {
case 0: button.setIcon(new ImageIcon(treeone)); break;
case 1: button.setIcon(new ImageIcon(treetwo)); break;
case 2: button.setIcon(new ImageIcon(treethree)); break;
case 3: button.setIcon(new ImageIcon(treefour)); break;
}
} else {
button.setIcon(null);
}
}
}
// Make leprechaun slow down!
sleep(250);
}
// Setup graphics
private void setupGraphics() {
// Look and feel
try {
UIManager.setLookAndFeel(UIManager.getCrossPlatformLookAndFeelClassName());
} catch (Exception e) {
e.printStackTrace();
}
mazePanel = new JPanel();
mazePanel.setLayout(new GridLayout(maze.length, maze[0].length, 0, 0));
// Add row and column labels
panel = new JPanel();
panel.setLayout(new GridBagLayout());
GridBagConstraints gbc = new GridBagConstraints();
gbc.gridx = 0;
gbc.gridy = 1;
gbc.gridwidth = 1;
gbc.gridheight = 1;
gbc.weightx = 0.0;
gbc.weighty = 0.0;
gbc.fill = GridBagConstraints.BOTH;
gbc.anchor = GridBagConstraints.WEST;
gbc.insets = new Insets(0, 2 * 5, 0, 2 * 5);
panel.add(createRowLabels(), gbc);
gbc.gridx = 2;
gbc.gridy = 1;
gbc.anchor = GridBagConstraints.EAST;
panel.add(createRowLabels(), gbc);
gbc.gridx = 1;
gbc.gridy = 0;
gbc.anchor = GridBagConstraints.SOUTH;
gbc.insets = new Insets(5, 0, 5, 0);
panel.add(createColLabels(), gbc);
gbc.gridx = 1;
gbc.gridy = 2;
gbc.anchor = GridBagConstraints.NORTH;
panel.add(createColLabels(), gbc);
gbc.gridx = 1;
gbc.gridy = 1;
gbc.anchor = GridBagConstraints.CENTER;
gbc.insets = new Insets(0, 0, 0, 0);
panel.add(mazePanel, gbc);
// Load and scale images
ImageIcon icon;
icon = new ImageIcon("resources/images/Leprechaun.jpg");
leprechaun = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/PotOfGold.jpg");
potofgold = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/Shamrock.jpg");
shamrock = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/WrongWay.jpg");
wrongway = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/Success.jpg");
success = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/TreeOne.jpg");
treeone = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/TreeTwo.jpg");
treetwo = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/TreeThree.jpg");
treethree = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
icon = new ImageIcon("resources/images/TreeFour.jpg");
treefour = icon.getImage().getScaledInstance(80, 80, Image.SCALE_SMOOTH);
// Build panel of buttons
buttons = new ArrayList<JButton>();
for (int row = 0; row < maze.length; row++) {
for (int col = 0; col < maze[0].length; col++) {
// Initialize and add button
JButton button = new JButton();
Border border = new LineBorder(Color.darkGray, 4);
button.setOpaque(true);
button.setBackground(Color.gray);
button.setBorder(border);
mazePanel.add(button);
buttons.add(button);
}
}
// Initial update
updateBoard();
// Configure and show window
frame = new JFrame();
frame.getContentPane().add(panel);
frame.pack();
frame.setTitle("Maze");
frame.setSize(maze[0].length * 80 + 150, maze.length * 80 + 150);
frame.setResizable(false);
frame.setLocationRelativeTo(null);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setAlwaysOnTop(true);
frame.setFocusable(true);
frame.setVisible(true);
frame.setVisible(true);
}
// Create row labels
private JPanel createRowLabels() {
JPanel filePanel = new JPanel(new GridLayout(0, 1));
for (int row = 0; row < maze.length; row++) {
filePanel.add(new JLabel(String.valueOf(row), SwingConstants.CENTER));
}
return filePanel;
}
// Create column labels
private JPanel createColLabels() {
JPanel filePanel = new JPanel(new GridLayout(1, 0));
for (int col = 0; col < maze[0].length; col++) {
filePanel.add(new JLabel(String.valueOf(col), SwingConstants.CENTER));
}
return filePanel;
}
// Wait for awhile
private static void sleep(int milliseconds) {
try {
Thread.sleep(milliseconds);
} catch (InterruptedException ex) {
Thread.currentThread().interrupt();
}
}
}
CallbackInterface.java
public interface CallbackInterface {
/**
* Status of search.
* * PATH_VALID: Valid path
* * PATH_INVALID: Invalid path (cannot move)
* * PATH_COMPLETE: Path complete (found gold)
* * PATH_ILLEGAL: Illegal path (out of bounds)
* * PATH_IMPOSSIBLE: No path (cannot solve)
*/
public enum SearchStatus {
PATH_VALID, // Valid path
PATH_INVALID, // Invalid path (cannot move)
PATH_COMPLETE, // Path complete (found gold)
PATH_ILLEGAL, // Illegal path (out of bounds)
PATH_IMPOSSIBLE // No path (cannot solve)
}
/**
* Callback method invoked for each recursive call
* @param eStatus the current status of the maze
* @param row the current row of the leprechaun
* @param col the current column of the leprechaun
*/
public void sendStatus(SearchStatus eStatus, int row, int col);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.