Programming Forums > Application Development > Java

sbob60 · Oct 23rd, 2007, 7:13 PM

I have to make a maze solver using stacks. We can't use the stacks that come with java, and have to use this:

 java Syntax (Toggle Plain Text) 
import java.util.ArrayList;
 
public class iStack implements stackInterface
{
	private ArrayList <location> data;//stores object
	private int top;//top of stack
	private int size;//number of objects in stack
 
 
	public iStack()
	{
		data = new ArrayList();
		top = -1;
		size = 0;
	}
 
	public boolean isEmpty()//return true if stack is empty
	{
		return top == -1;
	}
 
	public void push(Object x)//puts an object into the stack
	{
		data.add(x);
		top++;
		size++;
	}
 
	public Object pop()//removes top object from stack
	{
		int temp = top;
		top--;
		size--;return data.remove(temp);
	}
 
	public Object peekTop()//returns top of stack but doesn't delete 
	{
		return data.get(top);
	}
 
	public int getSize()//returns number of objects in stack
	{
		return size;
	}
}
import java.util.ArrayList;

public class iStack implements stackInterface
{
	private ArrayList <location> data;//stores object
	private int top;//top of stack
	private int size;//number of objects in stack
	
	
	public iStack()
	{
		data = new ArrayList();
		top = -1;
		size = 0;
	}
	
	public boolean isEmpty()//return true if stack is empty
	{
		return top == -1;
	}
	
	public void push(Object x)//puts an object into the stack
	{
		data.add(x);
		top++;
		size++;
	}
	
	public Object pop()//removes top object from stack
	{
		int temp = top;
		top--;
		size--;return data.remove(temp);
	}
	
	public Object peekTop()//returns top of stack but doesn't delete 
	{
		return data.get(top);
	}
	
	public int getSize()//returns number of objects in stack
	{
		return size;
	}
}

I also made a location class that we have to use

 java Syntax (Toggle Plain Text) 
public class location
{
	private int row;
	private int col;
 
	public location()
	{
		row = 0;
		col = 0;
	}//location
 
	public location(int r, int c)
	{
		row = r;
		col = c;
	}
 
	public int getRow()
	{ 
		return row;
	}//getrow
	public int getCol()
	{ 
		return col; 
	}//getcol
 
 
	public String toString()
	{	
		return("(row, col) = ("+ row + ", " + col + ").");
	}//toString
 
	public int compareTo(Object obj)
	{
		location loc =(location)obj;
		if (this.row != loc.getRow() || 
			this.col != loc.getCol())
			return -1;
		else
			return 0;
	}//compareTo
}//location
public class location
{
	private int row;
	private int col;
	
	public location()
	{
		row = 0;
		col = 0;
	}//location
	
	public location(int r, int c)
	{
		row = r;
		col = c;
	}
	
	public int getRow()
	{ 
		return row;
	}//getrow
	public int getCol()
	{ 
		return col; 
	}//getcol

	
	public String toString()
	{	
		return("(row, col) = ("+ row + ", " + col + ").");
	}//toString
	
	public int compareTo(Object obj)
	{
		location loc =(location)obj;
		if (this.row != loc.getRow() || 
			this.col != loc.getCol())
			return -1;
		else
			return 0;
	}//compareTo
}//location

The part where I am pretty much stuck at is on how to change the board. The main objective here is to have a maze and let the program solve it. It should keep track of its path and record its data and finish the maze. The maze is a 2-d array.

 java Syntax (Toggle Plain Text) 
	int maze[][] = {{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
					{0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,0,0},
					{0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1},
					{0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0},
					{0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0},
					{0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
					{0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
					{1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1},
					{0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,1},
					{0,1,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0}};
	int maze[][] = {{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
					{0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,0,0},
					{0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1},
					{0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0},
					{0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0},
					{0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
					{0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
					{1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1},
					{0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,1},
					{0,1,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0}};

The 0's translates to the paths available and 1's are walls. The stack class above is to be used to get across the maze. I don't want anyone to do it for me, but any guidance would be really appreciated. I'm just really confused on where to start here.

DaWei · Oct 23rd, 2007, 7:32 PM

The use of a stack gives you the ability to reject bad choices back to your latest bad choice. At that point, you choose an alternative path. You may follow that for a while and hit a dead-end again. Then you back up to the choice that lead to the dead-end and make a different choice.

In this way, you will eventually cover every choice. Obviously this will lead (eventually) to a solution (presuming a fair maze).

There are other types of solutions. In a fair maze, if you choose to always go right (or left) at each choice, you will eventually emerge. You may have grown a beard in the process, or you may solve it quickly.

If you want to find the absolutely shortest path, you can treat it as a graph problem and explore every possible path forward from any point in the maze where you currently stand. These paths will either terminate or return to some position you've previously occupied. This doesn't imply less work, it just implies that the maze is definitively solved for shortest path.

You can also choose to make choices entirely randomly. The probability is high, but not certain, that you will reach the goal.

Oct 23rd, 2007, 7:13 PM	#1
sbob60 Newbie Join Date: Oct 2007 Posts: 6 Rep Power: 0	Maze solver w/ stacks. I have to make a maze solver using stacks. We can't use the stacks that come with java, and have to use this: java Syntax (Toggle Plain Text) import java.util.ArrayList; public class iStack implements stackInterface { private ArrayList <location> data;//stores object private int top;//top of stack private int size;//number of objects in stack public iStack() { data = new ArrayList(); top = -1; size = 0; } public boolean isEmpty()//return true if stack is empty { return top == -1; } public void push(Object x)//puts an object into the stack { data.add(x); top++; size++; } public Object pop()//removes top object from stack { int temp = top; top--; size--;return data.remove(temp); } public Object peekTop()//returns top of stack but doesn't delete { return data.get(top); } public int getSize()//returns number of objects in stack { return size; } } import java.util.ArrayList; public class iStack implements stackInterface { private ArrayList <location> data;//stores object private int top;//top of stack private int size;//number of objects in stack public iStack() { data = new ArrayList(); top = -1; size = 0; } public boolean isEmpty()//return true if stack is empty { return top == -1; } public void push(Object x)//puts an object into the stack { data.add(x); top++; size++; } public Object pop()//removes top object from stack { int temp = top; top--; size--;return data.remove(temp); } public Object peekTop()//returns top of stack but doesn't delete { return data.get(top); } public int getSize()//returns number of objects in stack { return size; } } I also made a location class that we have to use java Syntax (Toggle Plain Text) public class location { private int row; private int col; public location() { row = 0; col = 0; }//location public location(int r, int c) { row = r; col = c; } public int getRow() { return row; }//getrow public int getCol() { return col; }//getcol public String toString() { return("(row, col) = ("+ row + ", " + col + ")."); }//toString public int compareTo(Object obj) { location loc =(location)obj; if (this.row != loc.getRow() \|\| this.col != loc.getCol()) return -1; else return 0; }//compareTo }//location public class location { private int row; private int col; public location() { row = 0; col = 0; }//location public location(int r, int c) { row = r; col = c; } public int getRow() { return row; }//getrow public int getCol() { return col; }//getcol public String toString() { return("(row, col) = ("+ row + ", " + col + ")."); }//toString public int compareTo(Object obj) { location loc =(location)obj; if (this.row != loc.getRow() \|\| this.col != loc.getCol()) return -1; else return 0; }//compareTo }//location The part where I am pretty much stuck at is on how to change the board. The main objective here is to have a maze and let the program solve it. It should keep track of its path and record its data and finish the maze. The maze is a 2-d array. java Syntax (Toggle Plain Text) int maze[][] = {{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0}, {0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,0,0}, {0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1}, {0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0}, {0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0}, {0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0}, {1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1}, {0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,1}, {0,1,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0}}; int maze[][] = {{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0}, {0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,0,0}, {0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1}, {0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0}, {0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0}, {0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0}, {1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1}, {0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,1}, {0,1,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0}}; The 0's translates to the paths available and 1's are walls. The stack class above is to be used to get across the maze. I don't want anyone to do it for me, but any guidance would be really appreciated. I'm just really confused on where to start here.

Oct 23rd, 2007, 7:32 PM	#2
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Re: Maze solver w/ stacks. The use of a stack gives you the ability to reject bad choices back to your latest bad choice. At that point, you choose an alternative path. You may follow that for a while and hit a dead-end again. Then you back up to the choice that lead to the dead-end and make a different choice. In this way, you will eventually cover every choice. Obviously this will lead (eventually) to a solution (presuming a fair maze). There are other types of solutions. In a fair maze, if you choose to always go right (or left) at each choice, you will eventually emerge. You may have grown a beard in the process, or you may solve it quickly. If you want to find the absolutely shortest path, you can treat it as a graph problem and explore every possible path forward from any point in the maze where you currently stand. These paths will either terminate or return to some position you've previously occupied. This doesn't imply less work, it just implies that the maze is definitively solved for shortest path. You can also choose to make choices entirely randomly. The probability is high, but not certain, that you will reach the goal. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Recursion Maze Question	afroboy0731	Java	8	Dec 18th, 2006 5:18 AM
Sun Server Stacks.	Indigno	Coder's Corner Lounge	7	Aug 28th, 2006 2:51 PM
Help with maze	jl_7	C++	3	Apr 18th, 2006 7:03 AM
Avoiding Stackoverflow error using recursion to solve a maze	Mjordan2nd	Java	1	Feb 9th, 2006 10:01 PM
Maze generation	thomzor	C++	3	May 25th, 2005 11:51 AM

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Maze solver w/ stacks.