I have a Java class that I need help finishing, everything is done except for backtrack and findSolution, I have provided the program and the specifications for the previously mentioned methods.

package maze;

import java.io$.$FileNotFoundException;

import java.io$.$FileReader;

import java.util.Scanner;

public class MazeSolver

$\{$

private final static int HEIGHT $=99$;

private final static int WIDTH $=99$;

private boolean$[][]$ wall;

public MazeSolver$($String mazeFile$)$

$\{$

loadMaze$($mazeFile$)$;

$\}$

private void loadMaze$($String mazeFile$)$

$\{$

wall $=$ new boolean$[$HEIGHT$][$WIDTH$]$;

Scanner mazeScanner;

try

$\{$

mazeScanner $=$ new Scanner$($new FileReader$($mazeFile$))$;

for $($int i $=0$; i $<$ HEIGHT; i$++)$

$\{$

for $($int j $=0$; j $<$ WIDTH; j$++)$

$\{$

if $($mazeScanner$.$next$().$equals$("1"))$

$\{$

wall$[$i$][$j$]=$ true;

$\}$

$\}$

$\}$

mazeScanner.close$()$;

$\}$

catch $($FileNotFoundException e$)$

$\{$

System.out.println$("$File not found: $"+$ mazeFile$)$;

$\}$

$\}$

public void printMap$()$

$\{$

for $($int i $=0$; i $<$ HEIGHT; i$++)$

$\{$

for $($int j $=0$; j $<$ WIDTH; j$++)$

$\{$

if $($wall$[$i$][$j$])$

$\{$

System.out.print$("$X$")$;

$\}$

else

$\{$

System.out.print$("\_")$;

$\}$

$\}$

System.out.println$()$;

$\}$

System.out.println$()$;

$\}$

$\}$

findSolution

$*$ This should just call your recursive method, starting at the top left of the maze and an empty path so far.

$*$ It will return the string representing the path that the recursive method found.

backtrack

$*$ This is the recursive algorithm; all of the work happens here. The String backtrack returns, if there is a solution, is a list of the commands you need to input to get to the goal from the start with a space in between each command. For example, $"$up down up up left right..." etc.

$*$ You should first write the base case; check to see if you are at the goal of maze. If you are, return the String path that got you there.

$*$ If you are not at the goal, then you must continue to search. Try recursively checking the up$,$ down, left, and right positions of the current position; make sure all of these positions are valid.

$*$ If the result of one of the recursive calls is not null, that means the recursive algorithm has found a solution, and you should return that result.

$*$ The following pseudo code will give you an idea of how to complete the recursive call in the up direction.

$//$ try up$$ if board$[$row $-1][$col$]$ is on the board and has not been visited$\{$ result $=$ call to backtrack with row $-1$ and col$$ if result isn't null$\{$ return result$\}\}$

$*$ If you try all four directions and none of them worked, you failed to find a solution and should return null.

$*$ Keeping track of what positions you have already visited is very helpful. That way you can avoid revisiting a square that is already being tested. A $2$D array is recommended for this.$$

$*$ Writing a helper method that checks if a position is valid and not visited yet is highly recommended.