Traversing a Maze

• (2 Pages)
• 1
• 2

22 Replies - 4647 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=cc8c43a87910a15623b3fe97791a51e8&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#16 GregBrannon

• D.I.C Lover

Reputation: 2216
• Posts: 5,241
• Joined: 10-September 10

Re: Traversing a Maze

Posted 02 December 2012 - 04:46 AM

Well, for starters, the solveMaze() method would call the traverse method with the starting point and ensure that the solve process continues until the flag done = true. What it does after that depends on what traverse() does while it runs its course.

You said that traverse() is meant to be a recursive solver, and that's fine, but there may be desirable limits to the recursion to (again) simplify the code. If you think you have a requirement to never leave traverse() once it has been entered until a total solution is found, then what solveMaze() can do to help will be limited.

If allowed, solveMaze() could be used to keep track of the state of the traversal, whether it's moving forward or backward, restarting it from the last location with available moves, etc. This can also be done inside traverse() with flags, but simplifying traverse()'s tasks with outside help will reduce its complexity.

Stacks or a single stack can be used to keep track of the solver's progress through the puzzle. As each location is visited, push that location to the stack. Then if the solver comes to a dead end, pop the locations visited from the stack to backtrack to the last location with remaining possible moves or exits. If you don't want to use a stack, then another marker for puzzle locations that have moves/exits remaining may be necessary so that the solver can tell when to stop backtracking.

You already know that traverse() needs to look before it leaps to the puzzle location that has been passed to it. That's what I believe you intended to do with your if ( valid() ) call, but you'll need to expand that some. Or, you could consider first validating the puzzle locations sent to traverse().

As I said, lots to discover. There is a tutorial here on DIC in the Java tutorial section that discusses backtracking. You might review that for ideas.

#17 J0hnnysmokes

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

Re: Traversing a Maze

Posted 02 December 2012 - 08:06 AM

hmm definitely having trouble with the traverse method
Yes I am trying to only use the traverse method using recursion but so far I still do not have a clue on how to accurately do it
Here is what I have so far

```class Maze {

private char[][] maze;
private static final char E = 'E';
private int startRowNumber = 0;
private int startColumnNumber = 0;
private boolean done = false;
private static final char PATH = 'P';
private static final char TRIED = 'T';

// 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 column) {
this.startColumnNumber = column;
}

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 if (maze[i-1][j-1] == '1'){
// 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) {
done = false;

if (valid(row, column)){
if ((row == E) && (column == E)){
System.out.println("I am free!");
System.out.println(maze + " " + row + "," + column);
done = true;
}
else
{
if (traverse(row+1, column) ||
traverse(row, column+1) ||
traverse(row-1, column) ||
traverse(row, column-1)){
maze[row][column] = PATH;
return true;
}

}

} else if (valid(row, column)){
System.out.println("Help, I am trapped!");
System.out.println(maze[row][column] + " " + row + "," + column);
done = true;
}
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;
if (row > 0 && row < maze.length && column > 0
&& column < maze[row].length)  // checks if it is within the maze bounds

if (maze[row][column] == TRIED || maze[row][column] == '1') //checks if there is a wall or we have already went there
return false;

return true;
}

```

#18 GregBrannon

• D.I.C Lover

Reputation: 2216
• Posts: 5,241
• Joined: 10-September 10

Re: Traversing a Maze

Posted 02 December 2012 - 08:21 AM

What does this construct from traverse() accomplish?:
```if (valid(row, column))
{
// do this
}
else if (valid(row, column))
{
// do this
}
```

Maybe you're getting tired and need to take a break.

#19 J0hnnysmokes

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

Re: Traversing a Maze

Posted 02 December 2012 - 08:47 AM

Here is an updated version of my traverse method
```public boolean traverse(int row, int column) {
done = false;

if (maze[row][column] == 'E'){
System.out.println("I am free!");
done = true;
}
else if (!valid(row, column)){
done = false;
}
else {
maze[row][column] = TRIED;
} while (!done){
if (maze[row-1][column] == '0' || maze[row-1][column] == 'E'){
row = row-1;
column = column;
done = traverse(row-1, column);
}
if (maze[row][column+1] == '0' || maze[row][column+1] == 'E' ){
row = row;
column = column+1;
done = traverse(row, column+1);
}
if (maze[row+1][column] == '0' || maze[row+1][column] == 'E'){
row = row+1;
column = column;
done = traverse(row+1, column);
}
if (maze[row][column+1] == '0' || maze[row][column+1] == 'E'){
row = row;
column = column+1;
done = traverse(row, column+1);
}
}

return done;

}

```

and my valid method
```	private boolean valid(int row, int column ) {
boolean result;
if (row > 0 && row < maze.length && column > 0
&& column < maze[row].length)  // checks if it is within the maze bounds

if (maze[row][column] == TRIED || maze[row][column] == '1') //checks if there is a wall or we have already went there
return false;

return true;
}

```

However, it is giving me errors
```            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: 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

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Maze.traverse(Proj71773.java:170)
at Maze.traverse(Proj71773.java:183)
at Proj71773.main(Proj71773.java:52)

```

any ideas?

#20 J0hnnysmokes

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

Re: Traversing a Maze

Posted 02 December 2012 - 10:45 AM

Ok so I think i FINALLY got everything down
but here comes the dreaded debugging part
I have inputted a different maze text file that has 10*row and 19*columns and I think atleast 2 locations when there will be one empty space surrounded by walls

Here are my issues
1) whenever I try to make a starting position at a location that is surrounded by walls my program keeps looping ("illegal starting point try again") where it is suppose to end the traverse method by stating that the maze has no solution from that point therefore it should print ("help I am trapped!")

2) BIG ISSUE
for odd reason whenever I try to input the coordinated row:2, col: 12 it gives me a bunch of errors saying ArrayIndexOutOfBoundsException

I believe it has something to do with my traverse method, the method for storing the user inputted data into my maze, and the validation method. However I am having trouble making printlns on every method to see what is going wrong

Here is my updated code
```import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;
import java.util.HashMap;

public class Proj71773 {

static int rowSize = 10;
static int columnSize = 20;

static char[][] mazeArray = new char[rowSize][columnSize];

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

try {

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

String lineLn = " ";
int row = 0;

mazeArray[row++] = lineLn.toCharArray();
}
} catch (FileNotFoundException e) {
//problem with getting 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);
System.out.println(maze);
maze.location();
System.out.println(maze.toString());

boolean solved = maze.traverse(maze.getStartRowNumber(), maze.getStartColumnNumber());

if (solved == true) {

//EXTRA CREDIT, I WISH TO RECEIVE MORE THAN 15%!!!!
maze.recoverStartPos(maze.getStartRowNumber(), maze.getStartColumnNumber());
System.out.println(maze.toString());
System.out.println("I am free!");
} else {
System.out.println("Help, I am trapped!");
}
}

}

class Maze {

private int rowSize = 10;
private int columnSize = 20;
private char[][] maze = new char[rowSize][columnSize];
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

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 if (maze[i-1][j-1] == '1'){
// 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();
}

}

}

// -----------------------------------------------------------------
// 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) throws ArrayIndexOutOfBoundsException {

boolean done = false;

if (valid(row, column) == true && maze[row-1][column-1] == E) {
return true;

}
else if (valid(row, column) == false){
return false;
}
else {

maze[row-1][column-1] = '+';
if ( traverse(row-1, column)){
done = true;
} else if (traverse(row, column+1) ){
done = true;
} else if (traverse(row+1, column) ){
done = true;
} else if (traverse(row, column-1)){
return true;
} else {
maze[row-1][column-1] = ' ';
done = false;
}
}
return done;

}

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

if (row > 0 && row < rowSize && column > 0
&& column < columnSize) {
// 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 <= rowSize && column > 0 && column <= columnSize){

if (maze[row-1][column-1] == '0' || maze[row-1][column-1] == 'S' || maze[row-1][column-1] == 'E') {
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;
}

public void recoverStartPos(int row, int col){
maze[row-1][col-1] = 'S';
}

}

```

here is the new maze input data
0000111000100000010
1110001110101000111
1111100010000011100
E001111010110001001
0101101010111100011
0000000010011001111
1101110011011011100
0001111011011111110
0101101111011010101
0100000000011011011

And here is my output when I try certain input locations such as row:1, col:19
```          1
1234567890123456789
+-------------------+
1|    ###   #      # |1
2|###   ### # #   ###|2
3|#####   #     ###  |3
4|E  #### # ##   #  #|4
5| # ## # # ####   ##|5
6|        #  ##  ####|6
7|## ###  ## ## ###  |7
8|   #### ## ####### |8
9| # ## #### ## # # #|9
10| #         ## ## ##|10
+-------------------+
1
1234567890123456789

Starting point? row: 1
col: 19
1
1234567890123456789
+-------------------+
1|    ###   #      #S|1
2|###   ### # #   ###|2
3|#####   #     ###  |3
4|E  #### # ##   #  #|4
5| # ## # # ####   ##|5
6|        #  ##  ####|6
7|## ###  ## ## ###  |7
8|   #### ## ####### |8
9| # ## #### ## # # #|9
10| #         ## ## ##|10
+-------------------+
1
1234567890123456789

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 19
at Maze.valid(Proj71773.java:237)
at Maze.traverse(Proj71773.java:185)
at Maze.traverse(Proj71773.java:197)
at Proj71773.main(Proj71773.java:54)

```

#21 GregBrannon

• D.I.C Lover

Reputation: 2216
• Posts: 5,241
• Joined: 10-September 10

Re: Traversing a Maze

Posted 02 December 2012 - 11:05 AM

Lines 189 and 191 both add 1 to either the row or column before calling traverse(), and that will eventually bite you unless you include a check that the resulting numbers stay within the array's boundaries.

#22 J0hnnysmokes

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

Re: Traversing a Maze

Posted 02 December 2012 - 11:16 AM

Ok so I fixed what you said
```public boolean traverse(int row, int column) throws ArrayIndexOutOfBoundsException {

boolean done = false;

if (valid(row-1, column-1) == true && maze[row-1][column-1] == E) {
return true;

}
else if (valid(row-1, column-1) == false){
return false;
}
else {

maze[row-1][column-1] = '+';
if ( traverse(row-1, column)){
done = true;
} else if (traverse(row, column+1) ){
done = true;
} else if (traverse(row+1, column) ){
done = true;
} else if (traverse(row, column-1)){
return true;
} else {
maze[row-1][column-1] = ' ';
done = false;
}
}
return done;

}

```

However, once again when I input the coordinated
row: 2, col: 12
it seems that my traverse method stops working because it is automatically printing that the maze doesnt have a solution
```            1
1234567890123456789
+-------------------+
1|    ###   #      # |1
2|###   ### # #   ###|2
3|#####   #     ###  |3
4|E  #### # ##   #  #|4
5| # ## # # ####   ##|5
6|        #  ##  ####|6
7|## ###  ## ## ###  |7
8|   #### ## ####### |8
9| # ## #### ## # # #|9
10| #         ## ## ##|10
+-------------------+
1
1234567890123456789

Starting point? row: 2
col: 12
1
1234567890123456789
+-------------------+
1|    ###   #      # |1
2|###   ### #S#   ###|2
3|#####   #     ###  |3
4|E  #### # ##   #  #|4
5| # ## # # ####   ##|5
6|        #  ##  ####|6
7|## ###  ## ## ###  |7
8|   #### ## ####### |8
9| # ## #### ## # # #|9
10| #         ## ## ##|10
+-------------------+
1
1234567890123456789

Help, I am trapped!

```

but clearly it should have a solution

oh i see i fixed the wrong code haha
hmmm how can I fix this problem?
would inserting a for loop into my valid method reading the array help?
because the valid method was suppose to check that the locations are valid and if the moves are valid and within the array

#23 GregBrannon

• D.I.C Lover

Reputation: 2216
• Posts: 5,241
• Joined: 10-September 10

Re: Traversing a Maze

Posted 02 December 2012 - 11:44 AM

I added a statement to the beginning of the traverse() method that prints the coordinates being checked. The results are below. You might find tracing what the traverse() method is doing helpful.

The whole output is telling, but the last 5 or so lines show why the traverse() method is confused.

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

Starting point? row: 1
col: 10
1
1234567890123456789
+-------------------+
1|    ###  S#      # |1
2|###   ### # #   ###|2
3|#####   #     ###  |3
4|E  #### # ##   #  #|4
5| # ## # # ####   ##|5
6|        #  ##  ####|6
7|## ###  ## ## ###  |7
8|   #### ## ####### |8
9| # ## #### ## # # #|9
10| #         ## ## ##|10
+-------------------+
1
1234567890123456789

The coordinates being checked are: 1, 10
The coordinates being checked are: 0, 10
The coordinates being checked are: 1, 11
The coordinates being checked are: 2, 10
The coordinates being checked are: 1, 10
The coordinates being checked are: 2, 11
The coordinates being checked are: 3, 10
The coordinates being checked are: 2, 10
The coordinates being checked are: 3, 11
The coordinates being checked are: 2, 11
The coordinates being checked are: 3, 12
The coordinates being checked are: 2, 12
The coordinates being checked are: 1, 12
The coordinates being checked are: 0, 12
The coordinates being checked are: 1, 13
The coordinates being checked are: 0, 13
The coordinates being checked are: 1, 14
The coordinates being checked are: 0, 14
The coordinates being checked are: 1, 15
The coordinates being checked are: 0, 15
The coordinates being checked are: 1, 16
The coordinates being checked are: 0, 16
The coordinates being checked are: 1, 17
The coordinates being checked are: 0, 17
The coordinates being checked are: 1, 18
The coordinates being checked are: 2, 17
The coordinates being checked are: 1, 16
The coordinates being checked are: 2, 16
The coordinates being checked are: 1, 16
The coordinates being checked are: 2, 17
The coordinates being checked are: 3, 16
The coordinates being checked are: 2, 15
The coordinates being checked are: 1, 15
The coordinates being checked are: 2, 16
The coordinates being checked are: 3, 15
The coordinates being checked are: 2, 14
The coordinates being checked are: 1, 14
The coordinates being checked are: 2, 15
The coordinates being checked are: 3, 14
The coordinates being checked are: 2, 14
The coordinates being checked are: 3, 15
The coordinates being checked are: 4, 14
The coordinates being checked are: 3, 14
The coordinates being checked are: 4, 15
The coordinates being checked are: 3, 15
The coordinates being checked are: 4, 16
The coordinates being checked are: 5, 15
The coordinates being checked are: 4, 15
The coordinates being checked are: 5, 16
The coordinates being checked are: 4, 16
The coordinates being checked are: 5, 17
The coordinates being checked are: 4, 17
The coordinates being checked are: 3, 17
The coordinates being checked are: 4, 18
The coordinates being checked are: 3, 18
The coordinates being checked are: 2, 18
The coordinates being checked are: 4, 18
The coordinates being checked are: 3, 17
The coordinates being checked are: 5, 18
The coordinates being checked are: 4, 17
The coordinates being checked are: 5, 17
The coordinates being checked are: 4, 16
The coordinates being checked are: 5, 18
The coordinates being checked are: 6, 17
The coordinates being checked are: 5, 16
The coordinates being checked are: 6, 16
The coordinates being checked are: 5, 15
The coordinates being checked are: 6, 15
The coordinates being checked are: 5, 15
The coordinates being checked are: 6, 16
The coordinates being checked are: 7, 15
The coordinates being checked are: 6, 14
The coordinates being checked are: 5, 14
The coordinates being checked are: 6, 15
The coordinates being checked are: 7, 14
The coordinates being checked are: 6, 14
The coordinates being checked are: 7, 15
The coordinates being checked are: 8, 14
The coordinates being checked are: 7, 13
The coordinates being checked are: 6, 13
The coordinates being checked are: 5, 14
The coordinates being checked are: 4, 14
The coordinates being checked are: 5, 14
The coordinates being checked are: 4, 13
The coordinates being checked are: 3, 13
The coordinates being checked are: 2, 13
The coordinates being checked are: 3, 14
The coordinates being checked are: 4, 13
The coordinates being checked are: 3, 12
The coordinates being checked are: 4, 14
The coordinates being checked are: 5, 13
The coordinates being checked are: 4, 12
The coordinates being checked are: 3, 13
The coordinates being checked are: 2, 13
The coordinates being checked are: 1, 15
The coordinates being checked are: 2, 15
The coordinates being checked are: 1, 14
The coordinates being checked are: 2, 14
The coordinates being checked are: 1, 13
The coordinates being checked are: 2, 13
The coordinates being checked are: 1, 12
The coordinates being checked are: 2, 12
The coordinates being checked are: 1, 11
The coordinates being checked are: 2, 13
The coordinates being checked are: 3, 12
The coordinates being checked are: 2, 11
The coordinates being checked are: 3, 13
The coordinates being checked are: 4, 12
The coordinates being checked are: 3, 11
The coordinates being checked are: 4, 11
The coordinates being checked are: 3, 10
The coordinates being checked are: 4, 10
The coordinates being checked are: 3, 10
The coordinates being checked are: 4, 11
The coordinates being checked are: 5, 10
The coordinates being checked are: 4, 10
The coordinates being checked are: 5, 11
The coordinates being checked are: 6, 10
The coordinates being checked are: 5, 10
The coordinates being checked are: 6, 11
The coordinates being checked are: 5, 11
The coordinates being checked are: 6, 12
The coordinates being checked are: 7, 11
The coordinates being checked are: 6, 11
The coordinates being checked are: 7, 12
The coordinates being checked are: 8, 11
The coordinates being checked are: 7, 11
The coordinates being checked are: 8, 12
The coordinates being checked are: 9, 11
The coordinates being checked are: 8, 11
The coordinates being checked are: 9, 12
The coordinates being checked are: 9, 10
The coordinates being checked are: 8, 10
The coordinates being checked are: 7, 10
The coordinates being checked are: 6, 10
The coordinates being checked are: 7, 10
The coordinates being checked are: 6, 9
The coordinates being checked are: 5, 9
The coordinates being checked are: 4, 9
The coordinates being checked are: 3, 9
The coordinates being checked are: 2, 9
The coordinates being checked are: 1, 9
The coordinates being checked are: 0, 9
The coordinates being checked are: 1, 10
The coordinates being checked are: 2, 9
The coordinates being checked are: 1, 8
The coordinates being checked are: 0, 8
The coordinates being checked are: 1, 9
The coordinates being checked are: 2, 8
The coordinates being checked are: 1, 7
Help, I am trapped!

```