Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: BackTracking in a maze

  1. #1
    Junior Member
    Join Date
    Jan 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: BackTracking in a maze

    One way I can think of is to use a recursive nextMove search method that tries all possible next squares from the current one. Any path that dead ends, stops running.
    Another would be to use a stack to keep track of the last position to allow you to back up if the current path was blocked.

    Is this a continuation of http://www.javaprogrammingforums.com...-program.html?

    I see that you didn't follow any of my suggestions from that post to make your code easier to debug.
    Last edited by Norm; January 26th, 2012 at 07:25 AM.

  3. #3
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: BackTracking in a maze

    Cross posted at BackTracking in a maze - Java | DaniWeb

Similar Threads

  1. Depth-Limited Search using Recursive Backtracking...please help!
    By Zaxx81 in forum Algorithms & Recursion
    Replies: 26
    Last Post: June 20th, 2012, 04:21 PM
  2. Maze Game
    By whatsbruin in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 15th, 2011, 05:59 PM
  3. Recursion Maze
    By sman1234 in forum What's Wrong With My Code?
    Replies: 0
    Last Post: October 28th, 2010, 11:40 AM
  4. Q:BackTracking Algorithm
    By Cross`17 in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 17th, 2010, 11:33 PM
  5. Problem in recursion for Solving Maze Recursively program
    By _Coder1985 in forum Algorithms & Recursion
    Replies: 1
    Last Post: April 29th, 2009, 04:37 AM

Tags for this Thread