September 21st, 2015
Using Stacks: Traversing a Maze
Another classic use of a stack data structure is to keep track of alternatives in maze traversal or other similar algorithms that involve trial and error. Suppose that we build a grid as a two-dimensional array of ints where each number represents either a path (1) or a wall (0) in a maze:
private int [][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,0,1,1,0,1,1,1,1,0,0,1},
{1,1,1,1,1,0,1,0,1,0,1,0,0},
{0,0,0,0,1,1,1,0,1,0,1,1,1},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1} };
Our goal is to start in the top-left corner of this grid and traverse to the bottom- right corner of this grid, traversing only positions that are marked as a path. Valid moves will be those that are within the bounds of the grid and are to cells in the grid marked with a 1. We will mark our path as we go by changing the 1’s to 3’s, and we will push only valid moves onto the stack.
Starting in the top-left corner, we have two valid moves: down and right. We push these moves onto the stack, pop the top move off of the stack (right), and then move to that location. This means that we moved right one position:
{3,3,1,0,1,1,0,0,0,1,1,1,1}
{1,0,0,1,1,0,1,1,1,1,0,0,1}
{1,1,1,1,1,0,1,0,1,0,1,0,0}
{0,0,0,0,1,1,1,0,1,0,1,1,1}
{1,1,1,0,1,1,1,0,1,0,1,1,1}
{1,0,1,0,0,0,0,1,1,1,0,0,1}
{1,0,1,1,1,1,1,1,0,1,1,1,1}
{1,0,0,0,0,0,0,0,0,0,0,0,0}
{1,1,1,1,1,1,1,1,1,1,1,1,1}
We now have only one valid move. We push that move onto the stack, pop the top element off of the stack (right), and then move to that location. Again we moved right one position:
{3,3,3,0,1,1,0,0,0,1,1,1,1}
{1,0,0,1,1,0,1,1,1,1,0,0,1}
{1,1,1,1,1,0,1,0,1,0,1,0,0}
{0,0,0,0,1,1,1,0,1,0,1,1,1}
{1,1,1,0,1,1,1,0,1,0,1,1,1}
{1,0,1,0,0,0,0,1,1,1,0,0,1}
{1,0,1,1,1,1,1,1,0,1,1,1,1}
{1,0,0,0,0,0,0,0,0,0,0,0,0}
{1,1,1,1,1,1,1,1,1,1,1,1,1}
From this position, we do not have any valid moves. At this point, however, our stack is not empty. Keep in mind that we still have a valid move on the stack left from the first position. We pop the next (and currently last) element off of the stack (down from the first position). We move to that position, push the valid move(s) from that position onto the stack, and continue processing.
//********************************************************************
// Maze.java Author: Lewis and Chase
//
// Represents a maze of characters. The goal is to get from the
// top left corner to the bottom right, following a path of 1s.
//********************************************************************
import jss2.*;
public class Maze
{
private final int TRIED = 3;
private final int PATH = 7;
private int [][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,0,1,1,0,1,1,1,1,0,0,1},
{1,1,1,1,1,0,1,0,1,0,1,0,0},
{0,0,0,0,1,1,1,0,1,0,1,1,1},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1} };
private StackADT push_new_pos(int x, int y, StackADT stack)
{
Position npos = new Position();
npos.setx(x);
npos.sety(y);
if (valid(npos.getx(),npos.gety()))
stack.push(npos);
return stack;
}
//-----------------------------------------------------------------
// Attempts to iteratively traverse the maze. It inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution. This method uses a
// stack to keep track of the possible moves that could be made.
//-----------------------------------------------------------------
public boolean traverse ()
{
boolean done = false;
Position pos = new Position();
Object dispose;
StackADT stack = new ArrayStack();
stack.push(pos);
while (!(done))
{
pos = stack.pop();
grid[pos.getx()][pos.gety()] = TRIED; // this cell has been tried
if (pos.getx() == grid.length-1 && pos.gety() == grid[0].length-1)
done = true; // the maze is solved
else
{
stack = push_new_pos(pos.getx(),pos.gety() - 1, stack);
stack = push_new_pos(pos.getx(),pos.gety() + 1, stack);
stack = push_new_pos(pos.getx() - 1,pos.gety(), stack);
stack = push_new_pos(pos.getx() + 1,pos.gety(), stack);
}//else
}//while
return done;
}//method traverse
//-----------------------------------------------------------------
// Determines if a specific location is valid.
//-----------------------------------------------------------------
private boolean valid (int row, int column)
{
boolean result = false;
// Check if cell is in the bounds of the matrix
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[row].length)
// Check if cell is not blocked and not previously tried
if (grid[row][column] == 1)
result = true;
return result;
}//method valid
//-----------------------------------------------------------------
// Returns the maze as a string.
//-----------------------------------------------------------------
public String toString ()
{
String result = "\n";
for (int row=0; row < grid.length; row++)
{
for (int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += "\n";
}//for
return result;
}//method toString
}//class Maze
//********************************************************************
// MazeSearch.java Author: Lewis and Chase
//
// Demonstrates a simulation of recursion using a stack.
//********************************************************************
public class MazeSearch
{
//-----------------------------------------------------------------
// Creates a new maze, prints its original form, attempts to
// solve it, and prints out its final form.
//-----------------------------------------------------------------
public static void main (String[] args)
{
Maze labyrinth = new Maze();
System.out.println (labyrinth);
if (labyrinth.traverse ())
System.out.println ("The maze was successfully traversed!");
else
System.out.println ("There is no possible path.");
System.out.println (labyrinth);
}//method main
}//class MazeSearch
Classwork:
Work in pairs to trace the maze solution by showing the stack contents as it is being traverse. Show the values of the array as you step through elements of the array. Remember to change them as defined above.
Heads up: Tomorrow we will be studying Queues.