skoon - Viewing Profile

skoon's Profile User Rating:

Reputation: 0 Apprentice

Group:: New Members
Active Posts:: 12 (0.03 per day)
Joined:: 28-January 12
Profile Views:: 82
Last Active:: Feb 18 2012 10:37 PM
Currently:: Offline

Previous Fields

Dream Kudos:: 0

skoon has not set their status

Posts I've Made

In Topic: BackTracking in a maze

Posted 16 Feb 2012

GregBrannon, on 13 February 2012 - 04:25 AM, said:

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.

Sorry for my late reply GregBrannon, I have been busy for the last 3 days.

I changed the logic at the end of the getMove() method as you told me but I'm still having an infinite loop. Also for the mazeSolution(), there is an if else so if currentMove tried the last move it could do and that move wasn't at (0,0), it should say that there is no solution to the maze.

this is my updated code

// Lab29ast.java


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;

				visitStack.push( new Coord(tempRow , tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow , tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow , tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow, tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow, tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow, tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow, tempCol));
			}
		}

		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;

				visitStack.push( new Coord(tempRow, tempCol));
			}
		}



		if(!visitStack.isEmpty())						//BackTracking
		{
    		currentMove = (Coord)visitStack.pop();

    		canmove = true;

		}
		else
		{
    		canmove = false;
		}

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

class MyStack<E>
{
	private ArrayList<E> data;	// stores stack data

	public MyStack()
	// Initializes an empty array object
	{
		data = new ArrayList<E>();
	}

	public boolean isEmpty()
	// Returns true if data is empty, false otherwise
	{
		return data.size() == 0;
	}

	public void push (E x)
	// Adds variable x to the top of the stack
	{
		 data.add(x);
	}

	public E pop()
	// Returns and removes the top element from the stack
	{
		if(!data.isEmpty())
			return data.remove((data.size())-1);

		return null;
	}

	public E peek()
	// Returns the top element from the stack without removal
	{
		return (E)data.get((data.size())-1);
	}
}

thank you for your comments. I really appreciate you help
Mahdi

In Topic: BackTracking in a maze

Posted 12 Feb 2012

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
In Topic: BackTracking in a maze

Posted 12 Feb 2012

GregBrannon, 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

In Topic: BackTracking in a maze

Posted 12 Feb 2012

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

In Topic: BackTracking in a maze

Posted 30 Jan 2012

mostyfriedman, 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

My Information

Member Title:: New D.I.C Head
Age:: Age Unknown
Birthday:: Birthday Unknown
Gender:

Contact Information

E-mail:: Private

Friends

skoon hasn't added any friends yet.

Comments

skoon has no profile comments yet. Why not say hello?