Solution to Maze Solver

The solution to the implementation of classes and their inheritance along with methods to solving a maze in JavaScript.

We'll cover the following...

Final step to check if a maze is solvable

With helper methods ready and the maze in front of us, we can finally implement a solution. The method solve takes the source and target indices and to tell if the maze is solvable. Look at the solution below.

Press + to interact
index.js
grid.js
const Grid = require('./grid').gridClass;
// Create MazeSolver class below
class MazeSolver extends Grid{
constructor(arr){
super(arr); // initialize the grid
}
canTraverse(x,y){
// check bounds
if (x < 0 || y < 0)
return false;
else if (x >= this.grid.length)
return false;
else if (y >= this.grid[x].length)
return false;
// check if 0 or not
else if(this.grid[x][y]===0)
return false;
else
return true; // all passsed
}
getNeighbours(x,y){
// return array of neighbours
var neighbours = [];
// up
if(this.canTraverse(x-1, y))
neighbours.push([x-1,y]);
// down
if(this.canTraverse(x+1, y))
neighbours.push([x+1,y]);
// left
if(this.canTraverse(x, y-1))
neighbours.push([x,y-1]);
// right
if(this.canTraverse(x, y+1))
neighbours.push([x,y+1]);
return neighbours;
}
checkVisited(x,y,visited){
// traverse array for visited
// console.log(x,y,visited)
for(var i= 0; i< visited.length; i++){
if(visited[i][0]=== x && visited[i][1]===y){
return true;
}
}
return false;
}
solve(x1,y1, x2, y2){
// solve from coordinates (x, y)
var stack = []; // maintain coordinates
var visited = [];
// check if initial position can be traversed
if(this.canTraverse(x1,y1)){
visited.push([x1,y1]);
stack.push([x1,y1]);
}
var solved = false;
while(stack.length > 0){
var currentPos = stack.pop();
if(currentPos[0] === x2 && currentPos[1] === y2){
// target found and so exit loop
solved = true;
break;
}
// target not found and so traverse neighbours
var neighbours = this.getNeighbours(currentPos[0], currentPos[1]);
for(var i = 0; i < neighbours.length; i++){
// check visited and if not, throw in stack
if (!this.checkVisited(neighbours[i][0],neighbours[i][1],visited)){
visited.push([neighbours[i][0],neighbours[i][1]]);
stack.push([neighbours[i][0],neighbours[i][1]]);
}
}
}
return solved;
}
}
var arr = [
[0, 1, 1, 1, 0],
[0, 1, 1, 1, 0],
[0, 1, 1, 1, 0],
[0, 1, 1, 1, 0],
[0, 1, 1, 1, 0],
]
var maze = new MazeSolver(arr);
console.log("check solavable -> source (0, 1) and Dest (4,3):")
console.log(maze.solve(0,1,4,3));
console.log("check solavable -> source (0, 0) and Dest (4,3):")
console.log(maze.solve(0,0,4,3));
console.log("check solavable -> source (0, 1) and Dest (3,3):")
console.log(maze.solve(0,1,3,3));
console.log("check solavable -> source (0, 1) and Dest (4,4):")
console.log(maze.solve(0,1,4,4));

The solve method takes 2 pairs of coordinates; x1 and y1are the source while x2 and y2are the destination indices. The solution works like this.

  • Initialize an empty array to track which indices to traverse next by the name of ...