1. Write a Java program that solves a maze Maze is an exciting puzzle game whose
ID: 3685786 • Letter: 1
Question
1. Write a Java program that solves a maze Maze is an exciting puzzle game whose goal is to find the path from a starting position (S) to an end position (E ).
2. Important functions for the program
Reading a maze file
After reading a maze file, the program executes finding a path of the maze.
The format of a maze file is like the following:
- The number of rows : 8
- The number of columns : 8
- The map of the maze (# : wall, ‘ ‘ : the road, S: a starting point, E: an ending point
3. Finding the path from S to E on a given maze
After receiving information related to direction from a user, the program executes to find the path to the position E.
The command that a user provides to the program has the following format. - Direction r: rightward, l: leftward, u: upward, d:downward
- The number of movements: a positive integer.
- Example
r 3 : moves 3 columns to the right
u 2 : moves 2 rows upward
4. Iterative execution based on menu.
Once the program starts, it shows a menu showing 1) Read a maze file, 2) Show the current maze map, 3) Start the game, 4) Exit. If one game ends, the program repeats this process until a user chooses ‘Exit’.
Explanation / Answer
public class RatMaze
{
final int N = 4;
/* 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++)
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 && x < N && y >= 0 &&
y < N && maze[x][y] == 1);
}
/* 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[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if (solveMazeUtil(maze, 0, 0, sol) == false)
{
System.out.print("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[][])
{
// if (x,y is goal) return true
if (x == N - 1 && y == N - 1)
{
sol[x][y] = 1;
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] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
/* If none of the above movements work then
BACKTRACK: unmark x,y as part of solution
path */
sol[x][y] = 0;
return false;
}
return false;
}
public static void main(String args[])
{
RatMaze rat = new RatMaze();
int maze[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
rat.solveMaze(maze);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.