July Newsletter Puzzle (Maze Solver)

[Jason Menard]

This month's puzzle is courtesy of Jim Yingst.


Maze Solver


Given an input ascii representation of a maze, write a program to find and
display a path from the start point of the maze to the end point of the maze.
The output should be a textual representation of the path through the maze from
start to finish. It is suggested to use a series of '.' (period) symbols to
indicate the path through the maze.


Notes:

• No diagonal moves are allowed.
• For an extra challenge, if there are multiple paths from start to finish,

find the path leading to the shortest solution.



Legend
O	Start
X	Finish
+	Wall



Maze #1

<pre>+++++++++++++++
+ + + + +
+ + + + + +
+ +++ +++++ + +
O + +++ X
+++ +++++ +++
+ + +++ + +
+ + + +
+++++++++++++++</pre>

Maze #2

<pre>+++++++++++++++++++++++++
+ + +
+ +++++++ + + +++++++++ +
+ + + + + +
+ +++++ +++ + +++ +++ + +
+ + + + + + + + +
+++ + + + + +++ +++ + + +
+ +O + + + +X + +
+ +++++ + + +++++ +++++++
+ + + + + +
+++++ + +++ + + + + +++ +
+ + + + + + + +
+ +++ + +++++ + +++++ +++
+ + + +
+++++++++++++++++++++++++</pre>

 

[Stan James]

This is serious brute force:

 package com.saxman.sandbox;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
/**
 * This class reads mazes from a file and displays their solutions.
 */
public class Amazing
{
   private MazeSolver mSolver = new MazeSolver();
   public Amazing()
   {
   }
   
   private void readFile( String aFileName )
   throws Exception
   {
      List lMazes = getMazes( aFileName );
      solveMazes( lMazes );
   }
   
   public List getMazes( String aFileName )
   throws Exception
   {
      System.out.println( "Amazing.getMazes FileName=" + aFileName );
      BufferedReader lReader = new BufferedReader( new FileReader( aFileName ) );
      String lLine;
      List lMazes = new LinkedList();
      Maze lMaze  = new Maze(); // this instance is a throwaway primer
      while ( true )
      {
         lLine = lReader.readLine();        
         if ( null == lLine ) 
            break;
         else
         if ( lLine.startsWith( "Maze" ) )
         {
            lMaze.loadCells();
            lMaze = new Maze();
            lMazes.add( lMaze );
            lMaze.mName = lLine;
            System.out.println( "Amazing.getMazes " + lMaze.mName );
         }
         else
            lMaze.add( lLine );
      }
      lMaze.loadCells();
      lReader.close();
      return lMazes;
   }
   
   private void solveMazes( List aMazes )
   throws Exception 
   {
      Iterator lIter = aMazes.iterator();
      while ( lIter.hasNext() )
      {
         Maze lMaze = (Maze)lIter.next();
         Maze lSolution = mSolver.solveMaze(lMaze);
         lSolution.display();
      }
   }
   
   /** Command line arguments are names of files containing maze puzzles */
   static public void main( String[] args )
   throws Exception
   {
      Amazing instance = new Amazing();
      for ( int i = 0; i < args.length; i++ )
      {
         instance.readFile( args[i] );
      }
   }
   
   /**
    * This class represents one Maze
    */
   private class Maze
   {
      public String   mName = "uninitialized";
      public char[][] mCell;
      public int mRows;
      public int mCols;
      private List mLines = new LinkedList(); 
      private int mLen = 0;
      
      public Maze()
      {}
      
      /** Copy constructor */
      public Maze( Maze aMaze )
      {
         mLen  = aMaze.mLen;
         mName = aMaze.mName;
         mRows = aMaze.mRows;
         mCols = aMaze.mCols;
         mCell = new char[mRows][mCols];
         for ( int r = 0; r < mRows; r++ )
            for ( int c = 0; c < mCols; c++ )
               mCell[r][c] = aMaze.mCell[r][c];
      }
      
      public void add( String aLine )
      {
         if ( aLine.length() > 0 ) // ignore blanks between puzzles
            mLines.add( aLine );  
      }
      
      public void loadCells()
      throws Exception 
      {
         if ( mName.equals( "uninitialized" ) )
            return;
         Object[] lLines = mLines.toArray();
         mRows = lLines.length;
         if ( mRows == 0 ) 
            throw new Exception( "Maze.loadCells Name=" + mName + " Lines=0" );
         String lLine = (String)lLines[0];
         mCols = lLine.length();
         mCell = new char[mRows][mCols];
         for ( int i = 0; i < mRows; i++ )
         {
            lLine = (String)lLines[i];
            mCell[i] = lLine.toCharArray();
         }
      }
      
      public void display()
      {
         System.out.println("Maze Name=" + mName + " Solution length=" + ( mLen == 0 ? "no solution": ""+ mLen ) );
         for ( int r = 0; r < mRows; r++ )
            System.out.println( new String( mCell[r] ));
      }
   }
   
   /**
    * This class solves a Maze puzzle by brute force and returns the shortest solution.
    */
   private class MazeSolver
   {
      Maze mMaze;
      private int ColStart;
      private int RowStart;
      private int ColEnd;
      private int RowEnd;
      private Maze mSolution;
      
      public Maze solveMaze( Maze aMaze )
      throws Exception 
      {      
         System.out.println("MazeSolver.solveMaze " + aMaze.mName );
         mMaze = aMaze;
         mSolution = new Maze( aMaze ); // this instance is a throway primer
         mSolution.mLen = 0;
         findStart( );
         tryCell( RowStart, ColStart, 0 );
         return mSolution;
      }
      
      private void findStart( )
      throws Exception
      {
         for ( int r = 0; r < mMaze.mRows; r++ )
         {
            for ( int c = 0; c < mMaze.mCols; c++ )
            {
               if ( mMaze.mCell[r][c] == 'O' )
               {
                  ColStart = c;
                  RowStart = r;
                  return;
               }
            }
         }
         throw new Exception("MazeSolver.findStart Maze=" + mMaze.mName + " Start not found" );
      }
      
      private void tryCell( int aRow, int aCol, int aLength )
      {
         if ( ( aRow < 0 ) | ( aCol < 0 ) | ( aRow > mMaze.mRows ) | ( aCol > mMaze.mCols ) )
            return;
         if ( mMaze.mCell[aRow][aCol] == 'X' )
         {
            saveSuccess( aLength );
            return;
         }
         if ( ( mMaze.mCell[aRow][aCol] == ' ' ) | ( mMaze.mCell[aRow][aCol] == 'O' ) )
         {
            char lWas = mMaze.mCell[aRow][aCol];
            if ( lWas != 'O' ) 
               mMaze.mCell[aRow][aCol] = '.';   // leave breadcrumbs
            tryCell( aRow-1, aCol, aLength+1 ); // up
            tryCell( aRow+1, aCol, aLength+1 ); // down
            tryCell( aRow, aCol-1, aLength+1 ); // left
            tryCell( aRow, aCol+1, aLength+1 ); // right
            mMaze.mCell[aRow][aCol] = lWas;     // eat breadcrumbs. Yum!
         }
      }
      
      private void saveSuccess( int aLength )
      {
         System.out.println("Solution found in " + aLength + " moves");
         if ( ( mSolution.mLen == 0 ) | ( mSolution.mLen > aLength ) )
         {
            mSolution = new Maze( mMaze );
            mSolution.mLen = aLength;
         }
      }
   }
} 

Here is the file I ran it against:

Maze #1
+++++++++++++++
+   +   +   + +
+ + + +   +   +
+ +++ +++++ + +
O     +   +++ X
+++ +++++   +++
+ +     +++ + +
+   + +       +
+++++++++++++++
Maze #2
+++++++++++++++++++++++++
+         +             +
+ +++++++ + + +++++++++ +
+       +   +   +     + +
+ +++++ +++ + +++ +++ + +
+   + + +   + +   +   + +
+++ + + + + +++ +++ + + +
+   +O  + +   + +X  +   +
+ +++++ + + +++++ +++++++
+     +   +   +   +     +
+++++ + +++ + + + + +++ +
+   +   +   + + +   +   +
+ +++ + +++++ + +++++ +++
+     +   +             +
+++++++++++++++++++++++++

Maze #3
+++++++++++++++++++++++++
+         +             +
+ +++++++ + + +++++++++ +
+       +   +   +     + +
+ +++++++++ + +++ +++ + +
+   + + +   + +   +   + +
+++ + + + + +++ +++ + + +
+   +O  + +   + +X  +   +
+ +++++++ + +++++ +++++++
+     +   +   +   +     +
+++++ + +++ + + + + +++ +
+   +   +   + + +   +   +
+ +++ + +++++ + +++++ +++
+     +   +             +
+++++++++++++++++++++++++

For results

Amazing.getMazes FileName=c:/temp/maze.dat
Amazing.getMazes Maze #1
Amazing.getMazes Maze #2
Amazing.getMazes Maze #3
MazeSolver.solveMaze Maze #1
Solution found in 22 moves
Maze Name=Maze #1 Solution length=22
+++++++++++++++
+   +...+...+ +
+ + +.+...+...+
+ +++.+++++ +.+
O.....+   +++.X
+++ +++++   +++
+ +     +++ + +
+   + +       +
+++++++++++++++
MazeSolver.solveMaze Maze #2
Solution found in 58 moves
Solution found in 50 moves
Solution found in 66 moves
Solution found in 74 moves
Solution found in 62 moves
Solution found in 78 moves
Solution found in 70 moves
Solution found in 62 moves
Solution found in 78 moves
Solution found in 46 moves
Solution found in 34 moves
Solution found in 50 moves
Solution found in 56 moves
Solution found in 48 moves
Solution found in 64 moves
Solution found in 72 moves
Solution found in 60 moves
Solution found in 76 moves
Solution found in 68 moves
Solution found in 60 moves
Solution found in 76 moves
Solution found in 44 moves
Solution found in 32 moves
Solution found in 48 moves
Maze Name=Maze #2 Solution length=32
+++++++++++++++++++++++++
+         +             +
+ +++++++ + + +++++++++ +
+       +   +   +     + +
+ +++++ +++ + +++ +++ + +
+   + + +...+ +   +   + +
+++ + + +.+.+++ +++ + + +
+   +O..+.+.  + +X  +   +
+ +++++.+.+.+++++.+++++++
+     +...+...+...+     +
+++++ + +++ +.+.+ + +++ +
+   +   +   +.+.+   +   +
+ +++ + +++++.+.+++++ +++
+     +   +  ...        +
+++++++++++++++++++++++++
MazeSolver.solveMaze Maze #3
Maze Name=Maze #3 Solution length=no solution
+++++++++++++++++++++++++
+         +             +
+ +++++++ + + +++++++++ +
+       +   +   +     + +
+ +++++++++ + +++ +++ + +
+   + + +   + +   +   + +
+++ + + + + +++ +++ + + +
+   +O  + +   + +X  +   +
+ +++++++ + +++++ +++++++
+     +   +   +   +     +
+++++ + +++ + + + + +++ +
+   +   +   + + +   +   +
+ +++ + +++++ + +++++ +++
+     +   +             +
+++++++++++++++++++++++++

[Michael Dunn]

Not really sure this is the way you want an answer, but here goes anyway (actually this is a bit similar to the word & knights tour puzzles)

class Maze
{
  private static String mazeBoard[][] = {{
  "+","+","+","+","+","+","+","+","+","+","+","+","+","+","+",
  "+"," "," "," ","+"," "," "," ","+"," "," "," ","+"," ","+",
  "+"," ","+"," ","+"," ","+"," "," "," ","+"," "," "," ","+",
  "+"," ","+","+","+"," ","+","+","+","+","+"," ","+"," ","+",
  "O"," "," "," "," "," ","+"," "," "," ","+","+","+"," ","X",
  "+","+","+"," ","+","+","+","+","+"," "," "," ","+","+","+",
  "+"," ","+"," "," "," "," "," ","+","+","+"," ","+"," ","+",
  "+"," "," "," ","+"," ","+"," "," "," "," "," "," "," ","+",
  "+","+","+","+","+","+","+","+","+","+","+","+","+","+","+"},{
  "+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+",
  "+"," "," "," "," "," "," "," "," "," ","+"," "," "," "," "," "," "," "," "," "," "," "," "," ","+",
  "+"," ","+","+","+","+","+","+","+"," ","+"," ","+"," ","+","+","+","+","+","+","+","+","+"," ","+",
  "+"," "," "," "," "," "," "," ","+"," "," "," ","+"," "," "," ","+"," "," "," "," "," ","+"," ","+",
  "+"," ","+","+","+","+","+"," ","+","+","+"," ","+"," ","+","+","+"," ","+","+","+"," ","+"," ","+",
  "+"," "," "," ","+"," ","+"," ","+"," "," "," ","+"," ","+"," "," "," ","+"," "," "," ","+"," ","+",
  "+","+","+"," ","+"," ","+"," ","+"," ","+"," ","+","+","+"," ","+","+","+"," ","+"," ","+"," ","+",
  "+"," "," "," ","+","O"," "," ","+"," ","+"," "," "," ","+"," ","+","X"," "," ","+"," "," "," ","+",
  "+"," ","+","+","+","+","+"," ","+"," ","+"," ","+","+","+","+","+"," ","+","+","+","+","+","+","+",
  "+"," "," "," "," "," ","+"," "," "," ","+"," "," "," ","+"," "," "," ","+"," "," "," "," "," ","+",
  "+","+","+","+","+"," ","+"," ","+","+","+"," ","+"," ","+"," ","+"," ","+"," ","+","+","+"," ","+",
  "+"," "," "," ","+"," "," "," ","+"," "," "," ","+"," ","+"," ","+"," "," "," ","+"," "," "," ","+",
  "+"," ","+","+","+"," ","+"," ","+","+","+","+","+"," ","+"," ","+","+","+","+","+"," ","+","+","+",
  "+"," "," "," "," "," ","+"," "," "," ","+"," "," "," "," "," "," "," "," "," "," "," "," "," ","+",
  "+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+"}};
  private static int boardWidth[] = {15,25};
  private static int directions[] = {-0,-1,1,0};
  private static String solutions[] = new String[100];
  private static int solutionCtr = 0;
  public static void main(String args[])
  {
    printBoard(0,boardWidth[0]);
    System.out.println();
    printBoard(1,boardWidth[1]);
    int startNum[] = {60,180};
    for(int i = 0; i < mazeBoard.length;i++)
    {
      solutionCtr = 0;
      directions[0] = -boardWidth[i];
      directions[3] = boardWidth[i];
      findSolution(i,startNum[i],",");
      String shortest = shortSolution();
      System.out.println("Solutions found = "+ solutionCtr + "\nshortest = " +shortest);
    }
    System.exit(0);
  }
  private static void printBoard(int num, int width)
  {
    for(int i = 0; i < mazeBoard[num].length; i++)
    {
      System.out.print(mazeBoard[num][i]);
      if((i+1)%width == 0) System.out.println();
    }
  }
  private static String shortSolution()
  {
    int shortNum = solutions[0].length();
    int shortIndexNum = 0;
    int checkNum;
    String temp = "";
    for(int i = 0; i < solutionCtr; i++)
    {
      temp = solutions[i].replaceAll(",","");
      checkNum = solutions[i].length()-temp.length();
      if(checkNum < shortNum)
      {
        shortNum = checkNum;
        shortIndexNum = i;
      }
    }
    return solutions[shortIndexNum];
  }
  private static void findSolution(int dim, int currentPos, String moveList)
  {
    moveList += currentPos+",";
    if(mazeBoard[dim][currentPos].equals("X"))
    {
      solutions[solutionCtr] = moveList.substring(1,moveList.length()-1);
      solutionCtr++;
      return;
    }
    else
    {
      for(int i = 0; i < directions.length; i++)
      {
        int nextPos = currentPos + directions[i];
        if(nextPos >= 0 && nextPos < mazeBoard[dim].length &&
           Math.abs(currentPos % boardWidth[dim] - nextPos % boardWidth[dim])<=1 &&
           !mazeBoard[dim][nextPos].equals("+") &&
           moveList.indexOf("," + nextPos + ",") < 0)
        {
          findSolution(dim,nextPos, moveList);
        }
      }
    }
  }
}

[Roy Tock]

My solution is non-recursive and breadth-first. It could use some polish, but it's getting REALLY late :-)
MazeSolver.java

import java.io.IOException;
/**
 * @author Roy Tock
 */
public class MazeSolver {
    public static void main(String[] args) throws IOException {
        Maze theMaze = new Maze(args[0]);
        System.out.println( theMaze );
        System.out.println( "Shortest path through maze in file " + args[0] );
        Path shortestPath = theMaze.shortestPath();
        if (shortestPath != null)
        {
            System.out.println(shortestPath);
            System.out.println(theMaze.toString(shortestPath));
        }
        else
        {
            System.out.println("There is no path through the maze.");
        }
    }
}

Maze.java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
 * @author Roy Tock
 *
 */
public class Maze extends Graph {
    private MyPoint startPoint;
    private MyPoint endPoint;
    public Maze(String fileName) throws IOException {
        int currentLineNum = 0;
        int currentCharNum = 0;
        File mazeFile = new File(fileName);
        BufferedReader bfr = new BufferedReader(new FileReader(mazeFile));
        int mazeChar;
        // Load the vertices
        while ((mazeChar = bfr.read()) > 0) {
            switch (mazeChar) {
                case '\n' :
                    {
                        // end of line; increment current line number
                        currentLineNum++;
                        currentCharNum = 0;
                        break;
                    }
                case ' ' :
                    {
                        // vertex
                        addVertex(
                            new Vertex(
                                new MyPoint(currentCharNum, currentLineNum)));
                        currentCharNum++;
                        break;
                    }
                case 'O' :
                    {
                        // starting vertex
                        startPoint =
                            new MyPoint(currentCharNum, currentLineNum);
                        addVertex(new Vertex(startPoint));
                        currentCharNum++;
                        break;
                    }
                case 'X' :
                    {
                        // ending vertex
                        endPoint = new MyPoint(currentCharNum, currentLineNum);
                        addVertex(new Vertex(endPoint));
                        currentCharNum++;
                        break;
                    }
                    //including '+'
                default :
                    {
                        // no vertex
                        currentCharNum++;
                        break;
                    }
            }
        }
        if (startPoint == null) {
            throw new IllegalArgumentException(
                "No start point in maze file " + fileName + ".");
        } else if (endPoint == null) {
            throw new IllegalArgumentException(
                "No end point in maze file " + fileName + ".");
        }
        /*
         * Load the edges.  We do it by looking at each vertex in the graph.  If there
         * is another vertex immediately south or immediately east, then we add a vertex.
         * We don't need to check north, because the vertex just north of this one will
         * have already added an edge.  Same for checking west.
         */
        Set vertices = vertices();
        Iterator vertexIterator = vertices.iterator();
        Vertex currentVertex;
        Vertex potentialVertex;
        MyPoint currentPoint;
        MyPoint nextPointEast;
        MyPoint nextPointSouth;
        while (vertexIterator.hasNext()) {
            currentVertex = (Vertex) vertexIterator.next();
            currentPoint = (MyPoint) currentVertex.getKey();
            // The next point east is one over from the current point.
            nextPointEast = new MyPoint(currentPoint);
            nextPointEast.translate(1, 0);
            potentialVertex = new Vertex(nextPointEast);
            if (vertices.contains(potentialVertex)) {
                // There is an edge between this vertex and the vertex to the east.
                addEdge(currentVertex, potentialVertex);
            }
            // The next point south is one over from the current point.
            nextPointSouth = new MyPoint(currentPoint);
            nextPointSouth.translate(0, 1);
            potentialVertex = new Vertex(nextPointSouth);
            if (vertices.contains(potentialVertex)) {
                // There is an edge between this vertex and the vertex to the east.
                addEdge(currentVertex, potentialVertex);
            }
        }
    }
    public Path shortestPath() {
        return shortestPath(new Vertex(startPoint), new Vertex(endPoint));
    }
    public String toString() {
        return "Start point "
            + startPoint
            + ", End point "
            + endPoint
            + ",\n"
            + "Graph "
            + super.toString();
    }
    public MyPoint getMazeExtent() {
        MyPoint mazeExtent = new MyPoint();
        Set vertices = vertices();
        Iterator i = vertices.iterator();
        Vertex v;
        MyPoint mp;
        while (i.hasNext()) {
            v = (Vertex) i.next();
            mp = (MyPoint) (v.getKey());
            mazeExtent.setLocation(
                Math.max(mp.getXInt(), mazeExtent.getXInt()),
                Math.max(mp.getYInt(), mazeExtent.getYInt()));
        }
        return mazeExtent;
    }
    public String toString(Path path) {
        StringBuffer returnBuffer = new StringBuffer();
        Vertex v = new Vertex();
        MyPoint mazeExtent = getMazeExtent();
        List pathVertices = path.getVertices();
        MyPoint currentPoint;
        for (int y = 0; y <= mazeExtent.getYInt() + 1; y++) {
            for (int x = 0; x <= mazeExtent.getXInt() + 1; x++) {
                currentPoint = new MyPoint(x, y);
                v.setKey(currentPoint);
                if (this.contains(v)) {
                    if (currentPoint.equals(startPoint)) {
                        returnBuffer.append('O');
                    } else if (currentPoint.equals(endPoint)) {
                        returnBuffer.append('X');
                    } else if (pathVertices.contains(v)) {
                        returnBuffer.append('.');
                    } else {
                        returnBuffer.append(' ');
                    }
                } else {
                    returnBuffer.append('+');
                }
            }
            returnBuffer.append('\n');
        }
        return returnBuffer.toString();
    }
}

Graph.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;
/**
 * A graph is a set of vertices, along with a set of edges between the vertices.
 * @author Roy Tock
 */
public class Graph {
    private HashSet vertexSet;
    private HashSet edgeSet;
    /**
     * Each vertex maps to the edges having it as an endpoint.
     */
    private Hashtable edgeIndex;
    public Graph() {
        vertexSet = new HashSet();
        edgeSet = new HashSet();
        edgeIndex = new Hashtable();
    }
    /**
     * Returns a set of vertices in the graph.
     */
    public Set vertices() {
        return vertexSet;
    }
    /**
     * Adds a vertex to the graph.
     */
    public void addVertex(Vertex v) {
        vertexSet.add(v);
        edgeIndex.put(v, new HashSet());
    }
    /**
     * Adds an edge to the graph.  No error checking; this API assumes you've
     * already added the vertices.
     */
    public void addEdge(Vertex v1, Vertex v2) {
        Edge newEdge = new Edge(v1, v2);
        edgeSet.add(newEdge);
        ((HashSet) edgeIndex.get(v1)).add(newEdge);
        ((HashSet) edgeIndex.get(v2)).add(newEdge);
    }
    /**
     * Returns the set of edges having the passed-in vertex as an endpoint,
     * or null if the vertex isn't in the graph.
     */
    public Set edgesHavingVertex(Vertex v) {
        return (Set) edgeIndex.get(v);
    }
    public boolean contains(Vertex v) {
        return vertexSet.contains(v);
    }
    /**
     * Returns the shortest path from the start vertex to the end vertex, or
     * null if no such path exists.
     */
    public Path shortestPath(Vertex start, Vertex end) {
        if (!contains(start)) {
            throw new IllegalArgumentException("Vertex " + start + " not in graph: " + toString());
        } else if (!contains(end)) {
            throw new IllegalArgumentException("Vertex " + end + " not in graph: " + toString());
        }            
        int searchDepth;
        HashSet addedAtPrevDepth = new HashSet();
        HashSet addedAtThisDepth = new HashSet();
        // Maps a vertex v to the shortest path from the start vertex to v
        HashMap pathHash = new HashMap();
        // When the search depth is 0, there is only one vertex in the hash.
        searchDepth = 0;
        pathHash.put(start, new Path(start));
        addedAtThisDepth.add(start);
        Iterator vertexIterator;
        Iterator edgeIterator;
        Vertex currentVertex;
        Path currentVertexPath;
        Vertex otherVertex;
        Path otherVertexPath;
        Edge currentEdge;
        do {
            searchDepth++;
            addedAtPrevDepth = addedAtThisDepth;
            addedAtThisDepth = new HashSet();
            vertexIterator = addedAtPrevDepth.iterator();
            currentDepthLoop : while (vertexIterator.hasNext()) {
                currentVertex = (Vertex) vertexIterator.next();
                currentVertexPath = (Path) pathHash.get(currentVertex);
                Set newEdges = this.edgesHavingVertex(currentVertex);
                edgeIterator = newEdges.iterator();
                while (edgeIterator.hasNext()) {
                    currentEdge = (Edge) edgeIterator.next();
                    otherVertex = currentEdge.otherVertex(currentVertex);
                    if (!pathHash.containsKey(otherVertex)) {
                        addedAtThisDepth.add(otherVertex);
                        otherVertexPath = new Path(currentVertexPath);
                        otherVertexPath.push(currentEdge);
                        pathHash.put(otherVertex, otherVertexPath);
                    }
                    if (otherVertex == end) {
                        break currentDepthLoop;
                    }
                }
            }
        }
        while (!((pathHash.containsKey(end))
            || (addedAtThisDepth.size() == 0)));
        return (Path) (pathHash.get(end));
    }
    
    public String toString() {
        return "Vertices: " + vertexSet + " Edges: " + edgeSet;
    }
}

MyPoint.java

import java.awt.Point;
/**
 * This is my extension of Point, done so that I don't always have
 * to round getX() and getY() to int.
 * 
 * @author Roy Tock
 */
public class MyPoint extends Point {
    public MyPoint() {
        super();
    }
    public MyPoint(int x, int y) {
        super(x, y);
    }
    public MyPoint(MyPoint mp) {
        this(mp.getXInt(), mp.getYInt());
    }
    public int getXInt() {
        return (int) Math.round(getX());
    }
    public int getYInt() {
        return (int) Math.round(getY());
    }
    public String toString() {
        return "(" + getXInt() + ", " + getYInt() + ")";
    }
}

Vertex.java

/**
 * @author Roy Tock
 */
public class Vertex {
    private Object key;
    public Vertex() {}
    public Vertex(Object key) {
        this.key = key;
    }
    public Object getKey() {
        return key;
    }
    public void setKey(Object key) {
        this.key = key;
    }
    public int hashCode() {
        return key.hashCode();
    }
    public boolean equals(Object v) {
        if (v.getClass() != this.getClass()) {
            return false;
        }
        return (((Vertex) v).key.equals(key));
    }
    public String toString() {
        return key.toString();
    }
}

Edge.java

import java.util.ArrayList;
import java.util.List;
/**
 * Encapsulates a graph edge.
 * @author Roy Tock
 */
public class Edge {
    private Vertex v1, v2;
    public Edge(Vertex v1, Vertex v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
    public boolean hasVertex(Vertex v) {
        return (v1.equals(v) || v2.equals(v));
    }
    public List vertices() {
        ArrayList vList = new ArrayList();
        vList.add(v1);
        vList.add(v2);
        return vList;
    }
    public Vertex otherVertex(Vertex v) {
        if (v1.equals(v)) {
            return v2;
        } else if (v2.equals(v)) {
            return v1;
        } else {
            throw new IllegalArgumentException(
                "Vertex " + v + " not in edge " + this +".");
        }
    }
    public String toString() {
        return v1.toString() + "-" + v2.toString();
    }
}

Path.java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;
/**
 * A Path is a list of connecting edges.
 * @author Roy Tock
 */
public class Path {
    Stack edgeList;
    Vertex startVertex;
    public Path(Vertex startVertex) {
        this.startVertex = startVertex;
        edgeList = new Stack();
    }
    public Path(Path p) {
        this.startVertex = p.startVertex;
        edgeList = new Stack();
        edgeList.addAll(p.edgeList);
    }
    /**
     * Adds an edge to the path.
     */
    public void push(Edge e) {
        edgeList.push(e);
    }
    /**
     * Pops an edge from the path.
     */
    public Edge popEdge() {
        return (Edge) edgeList.pop();
    }
    /**
     * Gets the list of vertices, in order, from the starting vertex to the ending vertex.
     */
    public List getVertices() {
        List vertexList = new ArrayList();
        vertexList.add(startVertex);
        Iterator i = edgeList.iterator();
        Vertex currentVertex = startVertex;
        Edge edge;
        while (i.hasNext()) {
            edge = (Edge) i.next();
            currentVertex = edge.otherVertex(currentVertex);
            vertexList.add(currentVertex);
        }
        return vertexList;
    }
    public String toString() {
        StringBuffer returnStringBuffer = new StringBuffer();
        List vertices = getVertices();
        Iterator i = vertices.iterator();
        Vertex v;
        while (i.hasNext()) {
            v = (Vertex) i.next();
            if (returnStringBuffer.length() == 0) {
                returnStringBuffer.append(v);
            } else {
                returnStringBuffer.append("->");
                returnStringBuffer.append(v);
            }
        }
        return returnStringBuffer.toString();
    }
}

[Chandaka Fernando]

hi, this is my first ever message.. here is my version.. its pretty vanila...

import java.io.*;
import java.util.*;
public class MazeSolver {
    public static void main(String[] args) throws IOException{
        Maze mz;
        Point beg, pt; 
        Vector vs, pathQ;
        Path head = null;
        boolean found = false;
        if (args.length != 1) {
            System.out.println("Usage : MazeSolver <fileName>");
            System.exit(1);
        }
/*
first line in the input file shoud have number of rows ans colums in the maze
then, representation of the maze. for example
        
4 8          -- line 0
++++++++     -- line 1
O      X     -- line 2
++++++++     -- line 3
++++++++     -- line 4 
*/
        mz = new Maze(args[0]);
        pathQ = new Vector();
        beg =  mz.getStartingPoint();
        
        pathQ.add(new Path(new Vector(), beg)); 
        while(!pathQ.isEmpty() && !found) {
            head = (Path)pathQ.remove(0);
            vs = mz.getOptions(head.getCurPoint());
        
            for (Enumeration e = vs.elements() ; e.hasMoreElements()     ;)     {
                pt = (Point) e.nextElement();
                if (mz.isEnd(pt)) {
                    found = true;  
                    break;
                }
                pathQ.add(new Path((Vector)head.getCurPath().clone(), pt));
            }
        }

        if(found) { 
            mz.showPath(head);
        } else {
            System.out.println("No path found");
        }
    }
} // class MazeSolver
class Maze {
    private static final int WALL    = '+';
    private static final int PATH    = ' ';
    private static final int VISITED = '#'; 
  
    private int[][] maze;
    private int row, col;
    private int begRow, begCol, endRow, endCol;
    public Maze(String fName) throws IOException {
 
        String line;
        int r,c;
        BufferedReader br = new BufferedReader(new FileReader(fName));
        line = br.readLine();
        StringTokenizer st = new StringTokenizer(line);
        row = Integer.parseInt(st.nextToken()); 
        col = Integer.parseInt(st.nextToken()); 
        maze = new int[row][col];
        for (r=0; r<row; r++) {
            line = br.readLine();
            for (c=0; c<col; c++) {
                switch (line.charAt(c)) {
                    case '+':
                        maze[r][c] = WALL; 
                        break;
                    case 'O':
                        maze[r][c] = WALL;
                        begRow = r; begCol = c;  
                        break;
                    case 'X':
                        maze[r][c] = PATH;
                        endRow = r; endCol = c;
                        break;
           
                    default :
                        maze[r][c] = PATH;
                }
            }
        }
    }    
                 
    public void showPath(Path path) {
        Vector vs = path.getCurPath();
        Point pt;
       
        for (Enumeration e = vs.elements() ; e.hasMoreElements()     ;)     {
            pt = (Point)e.nextElement();
            maze[pt.row][pt.col] = '.';
        }
        maze[begRow][begCol] = 'O';
        maze[endRow][endCol] = 'X';       
        for (int r=0; r<row; r++) {
            for (int c=0; c<col; c++) {
                maze[r][c] = (maze[r][c] == VISITED) ? PATH:maze[r][c];
                System.out.print((char)maze[r][c]);
            }
            System.out.println("");
        }
    }  
    public Point getStartingPoint() {
        return new Point(begRow, begCol);
    }
    public boolean isEnd(Point p) {
        return (p.row == endRow && p.col == endCol) ? true : false;
    }
    public Vector getOptions(Point p) {
        
        Vector ps = new Vector();
        if ((p.row + 1 < row) && (maze[p.row+1][p.col] == PATH) ) {
            ps.add(new Point(p.row+1, p.col));
            maze[p.row +1][p.col] = VISITED;
        }
        if ((p.row - 1 >= 0  ) && (maze[p.row-1][p.col] == PATH) ) {
            ps.add(new Point(p.row -1, p.col));
            maze[p.row -1][p.col] = VISITED;
        }
        if ((p.col + 1 < col) && (maze[p.row][p.col+1] == PATH) ) {
            ps.add(new Point(p.row, p.col+1));
            maze[p.row][p.col+1] = VISITED;
        }
        if ((p.col - 1 >= 0) && (maze[p.row][p.col-1] == PATH) ) {
            ps.add(new Point(p.row, p.col-1));
            maze[p.row][p.col-1] = VISITED;
        }
        return ps;
    }                                                                          
} // class Maze

class Point {
    int row, col;
    
    public Point(int r, int c) {
        row = r;
        col = c;
    }
}// class Point

class Path {
    private Vector path;
    public Path(Vector newPath) {
        path = newPath;
    } 
    public Path(Vector newPath, Point newPoint) {
        path = newPath;
        extend(newPoint);
    }
    public Vector getCurPath() {
        return path;
    }
    public void extend(Point p) {
        path.add(p);
    }
    public Point getCurPoint() {
        return (Point)path.get(path.size()-1);
    }
}// class Path

[ July 11, 2003: Message edited by: Chandaka Fernando ]
[edited to add CODE tags and disable smilies --JM]
[ July 11, 2003: Message edited by: Jason Menard ]

[Brian Nice]

Here is mine:

 
import java.util.*;
import java.io.*;
public class Maza {
// keep track of size of grid
int x, y;
char grid [];
ArrayList tree = new ArrayList();
int beginIndex, endIndex;
int begin, end;
// constructor
public Maza(String fileName) {
try {
BufferedReader br = new BufferedReader(new FileReader(fileName));
String line = null;
int row = 1;
while ((line = br.readLine()) != null) {
if (y == 0) {
x = line.length();
grid = new char[x * x + 1];
}
for (int i=0; i<x; i++) {
char c = line.charAt(i);
grid[row+i] = c;
if (c == 'O') begin=row+i;
if (c == 'X') end=row+i;
}
y++;
row += x;
}
} catch (Exception e) {}
}
// main
public static void main (String [] args) {
Maza maze = new Maza(args[0]);
//System.out.println("Start: " +maze.begin+", End: "+maze.end);
Node n = maze.solve();
maze.printResult(n);
}
// solve
private Node solve() {
beginIndex = 0; endIndex = 1;
tree.add(beginIndex, new Node(0, begin));
Node n = null;
while (true) {
int temp = endIndex;
for (int i=beginIndex; i<temp; i++) {
Node t = (Node)tree.get(i);
n = checkNode(t.value, i);
if (n != null) break;
}
beginIndex = temp;
if (beginIndex == endIndex || n != null)
break;
}
return n;
}
// check Node for solution or path
private Node checkNode(int nodeNumber, int curIndex) {
if (nodeNumber + 1 == end) return new Node(curIndex, nodeNumber + 1);
if (nodeNumber - 1 == end) return new Node(curIndex, nodeNumber - 1);
if (nodeNumber + x == end) return new Node(curIndex, nodeNumber + x);
if (nodeNumber - x == end) return new Node(curIndex, nodeNumber - x);
if (grid[nodeNumber + 1] == ' ' && ((nodeNumber+1)/x == nodeNumber / x)) updateGrid(nodeNumber+1, curIndex);
if (grid[nodeNumber - 1] == ' ' && ((nodeNumber-1)/x == nodeNumber / x)) updateGrid(nodeNumber-1, curIndex);
if ((nodeNumber + x)<=x*x && grid[nodeNumber + x] == ' ') updateGrid(nodeNumber + x, curIndex);
if ((nodeNumber - x)>0 && grid[nodeNumber - x] == ' ') updateGrid(nodeNumber - x, curIndex);
return null;
}
//updateGrid, mark so location is not visited again
private void updateGrid(int value, int curIndex) {
tree.add(endIndex, new Node(curIndex, value));
grid[value] = '*';
endIndex++;
}
// printResult
private void printResult(Node n) {
if (n == null)
System.out.println("No path was found!");
else {
int parent = n.parentIndex;
while (parent != 0)  {
if (n.value != end) grid[n.value]='.';
n = (Node)tree.get(parent);
parent = n.parentIndex;
}
}
for (int i=0; i<grid.length; i++)
if (grid[i] == '*') grid[i]=' ';
int index=1;
while (index < x*y+1) {
System.out.println(new String(grid, index, x));
index += x;
}
}
}
class Node {
int parentIndex;
int value;
public Node(int parentIndex, int value) {
this.parentIndex = parentIndex;
this.value = value;
}
}

[David Weitzman]

Here's a solution that should return the shortest path every time unless I messed up my implementation of Djisktra's algorithm:
Class MazeBuilder (contains main method):

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class MazeBuilder
{
    private static final int[][] OFFSETS = 
    {
        { 1, 0 },
        { -1, 0 },
        { 0, 1 },
        { 0, -1 }
    };
    private Cell _startCell;
    private Cell _endCell;
    private Cell[][] _cells;
    private MazeBuilder(char[][] chars) throws IOException
    {
        initializeCells(chars);
        connectNeighbors();
    }
    private void connectNeighbors()
    {
        for (int i = 0; i < _cells.length; i++)
        {
            for (int j = 0; j < _cells[i].length; j++)
            {
                connectNeighbors(i, j);
            }
        }
    }
    private void connectNeighbors(int row, int col)
    {
        if (_cells[row][col] == null)
        {
            return;
        }
        for (int i = 0; i < OFFSETS.length; i++)
        {
            int rowOffset = OFFSETS[i][0];
            int colOffset = OFFSETS[i][1];
            connectWithNeighbor(row, col, row + rowOffset, col + colOffset);
        }
    }
    private void connectWithNeighbor(int row, int col, int i, int j)
    {
        if (Math.min(i, j) < 0)
        {
            return;
        }
        if ((i >= _cells.length) || (j >= _cells[i].length))
        {
            return;
        }
        if (_cells[i][j] == null)
        {
            return;
        }
        _cells[row][col].addEdge(_cells[i][j]);
    }
    private void initializeCells(char[][] chars)
    {
        // We need a grid to lookup cells by location during construction.
        // After neighbors have been connected, we'll be able to forget the grid.
        _cells = new Cell[chars.length][chars[0].length];
        for (int i = 0; i < chars.length; i++)
        {
            for (int j = 0; j < chars[i].length; j++)
            {
                if (chars[i][j] == '+')
                {
                    continue;
                }
                if ((chars[i][j] != '+') && (chars[i][j] != 'X') && (chars[i][j] != 'O') &&
                        (chars[i][j] != ' '))
                {
                    throw new IllegalArgumentException("Unexpected char at row " + i + " col " + j +
                        ": " + chars[i][j]);
                }
                addCell(i, j);
                if (chars[i][j] == 'O')
                {
                    _cells[i][j].setDistance(0);
                    _startCell = _cells[i][j];
                }
                else if (chars[i][j] == 'X')
                {
                    _endCell = _cells[i][j];
                }
            }
        }
    }
    private void addCell(int i, int j)
    {
        _cells[i][j] = new Cell(i, j);
    }
    public static void main(String[] args) throws IOException
    {
        String fileName = "Maze2.txt";
        char[][] chars = getFileRows(fileName);
        MazeBuilder builder = new MazeBuilder(chars);
        MazeSolver solver = new MazeSolver();
        solver.generateSolution(builder.getStartCell());
        Cell[] solution = solver.interpetSolution(builder.getEndCell());
        if (solution == null)
        {
            System.out.println("There is no solution");
        }
        for (int i = 0; i < solution.length; i++)
        {
            int row = solution[i].getRow();
            int col = solution[i].getCol();
            if (chars[row][col] == ' ')
            {
            // leave the 'O' and 'X' as they are
                chars[row][col] = '.';
            }
        }
        for (int row = 0; row < chars.length; row++)
        {
            for (int col = 0; col < chars[row].length; col++)
            {
                System.out.print(chars[row][col]);
            }
            System.out.println();
        }
    }
    private Cell getEndCell()
    {
        return _endCell;
    }
    private Cell getStartCell()
    {
        return _startCell;
    }
    private static char[][] getFileRows(String fileName)
        throws IOException
    {
        BufferedReader in = new BufferedReader(new FileReader(fileName));
        List rows = new ArrayList();
        String line;
        while ((line = in.readLine()) != null)
        {
            rows.add(line.toCharArray());
        }
        return convertStringListToCharArray(rows);
    }
    private static char[][] convertStringListToCharArray(List rows)
    {
        char[][] result = new char[rows.size()][((char[])rows.get(0)).length];
        for (int row = 0; row < result.length; row++)
        {
            for (int col = 0; col < result[0].length; col++)
            {
                result[row][col] = ((char[])rows.get(row))[col];
            }
        }
        return result;
    }
}

Cell.java:

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
public class Cell
{
    Set _adjacent = new HashSet();
    int _row;
    int _col;
    Cell _predecessor = null;
    int _distance = Integer.MAX_VALUE;
    public Cell(int i, int j)
    {
        _row = i;
        _col = j;
    }
    public void addEdge(Cell cell)
    {
        _adjacent.add(cell);
    }
    public int hashCode()
    {
        // Since there's only one Cell object created to represent each cell,
        // .equals() can simply be the default identify function.
        return super.hashCode();
    }
    public boolean equals(Object obj)
    {
        // Since there's only one Cell object created to represent each cell,
        // .equals() can simply be the default identify function.
        return super.equals(obj);
    }
    public void setDistance(int i)
    {
        _distance = 0;
    }
    public Set getNeighbors()
    {
        return Collections.unmodifiableSet(_adjacent);
    }
    public void setPredecessor(Cell cell)
    {
        _predecessor = cell;
    }
    public int getDistance()
    {
        return _distance;
    }
    public Cell getPredecessor()
    {
        return _predecessor;
    }
    public int getCol()
    {
        return _col;
    }
    public int getRow()
    {
        return _row;
    }
}

MazeSolver.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class MazeSolver
{
    private Set seen = new HashSet();
    public MazeSolver()
    {
    }
    public void generateSolution(Cell startCell)
    {
        if (seen.contains(startCell))
        {
            return;
        }
        else
        {
            seen.add(startCell);
            Set adjacent = startCell.getNeighbors();
            for (Iterator i = adjacent.iterator(); i.hasNext() ;) 
            {
                Cell cell = (Cell)i.next();
                if (distance(cell) > (distance(startCell) + 1))
                {
                    cell.setPredecessor(startCell);
                    cell.setDistance(distance(startCell) + 1);
                }
            }
            for (Iterator i = adjacent.iterator(); i.hasNext() ;) 
            {
                generateSolution((Cell)i.next());
            }
        }
    }
    public Cell[] interpetSolution(Cell endCell)
    {
        if (endCell.getDistance() == Integer.MAX_VALUE)
        {
            // no solution
            return null;
        }
        List solution = new ArrayList();
        Cell currentCell = endCell;
        do
        {
            solution.add(currentCell);
            currentCell = currentCell.getPredecessor();
        }
        while (currentCell != null);
        Collections.reverse(solution);
        return (Cell[])solution.toArray(new Cell[0]);
    }
    private int distance(Cell cell)
    {
        return cell.getDistance();
    }
}

[edited to turn off Dave's smilies ;-) -- JM]
[ July 11, 2003: Message edited by: Jason Menard ]

[David Weitzman]

Yup. I messed it up -- not the shortest path (I was doing my own interpretation of the textbook version designed in a more human-friendly manner, but apparently I implemented David's algorithm and not Djikstras). I think I forgot to sort some stuff. Time to debug...

[David Weitzman]

I seem to have fixed the problem, but I took a shortcut at some cost. Java doesn't come with a built-in priority heap implementation, so I just use a list and keep sorting it every time I add a few elements. Hackish, but at least it works and I know where to look if it ever needs to be faster.
MazeSolver.java (version 2):

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class MazeSolver
{
    private static final Comparator DISTANCE_COMPARATOR = new Comparator()
        {
        // Sorts in REVERSE ORDER!  The item at the back of the list will
        // have the lowest distance
            public int compare(Object o1, Object o2)
            {
                return -((Cell)o1).getDistance() + ((Cell)o2).getDistance();
            }
        };
    private Set seen = new HashSet();
    private List unseen = new ArrayList();
    public MazeSolver()
    {
    }
    public void generateSolution(Cell startCell)
    {
        unseen.add(startCell);
        while (unseen.size() > 0)
        {
            // System.out.println("Unseen " + unseen);
            Cell cell = (Cell)unseen.remove(unseen.size() - 1);
            seen.add(cell);
            for (Iterator i = cell.getNeighbors().iterator(); i.hasNext() :wink: 
            {
                Cell neighbor = (Cell)i.next();
                relax(cell, neighbor);
                if (!seen.contains(neighbor))
                {
                    unseen.add(neighbor);
                }
                else
                {
                    // System.out.println("Already visited: " + neighbor);
                }
            }
            // System.out.println("Seen " + seen);
            Collections.sort(unseen, DISTANCE_COMPARATOR);
        }
    }
    private void relax(Cell startCell, Cell cell)
    {
        if (distance(cell) > (distance(startCell) + 1))
        {
            cell.setPredecessor(startCell);
            cell.setDistance(distance(startCell) + 1);
        }
    }
    public Cell[] interpetSolution(Cell endCell)
    {
        if (endCell.getDistance() == Integer.MAX_VALUE)
        {
            // no solution
            return null;
        }
        List solution = new ArrayList();
        Cell currentCell = endCell;
        do
        {
            solution.add(currentCell);
            currentCell = currentCell.getPredecessor();
        }
        while (currentCell != null);
        Collections.reverse(solution);
        return (Cell[])solution.toArray(new Cell[0]);
    }
    private int distance(Cell cell)
    {
        return cell.getDistance();
    }
}

[Stan James]

Cool. I borrowed the optimization to keep track of the shortest path to each cell and continue recursion only if we're doing better than before. Added 4 lines of code.
This is refactored into better objects than before, no longer compiles as a single file. The solver is now an interface for a strategey; if you want to just work on a new solver for a char[][] representation of the maze, feel free to grab the rest.

package com.saxman.sandbox.amazing;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.LinkedList;
/**
 * This class reads mazes from a file and displays their solutions. Draw a maze using +
 * characters for walls, 0 for the starting point and X for the ending point. Each maze
 * in the file must have a line that starts with Maze in column 1 to name the puzzle.
 * <pre>
 * Maze #1
 * +++++++++++++++
 * +   +   +   + +
 * + + + +   +   +
 * + +++ +++++ + +
 * O     +   +++ X
 * +++ +++++   +++
 * + +     +++ + +
 * +   + +       +
 * +++++++++++++++  
 * </pre>
 */
public class Amazing
{
   public Amazing()
   {
   }
   
   private void readFile( String aFileName )
   throws Exception
   {
      System.out.println( "Amazing.getMazes FileName=" + aFileName );
      BufferedReader lReader = new BufferedReader( new FileReader( aFileName ) );
      String lLine;
      String lName = "";
      List lLines = new LinkedList();
      
      // Collect name & lines for one maze, then create a Maze object when the
      // next maze is found or at end of file.
      while ( true )
      {
         lLine = lReader.readLine();
         if ( null == lLine )
            break; // end of file
         
         if ( lLine.startsWith( "Maze" ) )
         {
            createAndSolveMaze( lName, lLines );
            lName = lLine;
         }
         else
            if ( lLine.length() > 0 )
               lLines.add( lLine );
      }
      createAndSolveMaze( lName, lLines );
      lReader.close();
   }
   private void createAndSolveMaze( String aName, List aLines )
   throws Exception
   {
      if ( !aName.equals( "" ) )
      {
         Maze lMaze = new Maze( aName, aLines );
         lMaze.solve();
      }
      aLines.clear();
   }
   
   /** Command line arguments are names of files containing maze puzzles */
   static public void main( String[] args )
   throws Exception
   {
      Amazing instance = new Amazing();
      for ( int i = 0; i < args.length; i++ )
      {
         instance.readFile( args[i] );
      }
   }
}
package com.saxman.sandbox.amazing;
/** Interface for maze solving strategies */
public interface IMazeSolver
{
   /** Returns best possible solution */
   public Maze solveMaze( Maze aMaze )
   throws Exception;
}

package com.saxman.sandbox.amazing;
import java.util.List;
/**
 * This class represents one Maze
 */
public class Maze
{
   public String   mName = "uninitialized";
   public char[][] mCell;
   public int mRows;
   public int mCols;
   public int mSolutionLength = 0;
   public int mColStart;
   public int mRowStart;
   public IMazeSolver mSolver = new MazeSolver(); // Replaceable strategy
   
   private Maze()
   {}
   
   public Maze( String aName, List aLines )
   throws Exception
   {
      mName = aName;
      Object[] lLines = aLines.toArray();
      mRows = lLines.length;
      if ( mRows == 0 ) return;
      String lLine = (String)lLines[0];
      mCols = lLine.length();
      mCell = new char[mRows][mCols];
      for ( int i = 0; i < mRows; i++ )
      {
         lLine = (String)lLines[i];
         mCell[i] = lLine.toCharArray();
      }
      findStart();
   }
   
   /** Copy constructor */
   public Maze( Maze aMaze )
   {
      mSolutionLength  = aMaze.mSolutionLength;
      mName = aMaze.mName;
      mRows = aMaze.mRows;
      mCols = aMaze.mCols;
      mColStart = aMaze.mColStart;
      mRowStart = aMaze.mRowStart;
      mCell = new char[mRows][mCols];
      for ( int r = 0; r < mRows; r++ )
         for ( int c = 0; c < mCols; c++ )
            mCell[r][c] = aMaze.mCell[r][c];
   }
   
   private void findStart( )
   throws Exception
   {
      for ( int r = 0; r < mRows; r++ )
      {
         for ( int c = 0; c < mCols; c++ )
         {
            if ( mCell[r][c] == 'O' )
            {
               mColStart = c;
               mRowStart = r;
               return;
            }
         }
      }
      throw new Exception("Maze.findStart Name=" + mName + " Start not found" );
   }
   
   public void solve()
   throws Exception
   {
      Maze lSolution = mSolver.solveMaze( this );
      lSolution.display();
   }
   
   public void display()
   {
      System.out.println("Maze.display Name=" + mName + ( mSolutionLength == 0 ? " No solution": " Solution length=" +  mSolutionLength ) );
      for ( int r = 0; r < mRows; r++ )
         System.out.println( new String( mCell[r] ));
   }
}
package com.saxman.sandbox.amazing;
/**
 * This class solves a Maze puzzle by brute force and returns the shortest solution.
 */
public class MazeSolver implements IMazeSolver
{
   Maze mMaze;
   private Maze mSolution;
   private int[][] mShortest; // Shortest path to each cell
   
   public Maze solveMaze( Maze aMaze )
   throws Exception
   {
      System.out.println("MazeSolver.solveMaze " + aMaze.mName );
      mMaze = aMaze;
      mSolution = new Maze( aMaze ); // Default "no solution" answer
      mSolution.mSolutionLength = 0;
      mShortest = new int[aMaze.mRows][aMaze.mCols];
      tryCell( mMaze.mRowStart, mMaze.mColStart, 0 );
      return mSolution;
   }
   
   private void tryCell( int aRow, int aCol, int aLength )
   {
      if ( ( aRow < 0 ) | ( aCol < 0 ) | ( aRow > mMaze.mRows ) | ( aCol > mMaze.mCols ) )
      {}
      // 07/11/2003 JLS See if we already found a shorter route here
      else if ( ( mShortest[aRow][aCol] > 0 ) && ( mShortest[aRow][aCol] <= aLength ) )
      {} 
      else if ( mMaze.mCell[aRow][aCol] == 'X' )
         saveSuccess( aLength );
      else if ( ( mMaze.mCell[aRow][aCol] == ' ' ) | ( mMaze.mCell[aRow][aCol] == 'O' ) )
      {
         mShortest[aRow][aCol] = aLength;
         char lWas = mMaze.mCell[aRow][aCol];
         if ( lWas != 'O' )
            mMaze.mCell[aRow][aCol] = '.';   // leave breadcrumbs
         tryCell( aRow-1, aCol, aLength+1 ); // up
         tryCell( aRow+1, aCol, aLength+1 ); // down
         tryCell( aRow, aCol-1, aLength+1 ); // left
         tryCell( aRow, aCol+1, aLength+1 ); // right
         mMaze.mCell[aRow][aCol] = lWas;     // eat breadcrumbs. Yum!         
      }
   }
   
   private void saveSuccess( int aLength )
   {
      System.out.println("MazesSolver.saveSuccess Solution found in " + aLength + " moves");
      if ( ( mSolution.mSolutionLength == 0 ) | ( mSolution.mSolutionLength > aLength ) )
      {
         mSolution = new Maze( mMaze );
         mSolution.mSolutionLength = aLength;
      }
   }
}

[Ellen Zhao]

What a wonderful thread. You guys are really !
I think one may try concurrency here for the improvement of performence - suppose we implemented a universal maze loader so that can load different mazes, including very huge ones . Let tow objects start off concurrently from the entry and exit of the maze, and see if they can meet somewhere in the maze. And, if breath-first searching is implemented, every branch point can also has its several threads.
For David's solution, the idea is excellent. However I have question whether Djiskra's algorithm is the very suitable here. I guess a maze would have no more than 100 possible solutions - keep the different length value of every possible solution path in a list, then find out the shortest one - so that a naiver/simpler algorithm is not necessarily slower for a maze.
Maybe the maze puzzle can be also implemented via some kind of adjacency matrix other than adjacency list. I hope I could have time for it after all my homework of theoretical proofs there....

Regards,
Ellen

[David Weitzman]

Consider this maze:

+++++++++++++++++++++
+                   +
+                   +
+                   + 
+                   +
+                   +
+                   +
+O                 X+
+++++++++++++++++++++

(Note -- this doesn't look right because spaces aren't as wide as other characters ) Imagine that the right wall is actually at the right.
In order to find the best solution with the naive solution, you need to try every possible path. .
You might try to be clever to not looking at paths longer than one's you've already found, but look at the maze above. Suppose you tried to solve it by first looking up, then left, then down, then right. The first solution you find will be the absolute worst one, zig-zagging up and down until it finally hits the X. The next one will be only slightly better, since the beginning of the path will be largely unchanged. It will continually only find new solutions that are just a little bit better than the current optimum, thus severely limiting the power of the heuristic.
Now there could be heuristics to avoid this kind of problem. You could, for example, try each direction in random order. A less reliable technique would be to try looking first in directions that lead closer to the solution (although that would also allow evil worst-case scenarios to be constructed).
I'm about to make a small modification to my Djikstra implementation so it runs in O(V^2 + E) time and constant memory. Reliable, effective, scalable, and predictable.
[ July 12, 2003: Message edited by: David Weitzman ]
[Attempted to fix appearance in Mozilla - Jim]
[ July 13, 2003: Message edited by: Jim Yingst ]

[David Weitzman]

Okay, I don't expect to change my solution anymore:
MazeSolver.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class MazeSolver
{
    private Set seen = new HashSet();
    private List unseen = new ArrayList();
    public MazeSolver()
    {
    }
    public void generateSolution(Cell startCell)
    {
        unseen.add(startCell);
        while (unseen.size() > 0)
        {
            // System.out.println("Unseen " + unseen);
            Cell cell = extractClosestUnseen();
            for (Iterator i = cell.getNeighbors().iterator(); i.hasNext() :wink: 
            {
                Cell neighbor = (Cell)i.next();
                relax(cell, neighbor);
                if (!seen.contains(neighbor))
                {
                    unseen.add(neighbor);
                }
                else
                {
                    // System.out.println("Already visited: " + neighbor);
                }
            }
            // System.out.println("Seen " + seen);
        }
    }
    private Cell extractClosestUnseen()
    {
        Cell min = (Cell)unseen.get(0);
        int minLoc = 0;
        for (int i = 1; i < unseen.size(); i++)
        {
            Cell cell = (Cell)unseen.get(i);
            if (cell.getDistance() < min.getDistance())
            {
                min = cell;
                minLoc = i;
            }
        }
        // store the last element where the smallest one used to be
        // and shorten the list
        unseen.set(minLoc, unseen.get(unseen.size() - 1));
        unseen.remove(unseen.size() - 1);
        seen.add(min);
        return min;
    }
    private void relax(Cell startCell, Cell cell)
    {
        if (distance(cell) > (distance(startCell) + 1))
        {
            cell.setPredecessor(startCell);
            cell.setDistance(distance(startCell) + 1);
        }
    }
    public Cell[] interpetSolution(Cell endCell)
    {
        if (endCell.getDistance() == Integer.MAX_VALUE)
        {
            // no solution
            return null;
        }
        List solution = new ArrayList();
        Cell currentCell = endCell;
        do
        {
            solution.add(currentCell);
            currentCell = currentCell.getPredecessor();
        }
        while (currentCell != null);
        Collections.reverse(solution);
        return (Cell[])solution.toArray(new Cell[0]);
    }
    private int distance(Cell cell)
    {
        return cell.getDistance();
    }
}

[David Weitzman]

Ellen, if you want to do some concurrent computation testing then a good tool to use would probably be Doug Lea's Fork-Join tasks (available as part of util.concurrent.

[Ellen Zhao]

" Multi-threaded programs will be easier to write with the new concurrency utilities in JSR 166." from here
Seems Doug Lea's concurrency utility package is being added to the J2SE library.

regards,
Ellen

[Stan James]

Thanks for the "worst case" type test. With my optimizations in place (also added stop when there is a shorter solution than current length) I handle that one ok, but without them there is either a bug in my solver or it takes hundreds of millions of tries to find all the dead end paths. (Guess which. I gave up waiting to find out.)
I really like the non-recursive approach David is showing. I was a music major, not CS, so I pick up these fancy schmancy Djikstra algorithms slowly.

[David Weitzman]

Originally posted by Ellen Zhao:
" Multi-threaded programs will be easier to write with the new concurrency utilities in JSR 166." from here
Seems Doug Lea's concurrency utility package is

JSR 166 is a bit more expansive in scope than Lea's package, since Lea and Bloch et al. have permission to modify core classes like Thread. Another cool plus is that it will add a Queue interface to the collection framework and use that instead of Channel.
However it won't contain Fork-Join tasks for the humble computer scientist trying to exploit multiple processors. In Lea's words (from the concurency interest mailing list): "This
was just a decision about generality -- FJTasks are too nichy to put
into JDK. I'll continue to make them available separately though"