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

Quote:

---

Originally Posted by bdario1

Could someone at least help me get started. Thank You

---

Hello. For an excellent short article that can help you get started in this and similar problems, please the fourth link in my signature below. It will tell you that the key to solving this and most problems is to break the big problem down into small problems and to then try to solve each small problem in isolation before joining the effort together. If you still get stuck, then read the other links in my signature, including how to ask questions because the better your question, the more specific it is, the better the help you will receive. Right now your question is general to the extreme and so the only help most of us can offer is very general help (such as this).

Best of luck with this and future projects!

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

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
Exception in thread "main"

In this class:

Code:

---

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! ");
}

---

You seem to be trying to call many methods out in the open in the class itself and not in any method, constructor or initializer block. Perhaps you meant to put this stuff in a main method? If so, you may wish to correct what the error message is telling you.