Code needs to be changed to pass test cases provided.

Students will apply concepts of advanced Backtracking. Your solution for each test case must run within 0.31 seconds. Otherwise, no credit will be given for that test case!!!!

Assignment Description: Kenny is with his friends at the county fair. They got tickets to enter in the magical corn maze. The maze consists of teleportation pads, that allow you jump through various spots in the maze. Kenny is really scared to go in, but his friends promise they will always be together in the corn maze. Unfortunately, they got separated and now Kenny is alone in the corn maze. Kenny is freaking out until he gets a text from his friend that they are waiting for him to get to the end. They promise to guide Kenny to the end. However, his phone has a low battery, so he must hurry (or else he is trap there). Kenny’s friends remind him that there are some magical teleportation pads within the maze that will help him get out fast before his phone battery dies. However, there are some that can send Kenny to dead ends. Your goal is to get Kenny out of the magical maze before his phone dies (hence the running time constraint restriction). The Maze Files and Understanding the Maze Itself: You are provided a total of 5 text files. Inside each text file is a maze. Here is a sample below. • The number of rows and columns are all different in each text file, please do not assume they are the same. However, I can assure you that the time limit will remain the same for the grading. Meaning, the biggest maze provided will be the same size for when the graders test your code.

• The ‘*’ represents a valid space that Kenny can walk on.

• The ‘@’ represents an invalid space that Kenny cannot walk on. Think of it as an obstacle.

• The ‘X’ represents the exit square. This is basically the destination that Kenny needs to get to be out of the magical maze.

• Kenny can only walk in 4 directions. Up, down, left, and right. Diagonal moves are not allowed.

• The digits such as ‘1’, ‘2’, ‘3’, etc… represent magical squares. These squares will teleport you to other matching digit in the maze. For example, the ‘1’ in the above figure, if walked on, will transport you to the other ‘1’. It will NOT transport you to the different digit spots.

• Kenny will always start at the bottom left corner of the maze. That is the entry point technically.

Implementation Details for this Assignment:

1. You are going to create a Class called MagicMaze.

2. The MagicMaze Class must have the following attributes:

a. 2D primitive char array that will store the entire input maze from the provided text file.

b. A String object that stores the maze number (maze1, maze2, etc…)

c. 2 primitive integers that each hold the number of rows and columns in the 2D maze

d. You are welcome to add additional attributes that feel may be necessary.

3. The MagicMaze Class has one overloaded constructor with three parameters.

a. A String Object that represents the name of the maze text file

b. A primitive int that represents the number of rows.

c. A primitive int that represents the number of columns.

4. The MagicMaze Class must have some method that will perform scanning the maze from the provided text file into the respective class attribute. This is like Programming Assignment 1 when you had to read the moves for the player.

5. The MagicMaze Class has a non-static method called solveMagicMaze, which will be the actual problem solving (getting Kenny out of the maze) that you will need to implement. The method returns a Boolean value. If the value is true, then the maze was solved successfully, otherwise the maze was not solved successfully. You must use Backtracking to solve this maze. I would recommend creating a recursive method like the N-Queens problem we did in class.

6. You are given 5 test mazes inside the provided text files. All text files are in the same directory as the driver and solution file you are going to implement. DO NOT CREATE SUBFOLDERS! Points will be deducted and will not be given back!

7. You must use Backtracking in your implementation. If Backtracking is not used, then an automatic 0 will be given in this assignment as the overall grade with no partial credit.

8. Do NOT use any Graph Algorithms in this assignment. We have not covered graph algorithms yet! Any Graph Algorithms used will result in automatic 0 in the assignment as the overall grade with no partial credit.

9. You are welcome to create helper methods in your solution class, but please do not modify the driver class in any way. This will result in your code not working properly when grading, which will result in points being deducted that are not going to be given back.

The Provided Driver File: A driver file (MagicMazeDriver.java) has been provided for you to show you how the methods are called along with a test case based on maintaining the given maze. In this assignment, you will notice the main method uses the args parameter. In order to test your file when running your code you will need to type some extra things into the terminal. Besides typing java and the name of the class you want to run, you will need to include text file to be read, the number of rows, and the number of columns. For example, java MagicMazeDriver maze4.txt 15 20 will run the driver class along with sending the respective text file to be solved, the number of rows in that particular maze, and number of columns as well. Please note that you can only test one maze at a time. The provided python script will test all 5 mazes at once to ensure they are within the time constraint requirements.

Driver file:

import java.io.File; import java.util.Scanner; public class MagicMazeDriver { public static void main(String args[]) throws Exception { MagicMaze maze = new MagicMaze(args[0], Integer.parseInt(args[1]), Integer.parseInt(args[2])); if(maze.solveMagicMaze()) System.out.println(args[0] + " passed!"); else System.out.println(args[0] + " did not passed!"); } }

My code:

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class MagicMaze { private char[][] maze; //2D array to store the maze private String mazeName; //Name of the maze private int numRows; //Number of rows in the maze private int numColumns; //Number of columns in maze //Constructor to initialize the MagicMaze object public MagicMaze(String mazeName, int numRows, int numColumns) { this.mazeName = mazeName; this.numRows = numRows; this.numColumns = numColumns; this.maze = new char[numRows][numColumns]; readMazeFromFile(mazeName); } //Method to read maze from text files public void readMazeFromFile(String fileName) { try { Scanner scanner = new Scanner(new File(fileName)); for (int row = 0; row < numRows; row++) { String line = scanner.nextLine(); for (int col = 0; col < numColumns; col++) { maze[row][col] = line.charAt(col); } } scanner.close(); } catch (FileNotFoundException e) { System.err.println("Error reading maze from file: " + e.getMessage()); } } public boolean solveMagicMaze() { return backtrack(0, numColumns - 1); // Starting position is at (0, numColumns - 1) } private boolean backtrack(int row, int col) { // Base case: Check if Kenny has reached the exit ('X') if (maze[row][col] == 'X') { return true; // Maze is successfully solved } // Check if the current cell is a valid path ('*') or a teleportation pad ('1', '2', '3', etc.) if (maze[row][col] == '*' || Character.isDigit(maze[row][col])) { // Mark the current cell as visited char original = maze[row][col]; maze[row][col] = '@'; // Try to move in all 4 directions (up, down, left, right) if (isValidMove(row - 1, col) && backtrack(row - 1, col)) return true; // Move up if (isValidMove(row + 1, col) && backtrack(row + 1, col)) return true; // Move down if (isValidMove(row, col - 1) && backtrack(row, col - 1)) return true; // Move left if (isValidMove(row, col + 1) && backtrack(row, col + 1)) return true; // Move right // If no valid moves lead to the exit, revert the cell back to its original state maze[row][col] = original; } return false; // Maze cannot be solved from this position } private boolean isValidMove(int row, int col) { // Check if the move is within the maze boundaries and the cell is valid ('*' or a teleportation pad) return row >= 0 && row < numRows && col >= 0 && col < numColumns && (maze[row][col] == '*' || Character.isDigit(maze[row][col])); } }
maze1.txt:

@******@@@****X @****@@@@@@@*** @*************1 *@@@@@@@******* ********@@@@@@@ 1***@********** ****@****@***** ****@****@***** ****@****@***** ****@****@***** *********@*****
maze2.txt:

2***@8**X@***** ****@@@@@@@@@@@ *3**@3**4@****5 @@@@@@@@@@@@@@@ ****@***6@***** ****@5***@****7 6**7@***4@**8** @@@@@@@@@@@@@@@ ***1@****@****1 ****@****@***** ****@****@2****
maze3.txt:

*******@3*****4 *******@@@@@@@@ *******@******5 2*****3@4***@@@ @@@@@@@@@@@@@@@ *******@******* *******1***2**@ *******@******@ *******@@@@@@@@ *******@5@***1@ *******@X@****@
maze4.txt:

5@*****@*****@*****X *@*****@*****@****** *@***6*@*****@****** *@5***9@7***6@****** *@@@@@@@@@@@@@****** ****4@*******@****** *****@**@****@****** *****@2*@****@*****9 @@@@@@@@@@@@@@@@@@@@ **0**@******4@0***** *****@*******@****** 2*1*3@3******@****** @@@@@@@@@@@@@@@@@@@@ ****1@*******@7***** *****@8******@*****8
maze5.txt:

******************** 5******************* ******@@@@@@***X**** @@@@@@@5432@@@@@@@@@ ******************** ***********@@@@@@@@* *******@***@@@@@@@@* *@@@@@4@***@@******* ******@@***@@******* *@*********@@******* *3@@*******@@1****** @@@@@@@@@@@@@@@@@@@@ ******************** ***@@@@***@@@@@@@@@@ *****2@************1