BackTracking in a maze

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 3053 Views - Last Post: 16 February 2012 - 08:06 PM Rate Topic: -----

#1 skoon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-January 12

BackTracking in a maze

Posted 28 January 2012 - 12:45 AM

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 or any solution 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

Is This A Good Question/Topic? 0
  • +

Replies To: BackTracking in a maze

#2 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: BackTracking in a maze

Posted 28 January 2012 - 06:48 PM

to solve the maze using backtracking, basically here's idea

solve_maze:
   for ever possible starting position in the maze
       if(search(position)) //try solving from that position
           return true
   return false

search(pos):
    if i am out of the maze
        return true
    if i can move right
        pos = move right
        search(new pos)
    if i can move left
        pos = move left
        search(pos)
    if i can move down
        pos = move down
        search(pos)
    if i can move up
        pos = move up
        search(pos)
    return false



This is just a typical depth first search algorithm. Hope this helps.
Was This Post Helpful? 2
  • +
  • -

#3 skoon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-January 12

Re: BackTracking in a maze

Posted 29 January 2012 - 07:47 PM

Hello every body

I'm new to programming so please don't think I know everything in programming

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 or any other solution 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
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10461
  • View blog
  • Posts: 38,753
  • Joined: 27-December 08

Re: BackTracking in a maze

Posted 30 January 2012 - 06:59 AM

I don't see any clear logic to determine if the maze has been solved or not. That's the biggest problem. See your logic. While you can make a move, then move.
while(getMove())
092	        {
093	            mat[currentMove.getrPos()][currentMove.getcPos()] = '.';
094	        }


Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10461
  • View blog
  • Posts: 38,753
  • Joined: 27-December 08

Re: BackTracking in a maze

Posted 30 January 2012 - 07:20 AM

Duplicate threads merged. Please avoid duplicate posting.
Was This Post Helpful? 0
  • +
  • -

#6 skoon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-January 12

Re: BackTracking in a maze

Posted 30 January 2012 - 06:34 PM

View Postmostyfriedman, on 28 January 2012 - 06:48 PM, said:

to solve the maze using backtracking, basically here's idea

solve_maze:
   for ever possible starting position in the maze
       if(search(position)) //try solving from that position
           return true
   return false

search(pos):
    if i am out of the maze
        return true
    if i can move right
        pos = move right
        search(new pos)
    if i can move left
        pos = move left
        search(pos)
    if i can move down
        pos = move down
        search(pos)
    if i can move up
        pos = move up
        search(pos)
    return false



This is just a typical depth first search algorithm. Hope this helps.



thank for your answer mostyfriedman but I am new to programming and I don't fully understand the code you've put or how to implement it in my program. I would be grateful to you if you can clarify the code more and show how to implement it in the program

thanks,
Mahdi
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10461
  • View blog
  • Posts: 38,753
  • Joined: 27-December 08

Re: BackTracking in a maze

Posted 30 January 2012 - 06:50 PM

It really doesn't get much simpler than mostyfriedman's algorithm. You can almost directly translate it into code. I have a tutorial on backtracking, as well, that may help you. It is up to you though to adapt this into your code. We are happy to help you further debug as you run into problems. :)
Was This Post Helpful? 2
  • +
  • -

#8 skoon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-January 12

Re: BackTracking in a maze

Posted 12 February 2012 - 12:16 AM

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 did BackTracking in the getMove() method but it didn't work

this is my code

// Lab29ast.java
// This is the student version of the Lab29a assignment.  Complete this file as is.


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()] = '.';
			//System.out.println("1");
			visitStack.push(currentMove);
			//System.out.println("2");

		}
	}

	// 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;
			}
		}

		else 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;
			}
		}

		else 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;
			}
		}

		else 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;
			}
		}

		else 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;
			}
		}

		else 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;
			}
		}

		else 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;
			}
		}

		else 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(canmove == true)                                //BackTracking
		{
			currentMove = new Coord(tempRow, tempCol);
			//System.out.println(currentMove + " push");
		}
		else
		{
			currentMove = (Coord)visitStack.pop();
		    //System.out.println(currentMove + " pop");
		}

//		if(visitStack.isEmpty())
//			canmove = false;
//		else
//			canmove = true;

		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();
	}
}




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  .  X
X  X  X  X  X  O  O  X  X  X  .  X
X  X  X  O  O  X  X  O  O  X  .  X
X  O  X  X  O  O  O  X  O  O  .  X
X  X  X  X  X  O  O  X  O  X  .  .
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
Was This Post Helpful? 0
  • +
  • -

#9 skaoth  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 91
  • View blog
  • Posts: 601
  • Joined: 07-November 07

Re: BackTracking in a maze

Posted 12 February 2012 - 12:55 AM

Disclaimer: I didn't read through all your code cuz I've been drinking too much.

Just looking at the amount of code you wrote for getMove and mazeSolution smelled kind of funny
The concept is pretty straight forward

With your assumtions
X - SOLID WALL (no passage allowed)

O - PATH (passage allowed)

. - TRAVELED (path traveled to find the exit)

and F for exit

pseudo code

boolean solveMaze(int x, int y) {
  if(maze[x][y] == 'F' {
    return true;
  } else if (maze[x][y] == '.' || maze[x][y] == 'X') {
    return false
  } else {
  // otherwise try each of the 4 possible steps
    maze[x][y] = '.'
    if(solveMaze(x + 1, y)) return true;
    if(solveMaze(x, y + 1)) return true;
    if(solveMaze(x, y - 1)) return true;
    if(solveMaze(x - 1, y)) return true;

    // couldn't find a from this position
    maze[x][y] = 'O';
    return false;

  }  

}



hopefully this clears somethings up

This post has been edited by skaoth: 12 February 2012 - 12:56 AM

Was This Post Helpful? 0
  • +
  • -

#10 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • Joined: 10-September 10

Re: BackTracking in a maze

Posted 12 February 2012 - 01:21 AM

You suggested "back tracking," but I would think of it as "resetting." I suggest storing all possible moves for each visited location (pushing onto a stack?), and if you come to a dead end as you've done in your current solution, then you'd reset to the first stored location, and continue solving the maze from there. The stored move specifies the ( x, y ) location and the coordinate of the possible move. When you've reached a dead end with no possible moves stored, then the maze has no solution from that starting point.
Was This Post Helpful? 1
  • +
  • -

#11 Atli  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3717
  • View blog
  • Posts: 5,979
  • Joined: 08-June 10

Re: BackTracking in a maze

Posted 12 February 2012 - 02:37 AM

* Duplicate threads merged... again. *

Do not double post your questions!
Was This Post Helpful? 0
  • +
  • -

#12 skoon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-January 12

Re: BackTracking in a maze

Posted 12 February 2012 - 11:37 AM

View PostGregBrannon, on 12 February 2012 - 01:21 AM, said:

You suggested "back tracking," but I would think of it as "resetting." I suggest storing all possible moves for each visited location (pushing onto a stack?), and if you come to a dead end as you've done in your current solution, then you'd reset to the first stored location, and continue solving the maze from there. The stored move specifies the ( x, y ) location and the coordinate of the possible move. When you've reached a dead end with no possible moves stored, then the maze has no solution from that starting point.


thank you for your comment GregBrannon, but I am new to programming and I don't fully understand how to fully implement the concept you told me about. I would be grateful to you if you can show me an example of how to implement this concept in me program

thanks,
Mahdi
Was This Post Helpful? 0
  • +
  • -

#13 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • Joined: 10-September 10

Re: BackTracking in a maze

Posted 12 February 2012 - 12:20 PM

This was a fun exercise; a welcome diversion from my own rather boring project. Thanks for posting it and your code that I think is pretty close to a solution requiring only minor changes.

I wrote a recursive solveMaze() method that uses the following logic:
public void solveMaze( Coord currentPosition )
{
   // determine if the maze has been solved and stop the
   // recursion if it has. (I check for 0,0 = '.')
   // set a flag hasSolution = true, and return

   // leave a bread crumb, '.', at the currentPosition

   // determine all possible moves for currentPosition
   // (note comment below re: possible moves)

   // while there are moves remaining in the nextMoves stack
   {
      // get the next move from the stack

      // solve the maze starting from the next move
      // ^ this is where the recursion happens
   }

} // end solveMaze()

You can modify the above to find all possible moves in the maze. If coded as above, it will find A path to a solution, if one exists, that may not show all possible moves in the maze.

Note re: possible moves: Your getMove() method needs to be modified to find ALL possible moves rather than a SINGLE possible move from each position in the maze. The if/else logic used currently only finds one move. Just fixing this may move you very close to a solution, but I can't verify that without your class MyStack. Try fixing this first and see what happens.

Here's how I modified your code to check for a move at x - 1, y. Notice:

- I used the temp variables to simplify the if statements,
- I took advantage of the boolean returned by the method inBounds(), and
- the removal of the else.
private void setMoves( MazeCoord currentPosition ) // throws IOException
{
    int tempX = currentPosition.getXPos();
    int tempY = currentPosition.getYPos();

    if( inBounds( ( tempX - 1 ), ( tempY ) ) )
    {
        if( charMatrix[tempX - 1][tempY] == 'O' )
        {
            nextMoves.push( new MazeCoord( tempX - 1, tempY ) );
        }
    }

    if( inBounds( ( tempX -1 ), ( tempY +1 ) ) )

etc . . . .

You might wonder, "How big does the nextMoves stack have to be?" To explore ALL possible moves, it topped out ~50 elements on the stack. To find A solution, it tops out in the low 20s.

Let us know how it's going.
Was This Post Helpful? 1
  • +
  • -

#14 skoon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-January 12

Re: BackTracking in a maze

Posted 12 February 2012 - 08:10 PM

I tried the code you wrote but it didn't work (infinite loop). I might implemented the code wrong. If you can show me how to implement the code into my program I world be thankful.

thanks,
Mahdi

This post has been edited by Atli: 13 February 2012 - 02:54 AM
Reason for edit:: Removed the quote. There is no need to quote the enitre post above.

Was This Post Helpful? 0
  • +
  • -

#15 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • Joined: 10-September 10

Re: BackTracking in a maze

Posted 13 February 2012 - 04:25 AM

Post your updated code, and describe the infinite loop indications.

BTW - Your code works with a few minor changes:

1. The biggest change is to rethink your stack. You're currently saving the coordinates of where you've been in the maze, but you don't care where you've been. You want to know where you can go from where you've been. So for each location visited, push the possible moves to the stack. That's a simple change to your getMove() method - 8 times.

2. Correct the logic at the end of getMove() as shown below so that as long as there are moves left on myStack, the solveMaze() method will continue:
        if( !myStack.isEmpty() )                                //BackTracking
        {
            currentMove = (Coord)myStack.pop();
            return true;
        }
        else
        {
            return false;
        }


3. You'll then have to change your logic to determine if the maze has a solution, because the currentMove may not be at 0, 0 when the getMove() method is done.

Minor stuff. You can finish it quickly.

This post has been edited by GregBrannon: 13 February 2012 - 11:39 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2