For this homework, you will be making a maze solver. Your program will take in f
ID: 3817876 • Letter: F
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 separating 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):
0
0
0
0
0
3
3
3
3
3
0
1
1
1
0
0
0
3
3
3
0
3
3
3
3
3
0
0
0
0
3
3
3
3
3
0
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.
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:
0 0 0
1 3 0
0 0 0
While the shortest path is actually the following:
0 1 1
0 3 1
0 1 1
You may also assume that the maze will be no larger than 40x40
"I need need the code to look very similar to this please" some of my classmates have already posted this and I can't have the same code.
0
0
0
0
0
3
3
3
3
3
0
1
1
1
0
0
0
3
3
3
0
3
3
3
3
3
0
0
0
0
3
3
3
3
3
0
Explanation / Answer
Please make sure you have file maze.txt containing maze details as posted in question and is present in same folder from where you are running the code.
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
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 printArray(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 (solveMaze(maze, 0, 0, sol, visted) == false)
{
System.out.println("Solution doesn't exist");
return false;
}
printArray(sol);
return true;
}
/* A recursive utility function to solve Maze
problem */
boolean solveMaze(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(solveMaze(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(solveMaze(maze, x+1, y, sol, visited))
return true;
}
if ((y +1) < N && visited[x][y+1] == 0)
{
visited[x][y+1] = 1;
if(solveMaze(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;
}
else
{
if (x < N && x >= 0 && y >= 0 && y < N)
{
sol[x][y] = maze[x][y];
}
}
return false;
}
public static void main(String args[]) throws IOException
{
FileReader fr = new FileReader("maze.txt");
Scanner sc = new Scanner(fr);
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();
fr.close();
hw.solveMaze(maze);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.