Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Java (http://www.programmingforums.org/forum17.html)
-   -   Maze solver w/ stacks. (http://www.programmingforums.org/showthread.php?t=14225)

sbob60 Oct 23rd, 2007 7:13 PM

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:
:

  1. import java.util.ArrayList;
  2.  
  3. public class iStack implements stackInterface
  4. {
  5.         private ArrayList <location> data;//stores object
  6.         private int top;//top of stack
  7.         private int size;//number of objects in stack
  8.  
  9.  
  10.         public iStack()
  11.         {
  12.                 data = new ArrayList();
  13.                 top = -1;
  14.                 size = 0;
  15.         }
  16.  
  17.         public boolean isEmpty()//return true if stack is empty
  18.         {
  19.                 return top == -1;
  20.         }
  21.  
  22.         public void push(Object x)//puts an object into the stack
  23.         {
  24.                 data.add(x);
  25.                 top++;
  26.                 size++;
  27.         }
  28.  
  29.         public Object pop()//removes top object from stack
  30.         {
  31.                 int temp = top;
  32.                 top--;
  33.                 size--;return data.remove(temp);
  34.         }
  35.  
  36.         public Object peekTop()//returns top of stack but doesn't delete
  37.         {
  38.                 return data.get(top);
  39.         }
  40.  
  41.         public int getSize()//returns number of objects in stack
  42.         {
  43.                 return size;
  44.         }
  45. }


I also made a location class that we have to use

:

  1. public class location
  2. {
  3.         private int row;
  4.         private int col;
  5.  
  6.         public location()
  7.         {
  8.                 row = 0;
  9.                 col = 0;
  10.         }//location
  11.  
  12.         public location(int r, int c)
  13.         {
  14.                 row = r;
  15.                 col = c;
  16.         }
  17.  
  18.         public int getRow()
  19.         {
  20.                 return row;
  21.         }//getrow
  22.         public int getCol()
  23.         {
  24.                 return col;
  25.         }//getcol
  26.  
  27.  
  28.         public String toString()
  29.         {       
  30.                 return("(row, col) = ("+ row + ", " + col + ").");
  31.         }//toString
  32.  
  33.         public int compareTo(Object obj)
  34.         {
  35.                 location loc =(location)obj;
  36.                 if (this.row != loc.getRow() ||
  37.                         this.col != loc.getCol())
  38.                         return -1;
  39.                 else
  40.                         return 0;
  41.         }//compareTo
  42. }//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.

:

  1.         int maze[][] = {{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
  2.                                         {0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,0,0},
  3.                                         {0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1},
  4.                                         {0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0},
  5.                                         {0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0},
  6.                                         {0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
  7.                                         {0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
  8.                                         {1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1},
  9.                                         {0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,1},
  10.                                         {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

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.


All times are GMT -5. The time now is 12:49 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC