Java Maze Solver

 

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Comparator;
	import java.util.Optional;
	public class RatMaze {
	final int N = 7;
	void printSolution(int sol[][], int[][] visited, int[][] distances) {
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++)
	System.out.print (" " + sol[i][j] + " ");
	System.out.println ();
	}
	System.out.println ();
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++)
	System.out.print (" " + visited[i][j] + " ");
	System.out.println ();
	}
	System.out.println ();
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++)
	System.out.print (" " + distances[i][j] + " ");
	System.out.println ();
	}
	}
	boolean isSafe(int maze[][], int x, int y, int visited[][], int[][] distances, int distance) {
	return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1 && (visited[x][y] == 0 || (visited[x][y] == 1 && distances[x][y] >= distance)));
	}
	boolean solveMaze(int maze[][]) {
	int sol[][] = {
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0}};
	int visited[][] = {
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0}};
	int distances[][] = {
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0}};
	Result result = solveMazeUtil (maze, 0, 0, sol, visited, distances, 1);
	if (result.distance == Integer.MAX_VALUE) {
	System.out.print ("Solution doesn't exist");
	return false;
	}
	printSolution (result.sol, visited, distances);
	return true;
	}
	class Result {
	int distance;
	int[][] sol;
	public Result(int distance, int[][] sol) {
	this.distance = distance;
	this.sol = sol;
	}
	}
	Result solveMazeUtil(int maze[][], int x, int y, int sol[][], int visited[][], int distances[][], int distance) {
	// if (x, y is goal) return true
	if (x == N - 1 && y == N - 1) {
	sol[x][y] = 1;
	return new Result (distance, sol);
	}
	if (isSafe (maze, x, y, visited, distances, distance) == true) {
	int solTmp = sol[x][y];
	sol[x][y] = 1;
	int tmpVisit = visited[x][y];
	visited[x][y] = 1;
	int tmpDist = distances[x][y];
	distances[x][y] = distance;
	ArrayList<Result> results = new ArrayList<> ();
	Result down = solveMazeUtil (maze, x + 1, y, sol, visited, distances, distance + 1);
	if(down.distance != Integer.MAX_VALUE){
	results.add (down);
	}
	Result up = solveMazeUtil (maze, x - 1, y, sol, visited, distances, distance + 1);
	if(up.distance != Integer.MAX_VALUE){
	results.add (up);
	}
	Result right = solveMazeUtil (maze, x, y + 1, sol, visited, distances, distance + 1);
	if(right.distance != Integer.MAX_VALUE){
	results.add (right);
	}
	Result left = solveMazeUtil (maze, x, y - 1, sol, visited, distances, distance + 1);
	if(left.distance != Integer.MAX_VALUE){
	results.add (left);
	}
	Optional<Result> min = Arrays.asList (new Result[]{up, down, right, left}).stream ().
	min (Comparator.comparingInt (r -> r.distance));
	if(min.get () != null){
	return min.get ();
	}
	sol[x][y] = solTmp;
	visited[x][y] = tmpVisit;
	distances[x][y] = tmpDist;
	return new Result (Integer.MAX_VALUE, sol);
	}
	return new Result (Integer.MAX_VALUE, sol);
	}
	public static void main(String args[]) {
	RatMaze rat = new RatMaze ();
	int maze[][] = {
	{1, 0, 0, 1, 1, 1, 0},
	{1, 1, 0, 1, 0, 1, 1},
	{0, 1, 0, 1, 0, 0, 1},
	{0, 1, 0, 1, 0, 0, 1},
	{0, 1, 0, 1, 1, 1, 1},
	{0, 1, 0, 1, 0, 0, 1},
	{1, 1, 1, 1, 1, 1, 1}
	};
	rat.solveMaze (maze);
	}
	}

view raw RatMaze.java hosted with ❤ by GitHub