aspose file tools*
The moose likes Programming Diversions and the fly likes July Newsletter Puzzle (Maze Solver) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "July Newsletter Puzzle (Maze Solver)" Watch "July Newsletter Puzzle (Maze Solver)" New topic
Author

July Newsletter Puzzle (Maze Solver)

Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450

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
    OStart
    XFinish
    +Wall


    Maze #1

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

    Maze #2

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

     
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
This is serious brute force:

Here is the file I ran it against:

For results


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
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)
Roy Tock
Ranch Hand

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

Maze.java

Graph.java

MyPoint.java

Vertex.java

Edge.java

Path.java
Chandaka Fernando
Greenhorn

Joined: Jul 11, 2003
Posts: 4
hi, this is my first ever message.. here is my version.. its pretty vanila...

[ 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
Ranch Hand

Joined: Nov 02, 2000
Posts: 195
Here is mine:
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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):

Cell.java:

MazeSolver.java

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

Joined: Jul 27, 2001
Posts: 1365
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
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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):
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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.
Ellen Zhao
Ranch Hand

Joined: Sep 17, 2002
Posts: 581
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
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Consider this maze:

(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
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Okay, I don't expect to change my solution anymore:
MazeSolver.java
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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
Ranch Hand

Joined: Sep 17, 2002
Posts: 581
" 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
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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"
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: July Newsletter Puzzle (Maze Solver)