Title: Stack Algorithm Maize
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Stack Algorithm: Maize

A Stack can also be used to solve a Maize

Maize.java


package maize;

import java.awt.Color;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;


class CellLocation
{
    int row=0; int col=0;
    CellLocation()
    {

    }
    CellLocation(int r, int c)
    {
        row=r;
        col = c;
    }
};

enum DIR {East, South, West, North, Nothing};

class Cell
{
    boolean[] holes = new boolean[4];  //East=0, South=1, West=2, North=3

    Cell()
    {

    }

    Cell (Cell c) // copy constructor
    {
        for (int i=0; i < 4; i++)
            holes[i]= c.holes[i];
    }
};

class PathSegment
{
    int row;
    int col;
    DIR currDirection;
    Cell remaining_directions = new Cell();

    PathSegment()
    {

    }
    PathSegment (PathSegment s) // copy constructor
    {
        row = s.row;
        col = s.col;
        currDirection = s.currDirection;
        remaining_directions = new Cell(s.remaining_directions);
    }
};

public class Maize {
    static final int MAIZE_ROWS=20;
    static final int MAIZE_COLS=8;
    CellLocation begin=new CellLocation();
    CellLocation finish=new CellLocation();
    Stack<PathSegment> solution=null; // gets filled in with a call to solve in MaizeSolution

    Cell[][] maizeCells = new Cell[MAIZE_ROWS][MAIZE_COLS];

    public Maize(String filename)
    {
        for (int i=0; i < MAIZE_ROWS; i++)
            for (int j=0;j < MAIZE_COLS; j++)
                maizeCells[i][j] = new Cell();

        if (filename != null)
            readInFile(filename);

    }
    private void readInFile(String filename)
    {
        Scanner infile = null;


        try {
            infile = new Scanner(new File(filename));
        } catch (FileNotFoundException e) {

            e.printStackTrace();
            return;
        }
        int rows = infile.nextInt();
        int cols = infile.nextInt();
        System.out.println(" File contains rows=" + rows + " cols=" + cols);
        if (rows != MAIZE_ROWS || cols != MAIZE_COLS)
            throw new RuntimeException("file row/col size mismatch with MAIZE_ROWS and MAIZE_COLS");

        begin.row = infile.nextInt();
        begin.col = infile.nextInt();

        finish.row = infile.nextInt();
        finish.col = infile.nextInt();

        System.out.println(" begin =" + begin.row +" " + begin.col + " finish="  +finish.row + " " + finish.col );

        for (int row=0; row < MAIZE_ROWS; row++)
        {
            for (int col=0; col < MAIZE_COLS; col++)
            {
                String str;
                if (!infile.hasNext()) throw new RuntimeException("file doesn't contain enough data");
                str = infile.next();
                for (int direction=0; direction < 4; direction++)
                {
                    boolean value;
                    if (str.charAt(direction)=='T') value=true;
                    else value=false;
                    maizeCells[row][col].holes[direction]=value;

                }
            }
        }
        infile.close();
    }
	
    private ArrayList<PathSegment> convert(Stack<PathSegment> stack)
    {
        if (stack == null)
            return null;
        Stack<PathSegment> temp = (Stack<PathSegment>)stack.clone();
        ArrayList<PathSegment> arr = new ArrayList<PathSegment>();
        // Get solution into a Vector for easier access
        while(temp.size() > 0)
        {
            arr.add(temp.peek());
            temp.pop();
        }
        return arr;
    }
	
    void print_solution(Graphics g,
            int xStart, int yStart, int totalWidth, int totalHeight,
            int maxAscent, int letterHeight, int letterWidth)
    {
        ArrayList<PathSegment> varr = convert(solution);
        int diameter = 4;
        Color circleColor = Color.blue;
        Color lineColor = Color.black;
        Color pathColor = Color.red;
        int width = totalWidth/MAIZE_COLS;
        int height = totalHeight/MAIZE_ROWS;

        /*  Before calling print_solution, we expect something like:
         *
        FontMetrics fontMetrics = getFontMetrics(getFont())
        int maxAscent = fontMetrics.getMaxAscent();
        int letterHeight = fontMetrics.getHeight();
        int letterWidth = fontMetrics.stringWidth("W");
         */

        for (int row=0; row < MAIZE_ROWS; row++)
        {
            int y = yStart + row*height;
            int x = xStart;
            // Print Top of each cell of the Maize
            for (int col=0; col < MAIZE_COLS; col++)
            {
                x = xStart + col*width;
                g.setColor(circleColor);
                g.drawOval(x-diameter/2, y-diameter/2, diameter, diameter);
                if (!maizeCells[row][col].holes[DIR.North.ordinal()])
                {
                    g.setColor(lineColor);
                    g.drawLine(x,y, x + width, y);
                }
            }
            g.setColor(circleColor);
            g.drawOval(x+width-diameter/2, y-diameter/2, diameter, diameter);

            // Print the E/W sides '|' character.  Also place marker for solution:
            // 'B' is the start of the path., 'F' is the finish, 'X' is an other point on the path.
            for (int col=0; col < MAIZE_COLS; col++)
            {
                x = xStart + col*width;
                if (!maizeCells[row][col].holes[DIR.West.ordinal()])
                {
                    g.setColor(lineColor);
                    g.drawLine(x,y, x , y + height);
                }
                g.setColor(pathColor);

                g.drawString(""+print_solution_char(varr, row, col),
                        x+width/2 - letterWidth/2, y+height/2-letterHeight/2+maxAscent);

                if (col == MAIZE_COLS-1 && !maizeCells[row][col].holes[DIR.East.ordinal()])
                {
                    g.setColor(lineColor);
                    g.drawLine(x+width, y, x+width , y + height);
                }
            }

            // The South sides of the last cells.
            if (row == MAIZE_ROWS-1)
            {
                y += height;
                for (int col=0; col < MAIZE_COLS; col++)
                {
                    x = xStart + col*width;
                    g.setColor(circleColor);
                    g.drawOval(x-diameter/2, y-diameter/2, diameter, diameter);
                    if (!maizeCells[row][col].holes[DIR.South.ordinal()])
                    {
                        g.setColor(lineColor);
                        g.drawLine(x,y, x + width, y);
                    }
                }
                g.setColor(circleColor);
                g.drawOval(x+width-diameter/2, y-diameter/2, diameter, diameter);
            }
        }
    }
	
    void print_solution()
    {
        ArrayList<PathSegment> varr = convert(solution);
        System.out.println( "Maize Solution:");


        for (int row=0; row < MAIZE_ROWS; row++)
        {
            // Print Top of each cell of the Maize
            for (int col=0; col < MAIZE_COLS; col++)
            {
                if (maizeCells[row][col].holes[DIR.North.ordinal()])
                    System.out.print( ".   ");
                else
                    System.out.print(  ".___");
            }
            System.out.println( ".");

            // Print the E/W sides '|' character.  Also place marker for solution:
            // 'B' is the start of the path., 'F' is the finish, 'X' is an other point on the path.
            for (int col=0; col < MAIZE_COLS; col++)
            {
                if (maizeCells[row][col].holes[DIR.West.ordinal()])
                    System.out.print(  "  ");
                else
                    System.out.print(  "| ");

                System.out.print( ""+ print_solution_char(varr, row, col) + ' ');

                if (col == MAIZE_COLS-1 && !maizeCells[row][col].holes[DIR.East.ordinal()])
                    System.out.print( "|");
            }
            System.out.println();

            // The South sides of the last cells.
            if (row == MAIZE_ROWS-1)
            {
                for (int col=0; col < MAIZE_COLS; col++)
                {
                    if (maizeCells[row][col].holes[DIR.South.ordinal()])
                        System.out.print(  ".   ");
                    else
                        System.out.print(  ".___");
                }
                System.out.print(  ".");
            }
        }
        System.out.println();
        System.out.println();

    }

    private char print_solution_char(ArrayList<PathSegment> varr, int row, int col)
    {
        if (varr == null)
            return ' ';

        for (int index=0; index < varr.size(); index++)
        {
            PathSegment seg = varr.get(index);
            if (row == seg.row && col == seg.col)
            {
                if (index ==0) return 'F'; // finish path char
                if (index == varr.size()-1) return 'B'; // Begin path char
                switch(seg.currDirection)
                {
                case North:
                    return 'N';
                case East:
                    return 'E';
                case South:
                    return 'S';
                case West:
                    return 'W';
                default:
                    return 'X'; // shouldn't happen
                }

            }
        }
        return ' ';
    }
}



Stepper.java Interface


package maize;

public interface Stepper {
    public void step();
}


Solving a Maize

This code can read in a Maize file and print out a solution.

MaizeSolution.java


package maize;

import java.util.ArrayList;
import java.util.Stack;


public class MaizeSolution extends Maize{
    boolean traversed[][] = new boolean[Maize.MAIZE_ROWS][Maize.MAIZE_COLS];

    public MaizeSolution(String filename)
    {
        super(filename);

    }

    public boolean solve(boolean printSolution, Stepper stepper)
    {
        for (int i=0; i < Maize.MAIZE_ROWS; i++)
        {
            for (int j=0; j < Maize.MAIZE_COLS; j++)
            {
                traversed[i][j] = false;
            }
        }
        solution = new Stack<PathSegment>();
        solution.push( getBeginningSegment());

        while (!isFinish(solution.peek().row, solution.peek().col))
        {
            PathSegment next=getNextSegment(solution.peek());
            if (next != null)
                solution.push(next);
            else
            {
                // need to backtrack
                //  I used to think I needed this, but I think its much faster without
                //traversed[solution.top().row][ solution.top().col] = false;
                solution.pop();
                if (solution.size() == 0)
                {
                    return false; // Failed to find a path.
                }
            }
            // The following gives us the option to single step through the solution
            if (stepper != null)
                stepper.step();
        }
        if (printSolution)
        {
            print_solution();
        }


        return true;
    }

    PathSegment getNextSegment(PathSegment  s)
    {
        // Depending on where we our current Maize location is and the Finish is,
        //    there is a preferred direction that I would like to go:

        DIR[][] preferredDirection={
                {DIR.East,DIR.South,DIR.North,DIR.West},
                {DIR.East,DIR.North,DIR.South,DIR.West},
                {DIR.West,DIR.South,DIR.North,DIR.East},
                {DIR.West,DIR.North,DIR.South,DIR.East},
                {DIR.South,DIR.East,DIR.West,DIR.North},
                {DIR.North,DIR.East,DIR.West,DIR.South},
                {DIR.South,DIR.West,DIR.East,DIR.North},
                {DIR.North,DIR.West,DIR.East,DIR.South}
        };
        int prefIndex = lookAhead(s);
        PathSegment next = null;

        for (int dir=0; dir < 4; dir++)
        {
            DIR direction = preferredDirection[prefIndex][dir];
            if (s.remaining_directions.holes[direction.ordinal()] )
            {
                s.remaining_directions.holes[direction.ordinal()]=false; // mark this direction as tried
                s.currDirection=direction;
                next = new PathSegment(s); // start with a copy of where we are and allow buildNext to move to the right cell.
                if (buildNext( next, direction))
                {
                    return next;
                }

            }
        }
        return null;

    }

    private boolean buildNext(PathSegment  next, DIR direction)
    {
        switch(direction)
        {
        case North:
            if (next.row == 0) return false;
            next.row -= 1;
            break;
        case East:
            if (next.col >= Maize.MAIZE_COLS-1) return false;
            next.col +=1;
            break;
        case South:
            if (next.row >= Maize.MAIZE_ROWS-1) return false;
            next.row +=1;
            break;
        case West:
            if (next.col == 0) return false;
            next.col -= 1;
            break;
        }
        if (traversed[next.row][next.col]) return false;  // ALready traversed ... don't want loops.

        traversed[next.row][next.col] = true;
        next.remaining_directions = new Cell(maizeCells[next.row][next.col]);

        return true;
    }

    private int lookAhead(PathSegment  s)
    {
        int deltaEW = finish.col - s.col;
        int deltaSN = finish.row - s.row;
        int index=0;

        // default: {E,S,W,N}
        if (Math.abs(deltaEW) < Math.abs(deltaSN))
        {
            index +=4;
        }
        if (deltaEW < 0) index +=2;
        if (deltaSN < 0) index += 1;
        return index;

    }



    private boolean isFinish(int row, int col)
    {
        if (row==finish.row && col==finish.col) return true;
        else return false;
    }
    private PathSegment getBeginningSegment()
    {
        traversed[begin.row][begin.col] = true;
        PathSegment s=new PathSegment();
        s.row=begin.row;
        s.col=begin.col;
        s.remaining_directions = new Cell(maizeCells[begin.row][begin.col]);
        return s;
    }
    public static void main(String[] args)
    {
        MaizeSolution ms = new MaizeSolution("newMaize.txt");
        ms.solve(true,null);
    }

}




MaizeCreation.java

This program uses the MaizeSolution class to create Maize files.


package maize;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;


public class MaizeCreation extends MaizeSolution{
    int holeCount =0;

    MaizeCreation(CellLocation begin, CellLocation finish)
    {
        super(null); // Don't read in file
        for (int i=0; i < MAIZE_ROWS; i++)
            for (int j=0;j < MAIZE_COLS; j++)
            {
                for (int direction=0; direction < 4; direction++)
                {
                    maizeCells[i][j].holes[direction] = false;
                }
            }

        this.begin = begin;
        this.finish = finish;

        createHoles();
    }
    MaizeCreation()
    {
        this(new CellLocation(0,0), new CellLocation(MAIZE_ROWS-1, MAIZE_COLS-1));
    }

    private void createHoles()
    {
        Random rand = new Random();
        boolean path_found=false;

        // It's helpful to create at least one hole for the begin and finish points
        // While we are at it, we also create a boundary hole to allow path to escape.
        punchEntranceHole(begin);
        punchEntranceHole(finish);
		
        DIR[] values = DIR.values();

        do
        {
            int row= rand.nextInt(MAIZE_ROWS);
            int col= rand.nextInt(MAIZE_COLS);
            DIR direction = values[rand.nextInt(4)];  // want one of the first 4 values (not Nothing)

            // Don't punch additional boundary holes
            if (row==0 && direction==DIR.North) continue;
            if (col==0 && direction==DIR.West) continue;
            if (col==MAIZE_COLS-1 && direction==DIR.West) continue;
            if (row==MAIZE_ROWS-1 && direction==DIR.South) continue;

            if (punchHole(row, col, direction))
                continue; // Hole already punched ... try new random #'s



            path_found= solve(false, null);


            if (!path_found)
                createFile("notSolvable.txt"); // Print the last unsolvable maize
        } while(!path_found);


    }
    private void punchEntranceHole(CellLocation entrance)
    {
        DIR dir1=DIR.Nothing, dir2=DIR.Nothing;
        if (entrance.col == 0)
        {
            dir1= DIR.West; dir2=DIR.East;
        }
        else if (entrance.col == MAIZE_COLS-1)
        {
            dir1=DIR.West; dir2=DIR.East;
        }
        else if (entrance.row == 0)
        {
            dir1=DIR.North; dir2=DIR.South;
        }
        else if (entrance.row == MAIZE_ROWS -1)
        {
            dir1=DIR.North; dir2=DIR.South;
        }
        if (dir1 != DIR.Nothing && dir2 != DIR.Nothing)
        {
            punchHole(entrance.row, entrance.col, dir1);
            punchHole(entrance.row, entrance.col, dir2);
        }
    }
    private boolean punchHole(int row, int col, DIR direction)
    {
        if (maizeCells[row][col].holes[direction.ordinal()])
            return true; // Hole already punched

        holeCount+=1;
        System.out.println( "Punch hole(" + holeCount + ") row=" + row + " col=" + col + " dir="+ direction);
        maizeCells[row][col].holes[direction.ordinal()] = true;

        // Need to mark the hole available on the adjacent cell
        switch(direction)
        {
        case North:
            if (row > 0)
                maizeCells[row-1][col].holes[DIR.South.ordinal()] = true;
            break;
        case East:
            if (col < MAIZE_COLS-1)
                maizeCells[row][col+1].holes[DIR.West.ordinal()] = true;
            break;
        case South:
            if (row < MAIZE_ROWS-1)
                maizeCells[row+1][col].holes[DIR.North.ordinal()] = true;
            break;
        case West:
            if (col > 0)
                maizeCells[row][col-1].holes[DIR.East.ordinal()] = true;
            break;
        }
        return false; // new hole
    }

    void createFile(String filename)
    {
        PrintStream ps=null;
        try {
            ps = new PrintStream ( new File(filename));
        } catch (FileNotFoundException e) {
            System.out.println("I don't think this should happen");
            e.printStackTrace();
            return;
        }
        System.out.println(filename + " written");
        ps.println(MAIZE_ROWS + " " + MAIZE_COLS);
        ps.println(begin.row + " " + begin.col + " " + finish.row + " " + finish.col);

        for (int row=0; row < MAIZE_ROWS; row++)
        {
            for (int col=0; col < MAIZE_COLS; col++)
            {
                for (int direction=0; direction < 4; direction++)
                {
                    if (maizeCells[row][col].holes[direction])
                        ps.print('T');
                    else
                        ps.print('F');
                }
                ps.print( ' ');
            }
            ps.println();
        }
        ps.close();
    }
    public static void main(String[] args)
    {
        MaizeCreation mc = new MaizeCreation();
        System.out.println("Finished creating Maize solution .... now try to solve it");
        mc.createFile("newMaize.txt");

        MaizeSolution ms = new MaizeSolution("newMaize.txt");
        ms.solve(true, null);
    }



}



DrawMaize.java

This program draws a Maize solution solution in progress (in slow motion)


package maize;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;

import javax.swing.JFrame;


public class DrawMaize extends JFrame implements Stepper, Runnable {
    MaizeSolution ms = new MaizeSolution("newMaize.txt");

    class Solver extends Thread
    {
        public void run()
        {
            ms.solve(true, DrawMaize.this);
        }
    }

    public synchronized void  step()
    {
        try {
            wait();
        } catch (InterruptedException e) {}
    }
    public synchronized void singleStep()
    {
        notify(); // Wake up calls on step method
    }
    public void run()
    {
        while (true)
        {
            try {
                Thread.sleep(1000);
                singleStep();
                repaint();
            } catch (InterruptedException e) {}
        }
    }

    DrawMaize()
    {
        super("Drawing Maize");
        setSize(800, 800);
        setDefaultCloseOperation(EXIT_ON_CLOSE);
		
        Thread t = new Thread(this);
        t.start();

        Thread t2 = new Solver();
        t2.start();

        setVisible(true);
    }
    public void paint(Graphics g)
    {
        Dimension d = getSize();
        g.setColor(Color.white);
        g.fillRect(0,0, d.width, d.height);
        int pad = 50;
        Font font = getFont();
        FontMetrics fontMetrics = getFontMetrics(font);
        int maxAscent = fontMetrics.getMaxAscent();
        int letterHeight = fontMetrics.getHeight();
        int letterWidth = fontMetrics.stringWidth("W");
        ms.print_solution(g, pad/*xStart*/, pad/*yStart*/,
                d.width-2*pad, d.height-2*pad, maxAscent, letterHeight, letterWidth);
    }

    public static void main(String[] args) {
        DrawMaize dm = new DrawMaize();

    }

}



Last Updated: November 19, 2013 1:54 AM