Hello every body
I'm creating a program that generates a random maze depending on the starting point you enter and then solves it. My problem is that even thought there is a solution to the maze, it returns that there is no solution to the maze.
I know that I have to do backtracking in the getMove() method but I don't know how to do it
this is my code
import java.io.*;
import java.util.*;
import java.util.ArrayList;
public class lab29a
{
public static void main(String args[]) throws IOException
{
System.out.println("\nLab 29a \n");
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter random starting seed ===>> ");
int seed = Integer.parseInt(input.readLine());
Maze maze = new Maze(seed);
maze.displayMaze();
maze.solveMaze();
maze.displayMaze();
maze.mazeSolution();
}
}
class Coord // Coord is a class that stores a single maze location.
{
private int rPos;
private int cPos;
public Coord (int r, int c) { rPos = r; cPos = c; }
public boolean isFree() { return (rPos == 0 && cPos == 0);}
public void setPos(int r, int c) { rPos+= r; cPos+= c; }
public int getrPos() { return rPos; }
public int getcPos() { return cPos; }
}
class Maze
{
private char mat[][]; // 2d character array that stores the maze display
private Coord currentMove; // object that stores current maze position
private MyStack visitStack; // stack that stores location that have been visited
// constructor which generates the random maze, random starting location
// and initializes Maze class values. If the random value equals 0 the maze
// store an 'X' otherwise it store an 'O' in the maze.
public Maze(int seed)
{
Random random = new Random(seed);
int startRow, startCol;
mat = new char[12][12];
for (int r = 0; r < 12; r++)
for (int c = 0; c < 12; c++)
{
if (r == 0 || c == 0 || r == 11 || c == 11)
mat[r][c] = 'X';
else
{
int rndInt = random.nextInt(2);
if (rndInt == 0)
mat[r][c] = 'X';
else
mat[r][c] = 'O';
}
}
mat[0][0] = 'O';
startRow = random.nextInt(12);
startCol = 11;
mat[startRow][startCol] = '.';
visitStack = new MyStack();
currentMove = new Coord(startRow,startCol);
visitStack.push(currentMove);
}
// displays the current maze configuration
void displayMaze() throws IOException
{
System.out.println("\nRANDOM MAZE DISPLAY\n");
for (int r = 0; r < 12; r++)
{
for (int c = 0; c < 12; c++)
System.out.print(mat[r][c] + " ");
System.out.println();
}
System.out.println();
pause();
}
// This method solves the maze with private helper method <getMove>.
// A loop is needed to repeat getting new moves until either a maze solution
// is found or it is determined that there is no way out off the maze.
public void solveMaze() throws IOException
{
System.out.println("\n>>>>> WORKING .... SOLVING MAZE <<<<<\n");
while(getMove())
{
mat[currentMove.getrPos()][currentMove.getcPos()] = '.';
}
}
// Short method to display the result of the maze solution
public void mazeSolution()
{
if (currentMove.isFree())
System.out.println("\nTHE MAZE HAS A SOLUTION.\n");
else
System.out.println("\nTHE MAZE HAS NO SOLUTION.\n");
}
// This method determines if a coordinate position is inbounds or not
private boolean inBounds(int r, int c)
{
boolean inBound = false;
if(r >= 0 && c >= 0)
{
if((r + 1 ) < mat.length && (c + 1) < mat[0].length)
inBound = true;
}
return inBound;
}
// This method checks eight possible positions in a counter-clock wise manner
// starting with the (-1,0) position. If a position is found the method returns
// true and the currentMove coordinates are altered to the new position
private boolean getMove() throws IOException
{
boolean canmove = false;
int tempRow = currentMove.getrPos();
int tempCol = currentMove.getcPos();
if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() + 0)) == true)
{
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 0] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() - 1;
tempCol = currentMove.getcPos() + 0;
}
}
if(inBounds((currentMove.getrPos() -1), (currentMove.getcPos() +1)) == true)
{
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() - 1;
tempCol = currentMove.getcPos() + 1;
}
}
if(inBounds((currentMove.getrPos() + 0), (currentMove.getcPos() + 1)) == true)
{
if(mat[currentMove.getrPos() + 0][currentMove.getcPos() + 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 0;
tempCol = currentMove.getcPos() + 1;
}
}
if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() + 1)) == true)
{
if(mat[currentMove.getrPos() + 1][currentMove.getcPos() + 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 1;
tempCol = currentMove.getcPos() + 1;
}
}
if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() + 0)) == true)
{
if(mat[currentMove.getrPos() + 1][currentMove.getcPos() + 0] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 1;
tempCol = currentMove.getcPos() + 0;
}
}
if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() - 1)) == true)
{
if(mat[currentMove.getrPos() + 1][currentMove.getcPos() - 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 1;
tempCol = currentMove.getcPos() - 1;
}
}
if(inBounds((currentMove.getrPos() + 0), (currentMove.getcPos() - 1)) == true)
{
if(mat[currentMove.getrPos() + 0][currentMove.getcPos() - 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 0;
tempCol = currentMove.getcPos() - 1;
}
}
if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() - 1)) == true)
{
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() - 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() - 1;
tempCol = currentMove.getcPos() - 1;
}
}
currentMove = new Coord(tempRow, tempCol);
return canmove;
}
private void pause() throws IOException
{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
String dummy;
System.out.print("\nPress <Enter> to continue ===>> ");
dummy = input.readLine();
}
}
class MyStack<E>
{
private ArrayList<E> data; // stores stack data
private int top; // keeps index of the stack top
public MyStack()
// Initializes an empty array object with references of private variable data objects.
{
data = new ArrayList<E>();
top = -1;
}
public boolean isEmpty()
// Returns true if data is empty, false otherwise
{
return top == -1;
}
public void push (E x)
// Adds variable x to the top of the stack
{
data.add(x);
top++;
}
public E pop()
// Returns and removes the top element from the stack
{
int temp = top;
top--;
return data.remove(temp);
}
public E peek()
// Returns the top element from the stack without removal
{
return data.get(top);
}
}this is my output
X - SOLID WALL (no passage allowed)
O - PATH (passage allowed)
. - TRAVELED (path traveled to find the exit)
Enter random starting seed ===>> 25
RANDOM MAZE DISPLAY
O X X X X X X X X X X X
X O O X O O X X X X X X
X O O X O X O X O O O X
X X X O O X X O O O X X
X X X X O O O O O X O X
X X X X O O O X X X X X
X O X O X X O X O X O X
X X X X X O O X X X O X
X X X O O X X O O X O X
X O X X O O O X O O O X
X X X X X O O X O X O .
X X X X X X X X X X X X
Press <Enter> to continue ===>>
>>>>> WORKING .... SOLVING MAZE <<<<<
RANDOM MAZE DISPLAY
O X X X X X X X X X X X
X O O X O O X X X X X X
X O O X O X O X O O O X
X X X O O X X O O O X X
X X X X O O O O O X O X
X X X X O O O X X X X X
X O X O X X O X O X O X
X X X X X . . X X X O X
X X X . . X X . . X O X
X O X X . . . X O . . X
X X X X X . . X O X O .
X X X X X X X X X X X X
Press <Enter> to continue ===>>
THE MAZE HAS NO SOLUTION.
Press any key to continue...this is what should the output be
Enter random starting seed ===>> 25
RANDOM MAZE DISPLAY
O X X X X X X X X X X X
X O O X O O X X X X X X
X O O X O X O X O O O X
X X X O O X X O O O X X
X X X X O O O O O X O X
X X X X O O O X X X X X
X O X O X X O X O X O X
X X X X X O O X X X O X
X X X O O X X O O X O X
X O X X O O O X O O O X
X X X X X O O X O X O .
X X X X X X X X X X X X
Press <Enter> to continue ===>>
>>>>> WORKING .... SOLVING MAZE <<<<<
RANDOM MAZE DISPLAY
. X X X X X X X X X X X
X . . X . . X X X X X X
X . . X . X . X . . . X
X X X . . X X . . . X X
X X X X . . . . . X . X
X X X X . . . X X X X X
X O X O X X . X O X . X
X X X X X . O X X X . X
X X X O . X X . . X . X
X O X X . . . X . . . X
X X X X X . . X . X . .
X X X X X X X X X X X X
Press <Enter> to continue ===>>
THE MAZE HAS A SOLUTION.please help me for I need to know how to fix the program very quickly
I would appreciate any answer or comment
thank you in advance
