What happened to my maze? (JAVA)

Question

So, we are given a labyrinth with a wall (W) an open path (O) beginning pt (S) and finish pt (F).

I am trying to write an algorithm that takes a maze file and then turns it into a 2D dot array to create a grid.

As soon as I have a grid, I want to start with the “S” in the maze and try to determine if O can be crossed to get to F. (Return the boolean value true / false)

I know that this maze is solvable, so why am I becoming "false"? There must be a difficult problem, because everything I get is a simple logical false, and not "sorry, the maze does not go through" ...

Here is the Maze1.txt file:

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWOOOOOOOOOOOOOOOWWW
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWOFW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Here is my code (new attempt):

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;
import java.awt.Point;

public class MazeExplorer {
    static Point startPoint = new Point();
    static Point finishPoint = new Point();
    final static int mazeHeight = 12;
    final static int mazeWidth = 58;
    static char[][] mazePoints = new char[mazeHeight][mazeWidth];
    Stack<Point> pointsNotTraversed = new Stack<Point>();
    Point pt = new Point();
    static HashSet<Point> previousLocations = new HashSet<Point>();
    static Stack<Point> nextPoints = new Stack<Point>();

    public static void main(String[] args) throws FileNotFoundException{

        System.out.println("Please enter the file name of your Maze");
        Scanner console = new Scanner(System.in);
        File f = new File(console.nextLine());
        Scanner sc = new Scanner(f);

        if(!sc.hasNextLine()){
            System.out.println("Sorry, please enter a file name with the extension, that contains a maze!");
        }
        System.out.println("So, you want to know if your maze is solvable.....?");

        for (int row = 0; row < mazeHeight && sc.hasNext(); row++) {
            final String mazeRow = sc.next(); //Get the next row from the scanner.
            mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[].
        }
            //identify the finish point
        for(int i = 0; i < mazeHeight; i++){
            for(int j = 0; j<mazeWidth; j++){
                if(mazePoints[i][j] == 'F'){
                    finishPoint = new Point(i, j);
                }       
            }
        }
        // Identify the start point
       for(int i = 0; i< mazeHeight; i++){
           for(int j = 0; j < mazeWidth; j++){
               if(mazePoints[i][j] == 'S'){
                 startPoint = new Point(i , j);
               }
           }
       }
       isTraversable(startPoint);    
    }
        public static  boolean isTraversable(Point current){
            boolean isSolvable = false;
            do {
                mazePoints[current.x][current.y] = ' ';

                if (mazePoints[current.y - 1][current.x] == 'O'){ //up dir
                   nextPoints.push(new Point(current.y - 1, current.x));
                    mazePoints[current.y - 1][current.x] = ' ';  //'X' marks where you've already been          
                }
                if(mazePoints[current.y + 1][current.x] == 'O'){ // below direction
                    nextPoints.push(new Point(current.y + 1, current.x));
                    mazePoints[current.y + 1][current.x] = ' ';        
                }
                if(mazePoints[current.y][current.x + 1] == 'O'){ // to the right
                    nextPoints.push(new Point(current.y, current.x + 1));
                    mazePoints[current.y][current.x + 1] = ' ';
                }
                if(mazePoints[current.y][current.x - 1] == 'O'){ // to the left
                    nextPoints.push(new Point(current.y, current.x - 1));
                    mazePoints[current.y][current.x - 1] = ' ';             
                }
                if(mazePoints[current.y][current.x] == 'F'){
                    isSolvable = true;
                    System.out.println("MAZE IS SOLVABLE, YAHOOOOOO!!!!");
                }
                current = nextPoints.peek();
                nextPoints.pop();
                isTraversable(current);         
            } while(!current.equals('F') && !nextPoints.isEmpty());         
            return isSolvable;          
        }
}

Answer 1

:

do
    mark current spot in the array as "visited" (can use any symbol you want)
    push all of the neighbors not yet visited onto the stack
    current spot <-- top of the stack to visit the next spot
    pop the stack
while (exit is not found && stack is not empty)

5 , , .

EDIT ( OP):

canMove<direction> , , . , traverseMaze row col , ​​ .

-

//assuming that current spot is at r,c
if (mazePoints[r-1][c] == 'O'){ //up dir
    pointsInMaze.push(new Point(r, c));
    mazePoints[r-1,c] = '';  //empty char marks where you've already been
}
//other directions ommitted here

, , , , . , " " ", " ", , , . , . , , ,

Answer 2

, .

psuedo:

push starting point to path stack
lastStepValid = true
while (stack is not empty && goal not found) {
  lastStep = peek the top of path stack


  if (lastStep == goal) {
      goal found = true
  } else if (not lastStepValid) {
    leave last step poped
    if (path stack is not empty) {
      pop path stack
      lastStepValid = true
      if (lastStep is UP of top of path stack) {
          push RIGHT of top of path stack to path stack 
      } else if (lastStep is RIGHT of top of path stack) {
          push DOWN of top of path stack to path stack
      } else if (lastStep is DOWN of top of path stack) {
          push LEFT of top of path stack to path stack
      } else {
          lastStepValid = false
      }
    }
  } else if (lastStep is wall || lastStep exists more than once in the stack) {
      lastStepValid = false;
   } else {  // last step is valid
      push the UP of lastStep to path stack
   }
}

, , , , , .

, .

Answer 3

You asked in the comments of your question how to find a starting point. You can find the starting point while starting the mazePoints array

    Stack<Point> stack = new Stack<Point>();
    Point start;
    File f = new File("Maze1.txt");
    final Scanner sc = new Scanner(f);
    for (int row = 0; row < mazeHeight && sc.hasNext(); row++) {
      final String mazeRow = sc.next(); //Get the next row from the scanner.
      mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[].
      for (int i = 0; i < mazeRow.length(); i++) {
        if (mazeRow.charAt(i) == 'S') {
          start = new Point(row, i);
          stack.push(start);
          break;
        }
      }
    }

After initialization, follow one of the algorithms suggested above.