BackTracking in a maze

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

3

Contributors

2

Replies

9 Hours

Discussion Span

1 Year Ago

Last Updated

3

Views

skoon

Newbie Poster

7 posts since Jan 2012

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

1 Year Ago

0

You're never going to debug code that complex by just looking at the final result. Put a load of print statements into your code, printing the values of the key variables at each stage so you cen see where it's going wrong. Especially print everything that's pushed or popped on your stack.

JamesCherrill

... trying to help

Moderator

8,528 posts since Apr 2008

Reputation Points: 2,583

Solved Threads: 1,456

Skill Endorsements: 30

1 Year Ago

0

Cross posted at http://www.javaprogrammingforums.com/whats-wrong-my-code/13630-backtracking-maze.html

NormR1

Posting Sage