Question

For this homework you will be making a maze solver. Your program will take in from a file 2 things. The size of the square maze, and the maze itself. The maze will consists of numbers between 0 and 3, where 0 is the start of the maze, 1 is an open path, 3 is a wall, and 2 is the end of the maze. For example a 6x6 maze could be represented by the following file, there will be no spaces seperating the elements of the maze:

6
011113
333311
111113
331333
331111
333332

Your program must then solve the maze. It will then output the correct path through the maze marked by 0’s to the command line. For example for the maze above it may output the following solution(I added spaces to make it more readable not necessary):

000003 333301 110003 330333 330000 333330

You can assume that the input contains the exact amount of numbers needed and that it is a solvable maze, following the rules outlined above.

Save your program as a “Homework2.java” file. Your program should read from a file named “in.txt” if you have your program read from a different file you may recieve no credit for this assignment.

1

Your program does not need to find the shortest path, just a path from the start to the finish. For example on the following maze:

3 011 131 211

The following is an acceptable solution to the problem:

000 130 000

While the shortest path is actually the following:

011 031 011

You may also assume that the maze will be no larger than 40x40

1.1 Hints

• Recursion is your friend.
• Store the maze as a 2D array.
• Remember that arrays are pass by reference not value.

2 Extra Credit

For extra credit have your program find the shortest solution.

Answer 1

import java.util.Arrays;
import java.util.Scanner;

public class Homework2 {

private static int N = 4;

public Homework2(int n) {
N = n;
}

/* A utility function to print solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if(sol[i][j] == 1)
sol[i][j] = 0;
System.out.print(sol[i][j]);
}
System.out.println();
}
}

/* A utility function to check if x,y is valid
index for N*N maze */
boolean isSafe(int maze[][], int x, int y)
{
// if (x,y outside maze) return false
return ((x == 0 && y == 0) || (x >= 0 && x < N && y >= 0 &&
y < N && (maze[x][y] == 1 || maze[x][y] == 2)));
}

/* This function solves the Maze problem using
Backtracking. It mainly uses solveMazeUtil()
to solve the problem. It returns false if no
path is possible, otherwise return true and
prints the path in the form of 1s. Please note
that there may be more than one solutions, this
function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int sol[][] = new int[N][N];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
sol[i][j] = maze[i][j];
  
int visted[][] = new int[N][N];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
visted[i][j] = 0;
if (solveMazeUtil(maze, 0, 0, sol, visted) == false)
{
System.out.println("Solution doesn't exist");
return false;
}

printSolution(sol);
return true;
}

/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][], int visited[][])
{
// if (x,y is goal) return true
if (x == N - 1 && y == N - 1)
{
sol[x][y] = 2;
return true;
}

// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 0;
  
/* If moving in x direction doesn't give
solution then Move down in y direction */
if ((y -1) >= 0 && visited[x][y-1] == 0)
{
visited[x][y-1] = 1;
if(solveMazeUtil(maze, x, y - 1, sol, visited))
return true;
}

/* Move forward in x direction */
if ((x+1) < N && visited[x+1][y] == 0)
{
visited[x+1][y] = 1;
if(solveMazeUtil(maze, x+1, y, sol, visited))
return true;
}
if ((y +1) < N && visited[x][y+1] == 0)
{
visited[x][y+1] = 1;
if(solveMazeUtil(maze, x, y + 1, sol, visited))
return true;
}

  
/* If none of the above movements work then
BACKTRACK: unmark x,y as part of solution
path */
sol[x][y] = maze[x][y];
return false;
}

return false;
}

public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter size of maze: ");
int n = sc.nextInt();
Homework2 hw = new Homework2(n);
int maze[][] = new int [n][n];
sc.nextLine();
for(int i = 0; i < n; i++)
{
String str = sc.nextLine();
for (int j = 0; j < str.length(); j++)
{
maze[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
}
}
  
System.out.println();
sc.close();
hw.solveMaze(maze);
}
}