# Solving a Maze

• 04-13-2010, 02:16 AM
bdario1
Solving a Maze
A maze-solving application:
Write an application that finds the shortest path through a maze and reports this shortest path to the user. Your application must:

* Ask the user for the name of a file that contains the maze description.
* Read the maze description from the file.
* Compute the shortest path (any shortest path) through the maze.
* Display four pieces of information for the user:
o The row and column number of the start point in the maze.
o The row and column number of the end point in the maze.
o The number of steps in the shortest path in the maze.
o The exact steps required to move from the start point to the end point (along a shortest path).

You will need the following details:

Maze file format

Mazes will be described by the data in a text file. The data will have this exact form:

The first line of the text file will have two integers on it. The first integer represents the width of the maze (number of columns), the second integer represents the height of the maze (number of rows).

The next lines of the maze will contain a single 'word', or sequence of non-whitespace characters. These characters describe the maze one row at a time. There will be one line for each row in the maze. The characters have the following meaning:
# A wall square. This space is impassable.
- An empty square. You can move through these spaces.
S The start square. (Treat it as an empty square.)
E The end square. (Treat it as an empty square.)

Here are a few sample maze files:

Example maze #1:
5 4
#####
S--##
##--E
#####

Example maze #2:
6 6
------
#--#--
--##--
---#-#
--E#S-
------

Your program must display the following information for the user:

* The row and column number of the start point in the maze. The upper-left hand corner character of the maze is at row 0, column 0. Your message should be user friendly. For maze example #1, you might print: "The start point is at row 1, column 0."

* The row and column number of the end point in the maze. The upper-left hand corner character of the maze is at row 0, column 0. Your message should be user friendly. For maze example #2, you might print: "The end point is at row 4, column 2."

* The number of steps in the shortest path in the maze. Again, your message should be user friendly. For maze example #, you might print: "The shortest path through the maze takes 4 steps."

If there is no path through the maze, you should print: "There is no path through this maze."

* The exact steps required to move from the start point to the end point (along a shortest path). Print this in a compact form. Use single uppercase characters for each direction, and don't put spaces in the path. For maze example #2, you would print: "The shortest path is: SWWN."

Could someone at least help me get started. Thank You
• 04-13-2010, 02:30 AM
Fubarable
Quote:

Originally Posted by bdario1
Could someone at least help me get started. Thank You

Best of luck with this and future projects!
• 04-13-2010, 04:48 AM
bdario1
Ok thanx for that, i figured out how to import the file and create an 2d array that is width and height size, what i can't figure out is how to find the S in the maze i have the for loop that goes through the entire rows and columns.
Code:

``` public class Maze {         public static void main(String[] args) {         boolean [][] isWall;         int width, height;         int startRow, startColumn, endRow, endColumn;         File file = new File("maze1.txt");                  try {                                   Scanner scanner = new Scanner(file);                   width = scanner.nextInt();                   height = scanner.nextInt();                                     int [][] maze = new int [width][height];                   for(int row =0; row < maze.length; row++)                           {                           for (int col=0; col < maze[row].length; col++)                           {                                   // if(scanner.) here is where i am stuck                           }                           }                                                 } catch (FileNotFoundException e) {                     e.printStackTrace();                 } } }```
Also i am not sure if i am reading the file correctly in to the array
• 04-14-2010, 12:57 AM
bdario1
This is what i have so far for the Maze method.
Code:

```package assignment11; import java.util.Scanner; public class Maze {         private boolean[][] isWall;         private int startX, startY, endX, endY;         private int width, height;                 public Maze(Scanner input)         {                 width = input.nextInt();                 height = input.nextInt();                 isWall = new boolean [width][height];                 for(int y = 0; y < height; y++)                 {                         String rowOfTxt = input.next().toUpperCase();                         for(int x = 0; x < width; x++)                         {                                 char ch = rowOfTxt.charAt(x);                                 isWall[x][y] = ch == '#';                                 if(ch =='S')                                 {                                         startX = x;                                         startY = y;                                 }                                 if (ch =='E')                                 {                                         endX = x;                                         endY = y;                                 }                         }                 }         }                 public int getStartX()         {                 return startX;         }         public int getStartY()         {                 return startY;         }         public int getEndX()         {                 return endX;         }         public int getEndY()         {                 return endY;         }                 private boolean isWall(int x, int y)         {                 if(x< 0 || x>width|| y < 0 || y >= height)                         return true;                 return isWall[x][y];         }         public String solve()         {                 String [][] sol = new String[width][height];                 sol[startX][startY] = " ";                 boolean ArrayChanged = true;                 while(ArrayChanged)                 {                         ArrayChanged = false;                         for(int x = 0; x < width; x++)                                 for(int y = 0; y < height; y++)                                 {                                         if(isWall(x,y))                                                 continue;                                         String solS = null, solN=null, solE = null, solW = null;                                         if(!isWall(x-1,y)&&sol[x-1][y] !=null)                                                 solW = sol[x-1][y] + "E";                                         if(!isWall(x+1,y)&&sol[x+1][y] !=null)                                                 solE = sol[x+1][y] + "W";                                         if(!isWall(x,y-1)&&sol[x][y-1] !=null)                                                 solN = sol[x][y-1] + "S";                                         if(!isWall(x,y+1)&&sol[x][y+1] !=null)                                                 solS = sol[x][y+1] + "N";                                                                                 String shortest = null;                                         if(solW !=null && (shortest == null || solW.length()<shortest.length()))                                                         shortest = solW;                                         if(solE !=null && (shortest == null || solE.length()<shortest.length()))                                                 shortest = solE;                                         if(solN !=null && (shortest == null || solN.length()<shortest.length()))                                                 shortest = solN;                                         if(solS !=null && (shortest == null || solS.length()<shortest.length()))                                                 shortest = solS;                                                                                 if(shortest ==null)                                                 continue;                                                                                 if(sol[x][y] ==null || shortest.length()<sol[x][y].length()){                                                 sol[x][y] = shortest;                                                 ArrayChanged = true;                                         }                                                                         }                 }                 return sol[endX][endY];         }         }```
And here is the solver which is having problems that i can not figure out why?
Code:

```package assignment11; import java.io.File; import java.io.IOException; import java.util.Scanner; public class SolveMaze {         try{                 System.out.println("Please enter a name of your txt file (maze.txt): ");                 String filename = new Scanner(System.in).nextLine().trim();                 Scanner mazeScanner = new Scanner(new File(filename));                                 Maze m = new Maze(mazeScanner);                                 System.out.println("The Start is at location "+m.getStartX() + " row and " +m.getStartY() + " column.");                 System.out.println("The End is at location "+m.getEndX() + " row and " +m.getEndY() + " column.");                                 String sol = m.solve();                         if (sol == null)                                 System.out.println("There is no solution for the maze specified. ");                         else{                                 System.out.println("The solution is: " +sol);                                 System.out.println("Solution has length of " +sol.length());                                 } }catch(IOException e){         System.out.println("We are sorry but the file specified could not be located! "); } }```
Error: java.lang.NoSuchMethodError: main
```import java.io.File; import java.io.IOException; import java.util.Scanner; public class SolveMaze {         try{                 System.out.println("Please enter a name of your txt file (maze.txt): ");                 String filename = new Scanner(System.in).nextLine().trim();                 Scanner mazeScanner = new Scanner(new File(filename));                                 Maze m = new Maze(mazeScanner);                                 System.out.println("The Start is at location "+m.getStartX() + " row and " +m.getStartY() + " column.");                 System.out.println("The End is at location "+m.getEndX() + " row and " +m.getEndY() + " column.");                                 String sol = m.solve();                         if (sol == null)                                 System.out.println("There is no solution for the maze specified. ");                         else{                                 System.out.println("The solution is: " +sol);                                 System.out.println("Solution has length of " +sol.length());                                 } }catch(IOException e){         System.out.println("We are sorry but the file specified could not be located! "); }```