Thread: Need some help printing out my maze!

You have two problems.
First, is that your call to System.out.println(A[x][y]); occurs immediately after you read in an int. Meaning that it will just print out the int you inputted immediately after you input it. If you want to take all of the input first, then print it all out after you are done inputting, you need to put your print statements in another loop after the one you are using to input your numbers.
Second, if you want to print out 3 numbers per line, you should be using the System.out.print(...) method instead of the System.out.println(...) method, since the println method prints, and then moves to the next line, while the print method just prints. After you print out the 3 ints, you can call System.out.println(); to move to the next line.

That probably won't work, since you are overwriting wall several times here:

wall = findPath(r+1, c); // down
wall = findPath(r, c+1); // right
wall = findPath(r-1, c); //up
wall = findPath(r, c-1); //left
...
return wall;

which means that only the result of left will be returned. It is an interesting attempt at recursion (which would be considered the brute-force way and may not necessarily yield the shortest route), but not the *best* way of doing it recursively.
I guess for sudo-code for the recursion, it should be something like:

findPath(row,col):{
if: OUTSIDE_MAZE, return FALSE
if: END_OF_MAZE, set value to 7 (or whatever) and return TRUE
if: is a WALL, return FALSE
if: findPath(row,col-1)==TRUE, set value to 7 and return TRUE //go left
else if: findPath(row+1,col)==TRUE, set value to 7 and return TRUE //go down
else if: findPath(row,col+1)==TRUE, set value to 7 and return TRUE //go right
else if: findPath(row-1,col)==TRUE, set value to 7 and return TRUE //go up
else: return FALSE //dead end
}

Three questions.
1) Have you ever done recursion, and if so, how much?
2) What are the variables: r and c?
3) Are you calling the findPath(...) method before or after you print out the maze?

1. Computer Science? Hopefully your college is better than mine. I came in as a Computer Science major and then changed to Computer Engineering because the conceptual crap was kicking my ass. Ok, well recursion is both very difficult and very easy at the same time. One of the basic rules of a recursive method is that it *shouldn't* return a void (it can return void, but recursive methods rarely do), and there should be at least one exit case. In your case, your findPath() method should be returning a boolean. Setting the global wall variable doesn't help you, since that variable will continuously get changed by the multiple instances of the findPath() method. One of the great things about recursion is that it allows you to backtrace very easily (since it returns to a previous version of itself by design). How much do you understand about recursion?

2. Where are the variables r and c created, and what are their values? You don't appear to change the values of r and c each time you recursively call the findPath() method, which means it will always run with the same arguments and always yield the same result (which could be an infinite recursion).

3. Ok, with recursion, you should not have to worry about using the 7 or 3 numbers, just the plus.


Let's have a look at what my sudo-code does with the example maze:

1 0 1
0 0 1
1 0 0

where the coordinate 0,1 is the start and 2,2 is the end.

Here is a copy of my sudo-code with line numbers (for the sake of making the stuff below easier). I also edited it because I noticed it would create an infinite recursion:

/*
 * type is an int, representing the last move. -1 indicates no last move, 0 indicates left,
 * 1 indicates down, 2 indicates right, and 3 indicates up
 */
findPath(row,col,type):{ 
#1 if: OUTSIDE_MAZE, return FALSE
#2 if: END_OF_MAZE, set value to + (or whatever) and return TRUE
#3 if: is a WALL, return FALSE
#4 if: type!=2 and findPath(row,col-1)==TRUE, set value to + and return TRUE //go left
#5 else if: type!=3 and findPath(row+1,col)==TRUE, set value to + and return TRUE //go down
#6 else if: type!=0 and findPath(row,col+1)==TRUE, set value to + and return TRUE //go right
#7 else if: type!=1 and findPath(row-1,col)==TRUE, set value to + and return TRUE //go up
#8 else: return FALSE //dead end
}
}

We start by sending the findPath(row,col,type) method our starting index, so we say:
findPath(0,1,-1);
Now, that we did that, let's look at how it would trace (sudo-trace, I guess). I'll say inst #,call # to indicate the instance of findPath() and the line we are executing:

inst 1,call #1 -> evaluates to false, moves to #2
inst 1,call #2 -> evaluates to false, moves to #3
inst 1,call #3 -> evaluates to false, moves to #4
inst 1,call #4 -> starts inst 2 - findPath(0,0,0)
inst 2,call #1 -> evaluates to false, moves to #2
inst 2,call #2 -> evaluates to false, moves to #3
inst 2,call #3 -> evaluates to true, returns FALSE back to inst1
inst 1,call #4 -> returned value is false, moves to #5
inst 1,call #5 -> starts inst 3 - findPath(1,1,1)
inst 3,call #1 -> evaluates to false, moves to #2
inst 3,call #2 -> evaluates to false, moves to #3
inst 3,call #3 -> evaluates to false, moves to #4
inst 3,call #4 -> starts inst 4 - findPath(1,0,0)
inst 4,call #1 -> evaluates to false, moves to #2
inst 4,call #2 -> evaluates to false, moves to #3
inst 4,call #3 -> evaluates to false, moves to #4
inst 4,call #4 -> starts inst 5 - findPath(1,-1,0)
inst 5,call #1 -> evalutes to true, returns FALSE back to inst 4
inst 4,call #4 -> returned value is false, moves to #5
inst 4,call #5 -> starts inst 6 - findPath(2,0,1)
inst 6,call #1 -> evaluates to false, moves to #2
inst 6,call #2 -> evaluates to false, moves to #3
inst 6,call #3 -> evaluates to true, returns FALSE back to inst 4
inst 4,call #5 -> returned value is false, moves to #6
inst 4,call #6 -> evaluates to false, moves to #7
inst 4,call #7 -> starts inst 7 - findPath(0,0,3)
inst 7,call #1 -> evaluates to false, moves to #2
inst 7,call #2 -> evaluates to false, moves to #3
inst 7,call #3 -> evaluates to true, returns FALSE back to inst 4
inst 4,call #7 -> returned value is false, moves to #8
inst 4,call #8 -> returns FALSE back to inst 3
inst 3,call #4 -> returned value is false, moves to #5
inst 3,call #5 -> starts inst 8 - findPath(2,1,1)
inst 8,call #1 -> evaluates to false, moves to #2
inst 8,call #2 -> evaluates to false, moves to #3
inst 8,call #3 -> evaluates to false, moves to #4
inst 8,call #4 -> starts inst 9 - findPath(2,0,0)
inst 9,call #1 -> evaluates to false, moves to #2
inst 9,call #2 -> evaluates to false, moves to #3
inst 9,call #3 -> evaluates to true, returns FALSE back to inst 8
inst 8,call #4 -> returned value is false, moves to #5
inst 8,call #5 -> starts inst 10 - findPath(3,1,1)
inst 10,call #1-> evaluates to true, returns FALSE back to inst 8
inst 8,call #5 -> returned value is false, moves to #6
inst 8,call #6 -> starts inst 11 - findPath(2,2,2)
inst 11,call #1-> evaluates to false, moves to #2
inst 11,call #2-> evaluates to true, sets value at index 2,2 to + and returns TRUE to inst 8
inst 8,call #6 -> returned value is true, sets value at index 2,1 to + and returns TRUE to inst 3
inst 3,call #5 -> returned value is true, sets value at index 1,1 to + and returns TRUE to inst 1
inst 1,call #5 -> returned value is true, sets value at index 2,2 to + and returns TRUE

And there we are. The maze is solved. Now, read through all that and tell me what does and does not make sense about that trace. From there, we can figure out what aspects of recursion is causing you problems.

I will note that even with the above sudo-code, it will lead to infinite recursions if you have a large open area without walls. The only way to avoid that would be by marking your previous locations, like you were doing earlier.