# Traversing a Maze

• (2 Pages)
• 1
• 2

## 22 Replies - 8081 Views - Last Post: 02 December 2012 - 11:44 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=302160&amp;s=3b6bfeaa66f1bd10b332dded03a79ea9&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

# Traversing a Maze

Posted 30 November 2012 - 02:41 AM

Hey guys, I am new here plus i am a HUGE NOOB when it comes to programming and I was hoping you guys can help me out with my final project

1 Project Description
Given the starting point in a 10 row  20 column maze, your program is to discover and report
if there is a path out of the maze. A maze consists of only hedges, footpaths, and a single exit.
The program asks the user for the starting position in the maze (you may start at any point on a
footpath except the exit, and the upper left corner is considered row 1, column 1) and then reports
if they are free (i.e. you have found a way out) or trapped.
You may move vertically or horizontally (not diagonally!) in any direction in the maze as long as
you are on a footpath or at the exit; you may not move into (onto) a hedge. If you move into the
exit square, you have successfully exited the maze. If you have tried all of the possible paths out
of the maze without success, you are trapped. You must use a recursive routine to search for the
exit. If you are in a square and no progress is possible (i.e. the squares surrounding you either are
blocked with hedges and/or you have already tried those paths), you must `go back the way you
came' and try another path (this will be handled `automatically' by the recursive algorithm). The
path you nd out of the maze, if one exists, need not be the shortest path.

Input is a 10 row by 20 column array of characters (containing only 1s, 0s, a single E, with no
spaces) from an text data le speci ed on the command line; you may assume the maze data le
is correct. Each row in the data le corresponds to a row in your maze. Hedges are indicated by
the character 1, paths by the character 0, and the exit is marked by an upper case E. The starting
point (i.e. a row, column pair) in the maze will be input from the keyboard; you should make sure
it is a valid position (see the sample run).

You should format your output exactly as the sample run shown below; also use exactly the same
labels, spacing, data prompts, and error messages. Echo print the (initial) maze prior to asking the
user for their starting point. After acquiring the start position, print the complete maze with an S
in the starting point followed by the words `I am free' if you have found a path out of the maze or
the words `Help, I am trapped' if you cannot.
Your maze should be printed using one screen column and screen row per maze column and row
using exactly the same characters as shown in the sample run. You should print a border around
the maze and label all sides with the appropriate row and column number.

4 Sample Run

1 2
12345678901234567890
+--------------------+
1| ### # # |1
2|### ### # # ####|2
3|##### # ### |3
4|E #### # ## # # |4
5| # ## # # #### ## |5
6| # ## #### |6
7|## ### ## ## ### |7
8| #### ## ####### #|8
9| # ## #### ## #|9
10| # ## ## ###|10
+--------------------+
1 2
12345678901234567890
Starting point? row: -3
col: 5
Illegal starting position; try again
Starting point? row: 4
col: 1
Try again - you cannot start at the exit
Starting point? row: 2
col: 12

And here is my code and question

How can I make it so that the user inputs the starting location and then store that into a final char variable which in turn makes that location on the maze into an 'S' symbol
(By all means this code is nowhere complete for I have still doubts about the traverse and valid (checking for legal moves) methods and I am not suppose to have a maze. I know i need to make an empty Array so my teacher and use his maze as test data but for now I did create the sample maze for testing. I know for a fact that my toString is damn near flawless but I could use help on my question)

```import java.io.IOException;
import java.util.Scanner;

public class Proj71773 {
public static void main(String[] args) throws IOException {

Maze maze = new Maze();

System.out.println(maze);
Maze.location();

}
}

class Maze {

private final int TRIED = 3;
private final int PATH = 7;
private final char E = 'E';

private char [][] maze = {
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 },
{ E, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0 },
{ 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0 },
{ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1 } };

// -----------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
// -----------------------------------------------------------------

public static void location(){

Scanner input = new Scanner(System.in);

int row;
System.out.print ("Starting point? row: ");
row = input.nextInt();

int col;
System.out.print ("		col: " );
col = input.nextInt();

}

public boolean traverse (int row, int column) {
boolean done = false;

if (valid (row, column))
{
maze[row][column] = TRIED;

if (row == E && column == E)
done = true;

else
{
done = traverse (row+1, column);
if (!done)
done = traverse (row, column=1);
if (!done)
done = traverse (row-1, column);
if (!done)
done = traverse (row, column-1);
}
if (done)
maze[row][column] = PATH;

}
return done;

}
// -----------------------------------------------------------------
// Determines if a specific location is valid.
// -----------------------------------------------------------------
public boolean valid (int row, int column){

boolean result = false;

if (row >= 0 && row < maze.length && column >= 0 && column < maze[row].length)

if (maze[row][column] == 1)
result = true;

return result;
}

// -----------------------------------------------------------------
// Returns the maze as a string.
// -----------------------------------------------------------------
public String toString() {
StringBuffer titleBuf = new StringBuffer();
StringBuffer tagStr = new StringBuffer();
tagStr.append("\n");

int rowCount = 1;
int colCount = 0;

for (int row = 0; row < maze.length; row++) {

if (row == 0 || row == maze[row].length-1) {
titleBuf.append(lineDraw(maze[row].length));
}

for (int column = 0; column < maze[row].length; column++) {

// padding row # & pipe symbol in left end
if (column == 0) {
//  padding an empty space for single digit number
if ( rowCount < 10) {
tagStr.append(" ");
}
// print row count & pipe symbol
tagStr.append(rowCount);
tagStr.append("|");
}

if (maze[row][column] == E) {
tagStr.append("E");
} else if (maze[row][column] != 0) {
tagStr.append("#");
} else {
tagStr.append(" ");
}

// padding row # & pipe symbol in right end
if (column == maze[row].length - 1) {
tagStr.append("|");
tagStr.append(rowCount);
rowCount++;
}
colCount = maze[row].length;

}
tagStr.append("\n");
}

titleBuf.append(tagStr);
titleBuf.append(lineDraw(colCount));
titleBuf.append("\n");
return titleBuf.toString();
}

// -----------------------------------------------------------------
// Returns the the number title format of string as stringbuffer.
// It read the number of column, divided by 10.
// If the number is less than 10, print " " string.
// if 10 is reached, print 1. To drop after 10, filter out by modular
// number.
// The second line is mod by 10 to keep 0-9 repeat
// -----------------------------------------------------------------
StringBuffer sbuf = new StringBuffer();
sbuf.append("   ");
for (int i=1; i <= colSize; i++) {
// divide by 10
if (i/10 > 0) {
// print only 10 mod number
if(i % 10 == 0 ) {
sbuf.append(i/10);
} else {
sbuf.append(" ");
}
} else {
sbuf.append(" ");
}
}
sbuf.append("\n");
sbuf.append("   ");
for (int i=1; i <= colSize; i++) {
sbuf.append(i % 10);
}

sbuf.append("\n");
return sbuf;
}

// -----------------------------------------------------------------
// Returns the line draw as stringbuffer.
// The first and last symbol is "+", and others "=".
// -----------------------------------------------------------------
private StringBuffer lineDraw(int colSize) {
StringBuffer tbuf = new StringBuffer();
int formatSize = colSize+2;
tbuf.append("  ");
for (int i=0; i < formatSize; i++) {
if (i == 0 || i == formatSize-1) {

tbuf.append("+");
} else {
tbuf.append("-");
}
}
return tbuf;
}

}
```

Is This A Good Question/Topic? 0

## Replies To: Traversing a Maze

### #2 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Traversing a Maze

Posted 30 November 2012 - 05:56 AM

Quote

How can I make it so that the user inputs the starting location and then store that into a final char variable which in turn makes that location on the maze into an 'S' symbol

Are you simply asking how to get user input from the program's command line? If so, refer to this tutorial. Once you've obtained the command line arguments, store them as needed, verify the location in the maze is valid and an available starting point, and change the specified location in the maze array to an 'S'.

If there's more to your question (and there probably will be eventually), please come back with more details. Remember, arrays are zero based, but your assignment requires that the top left corner of the maze be specified as location (1, 1).

### #3 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 30 November 2012 - 10:14 AM

Any Idea why this isnt working? says I have InputMismatchException but I am still having problems understanding what to do
```import java.io.*;
import java.util.Scanner;

public class Proj71773 {
public static void main(String[] args) throws IOException, FileNotFoundException {
File file = new File(args [0]);
Maze maze = new Maze(file);

System.out.println(maze);

}

}

class Maze{

private final char TRIED = '3';
private final char PATH = '7';
private final char E = 'E';
private final char S = 'S';
private final int row, column;
private final char [][] maze;

Maze(File file) throws IOException {
row = line.nextInt();
column = line.nextInt();
maze = new char [row][column];

for (int i = 0; i < column; i++){
for (int j = 0; j < row; j++){
char c = line.next().charAt(0);
maze[i][j]  = c;
}
}

}

public boolean traverse (int row, int column) {
boolean done = false;

if (valid (row, column))
{
maze[row][column] = TRIED;

if (row == E && column == E)
done = true;

else
{
done = traverse (row+1, column);
if (!done)
done = traverse (row, column=1);
if (!done)
done = traverse (row-1, column);
if (!done)
done = traverse (row, column-1);
}
if (done)
maze[row][column] = PATH;

}
return done;

}
// -----------------------------------------------------------------
// Determines if a specific location is valid.
// -----------------------------------------------------------------
public boolean valid (int row, int column){

boolean result = false;

if (row >= 0 && row < maze.length && column >= 0 && column < maze[row].length)

if (maze[row][column] == 1)
result = true;

return result;
}

// -----------------------------------------------------------------
// Returns the maze as a string.
// -----------------------------------------------------------------
public String toString() {
StringBuffer titleBuf = new StringBuffer();
StringBuffer tagStr = new StringBuffer();
tagStr.append("\n");

int rowCount = 1;
int colCount = 0;

for (int row = 0; row < maze.length; row++) {

if (row == 0 || row == maze[row].length-1) {
titleBuf.append(lineDraw(maze[row].length));
}

for (int column = 0; column < maze[row].length; column++) {

// padding row # & pipe symbol in left end
if (column == 0) {
//  padding an empty space for single digit number
if ( rowCount < 10) {
tagStr.append(" ");
}
// print row count & pipe symbol
tagStr.append(rowCount);
tagStr.append("|");
}

if (maze[row][column] == E) {
tagStr.append("E");
//if (maze[row][column] == S) { tagStr.append("S");}
} else if (maze[row][column] != 0) {
tagStr.append("#");
} else {
tagStr.append(" ");
}

// padding row # & pipe symbol in right end
if (column == maze[row].length - 1) {
tagStr.append("|");
tagStr.append(rowCount);
rowCount++;
}
colCount = maze[row].length;

}
tagStr.append("\n");
}

titleBuf.append(tagStr);
titleBuf.append(lineDraw(colCount));
titleBuf.append("\n");
return titleBuf.toString();
}

// -----------------------------------------------------------------
// Returns the the number title format of string as stringbuffer.
// It read the number of column, divided by 10.
// If the number is less than 10, print " " string.
// if 10 is reached, print 1. To drop after 10, filter out by modular
// number.
// The second line is mod by 10 to keep 0-9 repeat
// -----------------------------------------------------------------
StringBuffer sbuf = new StringBuffer();
sbuf.append("   ");
for (int i=1; i <= colSize; i++) {
// divide by 10
if (i/10 > 0) {
// print only 10 mod number
if(i % 10 == 0 ) {
sbuf.append(i/10);
} else {
sbuf.append(" ");
}
} else {
sbuf.append(" ");
}
}
sbuf.append("\n");
sbuf.append("   ");
for (int i=1; i <= colSize; i++) {
sbuf.append(i % 10);
}

sbuf.append("\n");
return sbuf;
}

// -----------------------------------------------------------------
// Returns the line draw as stringbuffer.
// The first and last symbol is "+", and others "=".
// -----------------------------------------------------------------
private StringBuffer lineDraw(int colSize) {
StringBuffer tbuf = new StringBuffer();
int formatSize = colSize+2;
tbuf.append("  ");
for (int i=0; i < formatSize; i++) {
if (i == 0 || i == formatSize-1) {

tbuf.append("+");
} else {
tbuf.append("-");
}
}
return tbuf;
}

}
```

### #4 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Traversing a Maze

Posted 30 November 2012 - 11:06 AM

Posting the exact error message/stack trace is incredibly helpful, eliminating the need to look at each of the 200+ lines of code to figure out where/why you might be getting that error.

### #5 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 30 November 2012 - 10:42 PM

```import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;

public class Proj71773 {

static char[][] mazeArray = new char[10][20];
static final int rowSize = 10;
static final int colSize = 20;

public static void main(String[] args) throws FileNotFoundException,
IOException {

File inputFile = new File (args [0]);
FileInputStream is = null;

try {
is = new FileInputStream(inputFile);
int n = -1;
int rowCount = 0;
int colCount = 0;
while ((n = is.read()) != -1) {
// removes the line breaks
}

// if the size of row is reached,
// reset the row to the next row
if (rowCount++ >= rowSize - 1) {
rowCount = 0;
if (colCount++ >= colSize - 1) {
// array is full, so exit
break;
}
}
}
}
} catch (FileNotFoundException e) {
// could not get Inputstream from file
e.printStackTrace();
} catch (IOException e) {
// problem with the inputstream while reading
e.printStackTrace();
} finally {
// close all files & inpusStreams
is.close();
}

// instantiate your maze class here
Maze maze = new Maze(mazeArray);
// test output print
System.out.println(maze);

}

}

class Maze {
private char[][] maze = new char [10][20];

private final int TRIED = 3;
private final int PATH = 7;
private final char E = 'E';

// constructor with argument char 2-d array from input file
public Maze(char[][] maze) {
super();
this.maze = maze;
}

// -----------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
// -----------------------------------------------------------------
public boolean traverse(int row, int column) {
boolean done = false;

return done;
}

// -----------------------------------------------------------------
// Determines if a specific location is valid.
// -----------------------------------------------------------------
private boolean valid(int row, int column) {
boolean result = false;

return result;
}

// -----------------------------------------------------------------
// Returns the maze as a string.
// -----------------------------------------------------------------
public String toString() {
StringBuffer titleBuf = new StringBuffer();
StringBuffer tagStr = new StringBuffer();
tagStr.append("\n");

int rowCount = 1;
int colCount = 0;

for (int row = 0; row < maze.length; row++) {

if (row == 0 || row == maze[row].length - 1) {
titleBuf.append(lineDraw(maze[row].length));
}

for (int column = 0; column < maze[row].length; column++) {

// padding row # & pipe symbol in left end
if (column == 0) {
// padding an empty space for single digit number
if (rowCount < 10) {
tagStr.append(" ");
}
// print row count & pipe symbol
tagStr.append(rowCount);
tagStr.append("|");
}

if (maze[row][column] == E) {
tagStr.append("E");
} else if (maze[row][column] == '1') {
tagStr.append("#");
} else {
tagStr.append(" ");
}

// testing
//tagStr.append(maze[row][column]);
// padding row # & pipe symbol in right end
if (column == maze[row].length - 1) {
tagStr.append("|");
tagStr.append(rowCount);
rowCount++;
}
colCount = maze[row].length;

}
tagStr.append("\n");
}

titleBuf.append(tagStr);
titleBuf.append(lineDraw(colCount));
titleBuf.append("\n");
return titleBuf.toString();
}

// -----------------------------------------------------------------
// Returns the the number title format of string as stringbuffer.
// It read the number of column, divided by 10.
// If the number is less than 10, print " " string.
// if 10 is reached, print 1. To drop after 10, filter out by modular
// number.
// The second line is mod by 10 to keep 0-9 repeat
// -----------------------------------------------------------------
StringBuffer sbuf = new StringBuffer();
sbuf.append("   ");
for (int i = 1; i <= colSize; i++) {
// divide by 10
if (i / 10 > 0) {
// print only 10 mod number
if (i % 10 == 0) {
sbuf.append(i / 10);
} else {
sbuf.append(" ");
}
} else {
sbuf.append(" ");
}
}
sbuf.append("\n");
sbuf.append("   ");

for (int i = 1; i <= colSize; i++) {
sbuf.append(i % 10);
}

sbuf.append("\n");
return sbuf;
}

// -----------------------------------------------------------------
// Returns the line draw as stringbuffer.
// The first and last symbol is "+", and others "=".
// -----------------------------------------------------------------
private StringBuffer lineDraw(int colSize) {

StringBuffer tbuf = new StringBuffer();
int formatSize = colSize + 2;
tbuf.append("  ");
for (int i = 0; i < formatSize; i++) {
if (i == 0 || i == formatSize - 1) {

tbuf.append("+");
} else {
tbuf.append("-");
}
}
return tbuf;
}

}
```

Here is my output

```            1         2
12345678901234567890
+--------------------+
1| #  ##   #  ##### ##|1
2|  ##   ## # ######  |2
3|  # #    ## # ####  |3
4|  ### E#   ##  ##   |4
5|#   #  # #   #  ##  |5
6|#   #   ##   # # #  |6
7|#   ###  # ##  ###  |7
8| ### ## ## ###   ## |8
9|  ## ####    # #    |9
10|  ##  #     #  ###  |10
+--------------------+
1         2
12345678901234567890
```

Here is my problem, the output is suppose to be like
this

[code]1 2
12345678901234567890
+--------------------+
1| ### # # |1
2|### ### # # ####|2
3|##### # ### |3
4|E #### # ## # # |4
5| # ## # # #### ## |5
6| # ## #### |6
7|## ### ## ## ### |7
8| #### ## ####### #|8
9| # ## #### ## #|9
10| # ## ## ###|10
+--------------------+
1 2

### #6 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 30 November 2012 - 10:51 PM

Sorry clicked submit before I can clean up the correct output
```            1         2
12345678901234567890
+--------------------+
1|    ###   #      #  |1
2|###   ### # #   ####|2
3|####    #     ###   |3
4|E  #### # ##   #  # |4
5| # ## # # ####   ## |5
6|        #  ##  #### |6
7|## ###  ## ## ###   |7
8|   #### ## ####### #|8
9| # ## #### ##      #|9
10| #         ## ## ###|10
+--------------------+
1         2
12345678901234567890

[quote name='J0hnnysmokes' date='30 November 2012 - 10:50 PM' timestamp='1354341028' post='1758271']
Sorry clicked submit before I can clean up the correct output
[code]
1         2
12345678901234567890
+--------------------+
1|    ###   #      #  |1
2|###   ### # #   ####|2
3|####    #     ###   |3
4|E  #### # ##   #  # |4
5| # ## # # ####   ## |5
6|        #  ##  #### |6
7|## ###  ## ## ###   |7
8|   #### ## ####### #|8
9| # ## #### ##      #|9
10| #         ## ## ###|10
+--------------------+
1         2
12345678901234567890

```

^ that is what the correct output is suppose to look like

### #7 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Traversing a Maze

Posted 30 November 2012 - 11:49 PM

Post the contents of the maze definition file in code tags.

The problem is with the reading of the maze definition file, because your Maze.toString() method works great. I'm not sure exactly what's wrong with the way you're reading the file, but I know that it's more complicated than it needs to be. Why don't you just do something like:
```try
{
File inputFile = new File ( "./files/maze.txt" );
Scanner readFile = new Scanner( inputFile );

String lineIn = "";
int row = 0;

{
mazeArray[row++] = lineIn.toCharArray();
}
}
```

That works great for me with the maze definition file:
```00001110001000000100
11100011101010001111
11111000100000111000
E0011110101100010010
01011010101111000110
00000000100110011110
11011100110110111000
00011110110111111101
01011011110110000001
01000000000110110111
```

This post has been edited by GregBrannon: 01 December 2012 - 12:28 AM

### #8 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 01 December 2012 - 02:13 AM

oh wow thanks that actually helped alot

Ok now I am going to start thinking about how to make the starting point and replace that location with a 'S' on the maze. Ill be back after I try to figure it out on my own

### #9 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 01 December 2012 - 02:53 AM

hmm here is what I have so far,
But I have no clue on how to take those values, store them into my maze array, then change said values into a char 'S', then start the traversal process from those points
any ideas?
```  public void location (){
Scanner scan = new Scanner (System.in);

int i;

System.out.print("Starting point? row: ");
i = scan.nextInt();

int j;
System.out.print("		col: ");
j = scan.nextInt();
}

```

### #10 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Traversing a Maze

Posted 01 December 2012 - 03:28 AM

The values input by the user, i for row and j for column, specify the coordinates of the desired starting point. Since the printed maze rows and columns are not zero based but the maze array is, you'll have to translate the user's input from the screen coordinates to the maze array coordinates, but that's easy: just subtract one.

So if the user enters row: 5 and column: 20, the program will first subtract one from each to get maze array coordinates, ( i - 1, j - 1 ) or ( 4, 19 ), then check to see if that is a valid position. (I'm assuming that means it falls on a path, but should it also be on an edge?) The starting point is valid if mazeArray[i-1][j-1] == ' '. If not valid, the program should get new coordinates for the starting point. Once valid, then the starting point is denoted by an 'S' in the maze array:

mazeArray[i-1][j-1] = 'S';

and per the directions the finished puzzle is reprinted for the user to see.

The Maze class should include methods to determine whether a given starting point is valid and then to set the starting point.

This post has been edited by GregBrannon: 01 December 2012 - 03:32 AM

### #11 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 01 December 2012 - 04:59 AM

```public class Proj71773 {

static char[][] mazeArray = new char[10][20];

public static void main(String[] args) throws FileNotFoundException,
IOException {

try {

File inputFile = new File (args [0]);
Scanner readFile = new Scanner (inputFile);

String lineLn = " ";
int row = 0;

{
mazeArray[row++] = lineLn.toCharArray();
}
} catch (FileNotFoundException e) {
// could not get Inputstream from file
e.printStackTrace();
} catch (IOException e) {
// problem with the inputstream while reading
e.printStackTrace();
} finally {
// close all files & inpusStreams

}

// instantiate your maze class here
Maze maze = new Maze(mazeArray);
// test output print
System.out.println(maze);
maze.location();
System.out.println(maze);
}

}

class Maze {

private char [][] maze = new char [10][20];
private final int TRIED = 3;
private final int PATH = 7;
private final char E = 'E';

// constructor with argument char 2-d array from input file
public Maze(char[][] maze) {
super();
this.maze = maze;
}

public void location (){
Scanner scan = new Scanner (System.in);

int i;

System.out.print("Starting point? row: ");
i = scan.nextInt();

int j;
System.out.print("		col: ");
j = scan.nextInt();

if (valid (i, j))
{
maze[i-1][j-1] = 'S';

} else
{
if (!valid (i, j)){
System.out.println("Illegal starting position; try again");
System.out.print("Starting point? row: ");
i = scan.nextInt();
System.out.print("		col: ");
j = scan.nextInt();
}
if (maze[i-1][j-1] == E){
System.out.println("Try again - you cannot start at the extit");
System.out.print("Starting point? row: ");
i = scan.nextInt();
System.out.print("		col: ");
j = scan.nextInt();
}
}
}

// -----------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
// -----------------------------------------------------------------
public boolean traverse(int row, int column) {
boolean done = false;

if (valid (row, column))
{
maze[row][column] = TRIED;

if (row == E && column == E)
done = true;
else {
done = traverse (row+1, column);
if (!done)
done = traverse (row, column+1);
if (!done)
done = traverse (row-1, column);
if (!done)
done = traverse (row, column-1);
}
if (done)
maze[row][column] = PATH;
}
return done;
}

// -----------------------------------------------------------------
// Determines if a specific location is valid.
// -----------------------------------------------------------------
private boolean valid(int row, int column ) {
boolean result = false;

if (row >= 0 && row < maze.length && column >= 0 && column < maze[row].length)

if (maze[row][column] == 1)
result = true;

return result;
}

// -----------------------------------------------------------------
// Returns the maze as a string.
// -----------------------------------------------------------------
public String toString() {
StringBuffer titleBuf = new StringBuffer();
StringBuffer tagStr = new StringBuffer();
tagStr.append("\n");

int rowCount = 1;
int colCount = 0;

for (int row = 0; row < maze.length; row++) {

if (row == 0 || row == maze[row].length - 1) {
titleBuf.append(lineDraw(maze[row].length));
}

for (int column = 0; column < maze[row].length; column++) {

// padding row # & pipe symbol in left end
if (column == 0) {
// padding an empty space for single digit number
if (rowCount < 10) {
tagStr.append(" ");
}
// print row count & pipe symbol
tagStr.append(rowCount);
tagStr.append("|");
}

if (maze[row][column] == E) {
tagStr.append("E");
} else if (maze[row][column] == '1') {
tagStr.append("#");
} else {
tagStr.append(" ");
}

// testing
//tagStr.append(maze[row][column]);
// padding row # & pipe symbol in right end
if (column == maze[row].length - 1) {
tagStr.append("|");
tagStr.append(rowCount);
rowCount++;
}
colCount = maze[row].length;

}
tagStr.append("\n");
}

titleBuf.append(tagStr);
titleBuf.append(lineDraw(colCount));
titleBuf.append("\n");
return titleBuf.toString();
}

// -----------------------------------------------------------------
// Returns the the number title format of string as stringbuffer.
// It read the number of column, divided by 10.
// If the number is less than 10, print " " string.
// if 10 is reached, print 1. To drop after 10, filter out by modular
// number.
// The second line is mod by 10 to keep 0-9 repeat
// -----------------------------------------------------------------
StringBuffer sbuf = new StringBuffer();
sbuf.append("   ");
for (int i = 1; i <= colSize; i++) {
// divide by 10
if (i / 10 > 0) {
// print only 10 mod number
if (i % 10 == 0) {
sbuf.append(i / 10);
} else {
sbuf.append(" ");
}
} else {
sbuf.append(" ");
}
}
sbuf.append("\n");
sbuf.append("   ");

for (int i = 1; i <= colSize; i++) {
sbuf.append(i % 10);
}

sbuf.append("\n");
return sbuf;
}

// -----------------------------------------------------------------
// Returns the line draw as stringbuffer.
// The first and last symbol is "+", and others "=".
// -----------------------------------------------------------------
private StringBuffer lineDraw(int colSize) {

StringBuffer tbuf = new StringBuffer();
int formatSize = colSize + 2;
tbuf.append("  ");
for (int i = 0; i < formatSize; i++) {
if (i == 0 || i == formatSize - 1) {

tbuf.append("+");
} else {
tbuf.append("-");
}
}
return tbuf;
}

}

```

Ok so far it is doing what it is suppose to be doing for the function that if the starting positions are invalid it will request the user to ask for another set of locations for a starting point, if the starting point happens to be at the Exit 'E' then it will ask the user again for another set of starting point. The issue I am running into here is that how can I input the character S into the mazeArray when the user inputs a correct set for starting point?

Here are my outputs
```            1         2
12345678901234567890
+--------------------+
1|    ###   #      #  |1
2|###   ### # #   ####|2
3|#####   #     ###   |3
4|E  #### # ##   #  # |4
5| # ## # # ####   ## |5
6|        #  ##  #### |6
7|## ###  ## ## ###   |7
8|   #### ## ####### #|8
9| # ## #### ##      #|9
10| #         ## ## ###|10
+--------------------+
1         2
12345678901234567890

Starting point? row: -3
col: 5
Illegal starting position; try again
Starting point? row: 4
col: 1
Try again - you cannot start at the exit
Starting point? row: 2
col: 12
1         2
12345678901234567890
+--------------------+
1|    ###   #      #  |1
2|###   ### # #   ####|2
3|#####   #     ###   |3
4|E  #### # ##   #  # |4
5| # ## # # ####   ## |5
6|        #  ##  #### |6
7|## ###  ## ## ###   |7
8|   #### ## ####### #|8
9| # ## #### ##      #|9
10| #         ## ## ###|10
+--------------------+
1         2
12345678901234567890

```

### #12 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Traversing a Maze

Posted 01 December 2012 - 05:14 AM

You're coming along well, but your approach for getting the starting point from the user is incorrect. You need a loop, usually a do/while loop so the loop executes at least once but will continue to ask for user input until valid values are obtained. I think you'll see other issues with the validation logic once you do this part correctly:
```do
{
// get row, column from user

// validate user input
}
while ( !inputValid )

// set the valid starting point to 'S'
```

### #13 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 01 December 2012 - 08:24 PM

```import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;

public class Proj71773 {

static char[][] mazeArray = new char[10][20];

public static void main(String[] args) throws FileNotFoundException,
IOException {

try {

File inputFile = new File (args [0]);
//File inputFile = new File("C:\\dev\\test\\src\\maze.txt");

String lineLn = " ";
int row = 0;

mazeArray[row++] = lineLn.toCharArray();
}
} catch (FileNotFoundException e) {
// could not get Inputstream from file
e.printStackTrace();
} catch (IOException e) {
// problem with the inputstream while reading
e.printStackTrace();
} finally {
// close all files & inpusStreams

}

// instantiate your maze class here
Maze maze = new Maze(mazeArray);
// test output print
System.out.println(maze);
maze.location();
System.out.println(maze.toString());
maze.traverse(maze.getStartRowNumber(), maze.getStartColumnNumber());
}

}

class Maze {

private char[][] maze = new char[10][20];
private final int TRIED = 3;
private final int PATH = 7;
private final char E = 'E';

private int startRowNumber = 0;
private int startColumnNumber = 0;

// constructor with argument char 2-d array from input file
public Maze(char[][] maze) {
super();
this.maze = maze;
}

// getter/setter for starting row
public int getStartRowNumber() {
return this.startRowNumber;
}

public void setStartRowNumber(int row) {
this.startRowNumber = row;
}

// getter/setter for starting column
public int getStartColumnNumber() {
return this.startColumnNumber;
}

public void setStartColumnNumber(int col) {
this.startColumnNumber = col;
}

public void location() {

Scanner scan = new Scanner(System.in);
int i;
int j;
int maxTry = 10;
// set up max try to keep looping in case of invalid try

int numberAttempted = 0;

System.out.print("Starting point? row: ");
i = scan.nextInt();

System.out.print("		col: ");
j = scan.nextInt();

// set up some loop until getting valid result
// if the maximum tried, then kick out
for (int tried = 0; tried < maxTry; tried++) {
boolean isInValidPoistion = isValidPosition(i, j);
if (isInValidPoistion == true) {
// if the char is in right position
// and value is '0', then it's right
if (maze[i-1][j-1] == '0') {
// add 'S' char here and return
maze[i-1][j-1] = 'S';

// record starting row & column number here
// to start traverse method
setStartRowNumber(i);
setStartColumnNumber(j);
// if it right, get out of looping and skip the rest
break;
} else if (maze[i-1][j-1] == E) {
// add filtering logic to catch 'E' char here
// because it's valid position
System.out
.println("Try again - you cannot start at the exit");
System.out.print("Starting point? row: ");
i = scan.nextInt();
System.out.print("		col: ");
j = scan.nextInt();
} else {
// it's '1' and other invalid cases
// you cannot start if the value is '1'.
System.out
.println("Illegal starting position, try again");
System.out.print("Starting point? row: ");
i = scan.nextInt();
System.out.print("		col: ");
j = scan.nextInt();
}
} else {
System.out.println("Illegal starting position, try again");
System.out.print("Starting point? row: ");
i = scan.nextInt();
System.out.print("		col: ");
j = scan.nextInt();
}
numberAttempted++;
}

}

// -----------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
// ----------------------------------------------------------------
public boolean traverse(int row, int column) {
boolean done = false;
if (valid(row, column)) {
maze[row][column] = TRIED;

if (row == E && column == E) {
done = true;
} else {
done = traverse(row + 1, column);
if (!done)
done = traverse(row, column + 1);
if (!done)
done = traverse(row - 1, column);
if (!done)
done = traverse(row, column - 1);
}

if (done) {
System.out.println("Maze solved");
maze[row][column] = PATH;

}
}
return done;
}

// -----------------------------------------------------------------
// Determines if a specific location is valid.
// -----------------------------------------------------------------
private boolean isValidPosition(int row, int column) {
boolean result = false;

if (row >= 0 && row < maze.length && column >= 0
&& column < maze[row].length) {
// just check here if it's in valid position
// location method will handle if it's a valid character
result = true;
}
return result;
}

// -----------------------------------------------------------------
// Determines if a specific location is valid.
// -----------------------------------------------------------------
private boolean valid(int row, int column ) {
boolean result = false;

if (row >= 0 && row < maze.length && column >= 0 && column < maze[row].length) {
// you got to read it as char, not int
if (maze[row][column] == '0') {
result = true;
}
}
return result;
}

// -----------------------------------------------------------------
// Returns the maze as a string.
// -----------------------------------------------------------------
public String toString() {
StringBuffer titleBuf = new StringBuffer();
StringBuffer tagStr = new StringBuffer();
tagStr.append("\n");

int rowCount = 1;
int colCount = 0;

for (int row = 0; row < maze.length; row++) {

if (row == 0 || row == maze[row].length - 1) {
titleBuf.append(lineDraw(maze[row].length));
}

for (int column = 0; column < maze[row].length; column++) {

// padding row # & pipe symbol in left end
if (column == 0) {
// padding an empty space for single digit number
if (rowCount < 10) {
tagStr.append(" ");
}
// print row count & pipe symbol
tagStr.append(rowCount);
tagStr.append("|");
}

if (maze[row][column] == E) {
tagStr.append("E");
} else if (maze[row][column] == '1') {
tagStr.append("#");
} else if (maze[row][column] == 'S') {
tagStr.append("S");
// for extra credit
} else if (maze[row][column] == '+') {
tagStr.append("+");
} else {
tagStr.append(" ");
}

// testing
// tagStr.append(maze[row][column]);
// padding row # & pipe symbol in right end
if (column == maze[row].length - 1) {
tagStr.append("|");
tagStr.append(rowCount);
rowCount++;
}
colCount = maze[row].length;

}
tagStr.append("\n");
}

titleBuf.append(tagStr);
titleBuf.append(lineDraw(colCount));
titleBuf.append("\n");
return titleBuf.toString();
}

// -----------------------------------------------------------------
// Returns the the number title format of string as stringbuffer.
// It read the number of column, divided by 10.
// If the number is less than 10, print " " string.
// if 10 is reached, print 1. To drop after 10, filter out by modular
// number.
// The second line is mod by 10 to keep 0-9 repeat
// -----------------------------------------------------------------
StringBuffer sbuf = new StringBuffer();
sbuf.append("   ");
for (int i = 1; i <= colSize; i++) {
// divide by 10
if (i / 10 > 0) {
// print only 10 mod number
if (i % 10 == 0) {
sbuf.append(i / 10);
} else {
sbuf.append(" ");
}
} else {
sbuf.append(" ");
}
}
sbuf.append("\n");
sbuf.append("   ");

for (int i = 1; i <= colSize; i++) {
sbuf.append(i % 10);
}

sbuf.append("\n");
return sbuf;
}

// -----------------------------------------------------------------
// Returns the line draw as stringbuffer.
// The first and last symbol is "+", and others "=".
// -----------------------------------------------------------------
private StringBuffer lineDraw(int colSize) {

StringBuffer tbuf = new StringBuffer();
int formatSize = colSize + 2;
tbuf.append("  ");
for (int i = 0; i < formatSize; i++) {
if (i == 0 || i == formatSize - 1) {

tbuf.append("+");
} else {
tbuf.append("-");
}
}
return tbuf;
}

}

```

Output
[/code]
1 2
12345678901234567890
+--------------------+
1| ### # # |1
2|### ### # # ####|2
3|##### # ### |3
4|E #### # ## # # |4
5| # ## # # #### ## |5
6| # ## #### |6
7|## ### ## ## ### |7
8| #### ## ####### #|8
9| # ## #### ## #|9
10| # ## ## ###|10
+--------------------+
1 2
12345678901234567890

Starting point? row: 4
col: 1
Try again - you cannot start at the exit
Starting point? row: 2
col: 1
Illegal starting position, try again
Starting point? row: 1
col: 1
1 2
12345678901234567890
+--------------------+
1|S ### # # |1
2|### ### # # ####|2
3|##### # ### |3
4|E #### # ## # # |4
5| # ## # # #### ## |5
6| # ## #### |6
7|## ### ## ## ### |7
8| #### ## ####### #|8
9| # ## #### ## #|9
10| # ## ## ###|10
+--------------------+
1 2
12345678901234567890
[/code]

The problem is it doesnt seem that the traverse method is not working correctly
Is something wrong with it? Do i need to change some things? Do I need to add more methods?

opps output
```            1         2
12345678901234567890
+--------------------+
1|    ###   #      #  |1
2|###   ### # #   ####|2
3|#####   #     ###   |3
4|E  #### # ##   #  # |4
5| # ## # # ####   ## |5
6|        #  ##  #### |6
7|## ###  ## ## ###   |7
8|   #### ## ####### #|8
9| # ## #### ##      #|9
10| #         ## ## ###|10
+--------------------+
1         2
12345678901234567890

Starting point? row: 4
col: 1
Try again - you cannot start at the exit
Starting point? row: 2
col: 1
Illegal starting position, try again
Starting point? row: 1
col: 1
1         2
12345678901234567890
+--------------------+
1|S   ###   #      #  |1
2|###   ### # #   ####|2
3|#####   #     ###   |3
4|E  #### # ##   #  # |4
5| # ## # # ####   ## |5
6|        #  ##  #### |6
7|## ###  ## ## ###   |7
8|   #### ## ####### #|8
9| # ## #### ##      #|9
10| #         ## ## ###|10
+--------------------+
1         2
12345678901234567890

```

### #14 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Traversing a Maze

Posted 02 December 2012 - 03:50 AM

Good job overcoming the handful of challenges you had when you last departed.

Yes, your traversal algorithm needs more work. If you won't think me unkind, I'll say lots more work, and I don't mean to be unkind but to prepare you for the road ahead.

For starters, the second line of the traverse() method:

if (valid(row, column))

What happens when the valid() method returns false? I think the answer is "nothing happens, and the program stops" and that's what you're seeing in the output you posted. So, obviously the traversal algorithm can't just stop if it attempts to go in an invalid direction or to an invalid location.

A couple thoughts:

The way you called traverse() from the main() method ignores the flag "done" that you've wisely included to determine if the puzzle has been solved. A better approach might be for the main() method to call another Maze method, say solveMaze(), that manages to guide the traverse() method to achieve the total solution to the puzzle, not just the next step.

The traverse() method is a good start, but you'll find that it needs to be built up quite a bit to account for the special cases that will come up: attempted moves outside the puzzle boundaries, dead ends (backtracking), puzzle locations with multiple exits to explore, etc.

There's lots to do, lots to discover. Keep at it.

### #15 J0hnnysmokes

Reputation: 0
• Posts: 16
• Joined: 30-November 12

## Re: Traversing a Maze

Posted 02 December 2012 - 04:19 AM

Ah yes I see, it seems like I have a lot of work to do,
However, if I may ask, can you give me a starting point for me to get ideas on the solveMaze() method that you suggested? I would really like to make that method but I wouldnt know where to being and how I would be able to call the traverse method to it and how that method would solve it.