Solve A 2D Array Maze Using Recursion And JavaScript

To continue on the topic of popular interview questions for software engineering positions, I figured it might be appropriate to go over solving a maze that was created using a two-dimensional array.

A maze created from a 2D array can be solved using recursion similar to like we did for the previous Fibonacci article I made.

To keep the trend of my last two articles on interview questions, any code will be in JavaScript.

Let’s say we’ve got a two dimensional array, where the first dimension represents columns of a grid and the second dimension represents rows. More specifically lets think of the following:

var myMaze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];

The above 2D array is our maze. The zero values represent walls, the one values represent paths, and the value two represents the exit or goal of our maze.

So what are some things we must consider when trying to solve this maze? Well, we want to make sure we don’t traverse places we’ve been in a possible infinite loop and we don’t want to exceed the boundaries of our maze.

The goal here is to attempt a traversal in all directions as long as we’re on a path of one. With that said, we are just going to recursively call a traverse(column, row) function in four directions based on the current location. For each path value we land, we will change it to some other value to prevent traversing places we already visited. For these values any other that are not our goal, the traversal just dies off.

function MazeSolver(maze) {

    this.maze = maze;

    this.traverse = function(column, row) {
        if(this.maze[column][row] == 2) {
            console.log("We solved the maze at (" + column + ", " + row + ")");
        } else if(this.maze[column][row] == 1) {
            console.log("At valid position (" + column + ", " + row + ")");
            this.maze[column][row] = 9;
            if(column < this.maze.length - 1) {
                this.traverse(column + 1, row);
            }
            if(row < this.maze[column].length - 1) {
                this.traverse(column, row + 1);
            }
            if(column > 0) {
                this.traverse(column - 1, row);
            }
            if(row > 0) {
                this.traverse(column, row - 1);
            }
        }
    };

};

The above code represents a full class for traversing a maze.

Conclusion

Like the Fibonacci sequence post I did, solving a maze is another great way to demonstrate your ability to use recursion. Please share your experiences in the comments if you’ve had a question like this in a technical interview or think you can improve upon what I’ve done.

A video version of this article can be seen below.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.