Java - Cylindrical Maze solver

[hans030390]

My partner and I are having a hard time figuring out how to do this problem. Here's the description of the assignment:

Consider a two-dimensional array rolled into a cylinder so that the top and bottom rows are glued together.

A path is to be threaded from the left side of a cylinder to the right side, subject to the restrictions that from a given square you can move directly to the right, up and to the right, or down and to the right.

Some of the entries in the maze contain walls that are impassable. A wall is represented by the # character, and an open cell is represented by the . character.

Write a program, MazeSolver, that explores a cylindrical maze to find, and print, all left to right paths. If no paths exist, then print a message to that effect. The maze to explore is specified by three command line arguments.

A path is represented in a maze with the character - for moving due east, / for moving northeast, and \ for moving southeast.

Here's the method/procedure we have to create to solve this:

static int solve(char[][] maze, boolean printFlag) :
-Explores all left-to-right paths in the given maze and returns the number of solutions; each solution is printed iff the given printFlag is true.

We understand that there's a good chance we'll need a number of helper procedures to get this working. However, we're totally stuck on where to start. I think the main problem is the algorithm we'll need and the recursion/looping involved with all of this...and the fact that we need to find out ALL the solutions there are and print them makes it even more difficult and confusing. Where should we start? What should we do?

Any help, hints, tips, tidbits of code, etc...anything, really, is appreciated.

 

[Crusty]

Don't be confused by cylindrical. All that means is that when you are choosing which spot to move to next, you need to consider the bottom row IF your explorer is on the top row, and vice verse.

When writing a recursive algorithm, always determine the base case first. Then figure out how to get there.

 

[hans030390]

Originally posted by: Crusty
Don't be confused by cylindrical. All that means is that when you are choosing which spot to move to next, you need to consider the bottom row IF your explorer is on the top row, and vice verse.

When writing a recursive algorithm, always determine the base case first. Then figure out how to get there.

The cylindrical part isn't confusing. We just have to put in base cases for the "glued" sections with similar, but modified, code to if it wasn't going from, say, top to bottom.

I think the main problem is that we have to find all solutions possible, count how many solutions there are, print them all out if asked, etc. We're having trouble thinking of the recursive algorithm that can handle all of that...though I suppose we could split it up for printing and counting...

We're just having trouble thinking through it...we're not exactly stuck at the beginning, but not specifically stuck in a certain spot.

 

[Markbnj]

Look up A*, which is a pathfinding algorithm. It's more general than you need, but it will give you some ideas on how to use recursion and a stack-based data structure to explore the available paths and assign weights to them.

 

[Ken g6]

http://en.wikipedia.org/wiki/Depth-first_search

Edit: I don't think A*, or breadth-first search, will work in this case, just because he has to print out all possible paths if asked. The directionality has probably been added to avoid loops.

A* explores all paths in parallel, which is nice when you need only one, especially if the maze can go in all directions.

 

[slugg]

The simplest way to solve this is in fact a depth-first approach.

Here's the main idea:

Your algorithm should recursively try every possible path. If the algorithm reaches a wall, it fails and nothing happens. If the final column has been reached by a path, meaning we've "reached the end of the maze", then we should store such information somewhere. In Java, we could simply just store the completed path (in the form of a 2D character array) into an ArrayList if you'd like. Then just print the paths if the size of the ArrayList > 0, or otherwise print that no paths were found.


More info:
Why depth-first? Why not breadth-first?
Well, you COULD do it the other way, but this is just simpler. Since your algorithm will only deal with one root path at a time, it makes it much simpler to store/remember the path if it turns out to be a valid solution. Depth-first pretty much implies a geographical path between one node in a graph and another.

Suggested helper function:
void solveFrom(char[][] maze, int row, int col, ArrayList solutions)
Preconditions: maze is a 2D array as described by your original post. Ints row and col are the coordinates to begin solving from. ArrayList solutions is the ArrayList object to add valid solutions to.
Post-conditions: Adds maze to solutions and returns if (col == maze[row].length - 1). Returns without adding anything to solutions if(maze[row][col] == '#'). Otherwise, populate maze[row][col] with each directional character ('/', '\\', or '-') and call solveFrom(maze, row(+0, -1, and +1), col+1, solutions) for each of the 3 directions (east, northeast, southeast). Obviously, the row must be incremented, decremented, or left unchanged depending on the direction being taken.

Suggested main function behavior:
Create an ArrayList to store the valid solutions in. Let's just call it myList. For every row in maze (that is, 0 to maze.length - 1), call the helper function (described above) for column 0. This could be done with a for loop. Once that is done, use myList.size() to determine how many valid solutions to the maze were found. To retrieve a solution so you could print it, just use my myList.get(i), where i is the index of the solution you'd like to retrieve.


Hope this helps! If you have any questions, please feel free to ask.

 

[PhatoseAlpha]

You guys are way overthinking this. He doesn't need a full scale maze solver, since he always has to go right. Nor does he need to keep a record of his path beyond a simple string.

Should probably be a matter of a simple loop in the main routine to call every possible entry point, a stack to keep track of all solutions, probably a very simple helper method to handle wrap arounds, and a single recursive call with a definition like

void Try(char[][] theMaze, string CurrentPath, int row, int column, stack solutions)

pseudocode:

If theMaze[row][column] is #, return without doing anything.
If we're at the last column, push currentPath onto solutions and return.
If we're not, call:
try(theMaze, CurrentPath + "-", row, column+1, solutions);
try(theMaze, CurrentPath + "-", row-1, column +1, solutions);
try(theMaze, CurrentPath + "-", row+1, column+1, solutions);


though, with the row-1 and row+1 replace with a helper function to handle the wrapping.

 

[degibson]

BFS and DFS have equivalent time complexity, since you must find all solutions.

In practice, DFS will have less space overhead, as you can output paths as they are found.

Ignore A*.

 

[hans030390]

Just so you all know, I don't think we've learned anything about stacks.

 

[Markbnj]

Originally posted by: Ken g6
http://en.wikipedia.org/wiki/Depth-first_search

Edit: I don't think A*, or breadth-first search, will work in this case, just because he has to print out all possible paths if asked. The directionality has probably been added to avoid loops.

A* explores all paths in parallel, which is nice when you need only one, especially if the maze can go in all directions.

No, A* isn't the right answer here, but investigating A* would be a good start. There are variations of it that do a depth-first traversal, and you can easily constrain any of these algorithms to ignore connections to the left of the current node. In any event, the OP hasn't learned about stacks yet, so I assume we're all pushing too far ahead for what his prof. had in mind.

 

[Cogman]

Originally posted by: Markbnj

Originally posted by: Ken g6
http://en.wikipedia.org/wiki/Depth-first_search

Edit: I don't think A*, or breadth-first search, will work in this case, just because he has to print out all possible paths if asked. The directionality has probably been added to avoid loops.

A* explores all paths in parallel, which is nice when you need only one, especially if the maze can go in all directions.

No, A* isn't the right answer here, but investigating A* would be a good start. There are variations of it that do a depth-first traversal, and you can easily constrain any of these algorithms to ignore connections to the left of the current node. In any event, the OP hasn't learned about stacks yet, so I assume we're all pushing too far ahead for what his prof. had in mind.

Meh, with a BFS / DFS I don't think we are pushing to hard, they can both be done without a stack and require only a little recursive code. (ok, there is a stack in there, but the OP will never see it)

 

[tatteredpotato]

My prof. went over an algorithm for a "rat in a maze" problem in my data structures class. The idea is to have a fixed move order, for example: Left, Down, Right, Up. So try to move right, if you can't move down, if you can't move left, etc. If you can't move to any new square (that you haven't visited yet), back track one and repeat.

You can look at the powerpoint here.. Starting at slide 33 in introduction to stacks. I'm not sure it's want you want (doesn't find EVERY path), but it might if it never finds a destination.

 

[presidentender]

Originally posted by: ObscureCaucasian
My prof. went over an algorithm for a "rat in a maze" problem in my data structures class. The idea is to have a fixed move order, for example: Left, Down, Right, Up. So try to move right, if you can't move down, if you can't move left, etc. If you can't move to any new square (that you haven't visited yet), back track one and repeat.

You can look at the powerpoint here.. Starting at slide 33 in introduction to stacks. I'm not sure it's want you want (doesn't find EVERY path), but it might if it never finds a destination.

What you're talking about will work. Instead of just dying when you find the solution, you have the algorithm print the solution, then behave as if that solution is a dead end and keep trying.

 

[slugg]

I wrote a program very similar to what you're going. It was the exact same thing, except the path could move in 4 directions and wasnt forced to move right each step. I did it using the method I described above...

 

[Ken g6]

I have an idea for limiting the search, if you find the basic algorithm is too slow. (I wouldn't expect this to be needed for any grid smaller than about 17x17.)

Since the paths are basically symmetric (which is to say if you reversed the direction rules you would get the same paths), you can start with a BFS backwards, and mark the grid cells that are accessible. An easy way to do this is to search columns east-to-west and enter "true" in a separate array if any of the three cells to the right of a cell are accessible, or false otherwise. This "fills in" things like the backsides of walls and cul-de-sacs, so you don't get stuck there. And if the search produces no true cells in the final west column, there are no possible paths. Otherwise, you'd do the normal search, but consider any cells with false in the separate array as if the cells had "#" in the normal array.