1.11M Members

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");
System.out.print("Enter random starting seed  ===>>  ");

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
{
String dummy;
System.out.print("\nPress <Enter> to continue  ===>>  ");
}
}

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
{
}

public void push (E x)
// Adds variable x to the top of the stack
{
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.``````

I would appreciate any answer or comment