Despite all my rage I am still just a rat in a maze

By | September 30, 2013

Wait, … I don’t think I have the lyrics quite right. In any event I thought I’d post a maze solving solution that I came up with after being asked to provide one during an interview.

I was once asked on an interview to come up with a solution to solve a maze. The maze was represented by a matrix of 10 rows by 10 columns.¬† A value of 0 in a given element in the matrix meant that that coordinate of the maze was open and a value of 1 represented a closed off, or walled, coordinate. Unfortunately I wasn’t able to come up with a solution on the spot. I am notoriously awful at producing source code for solutions, on the spot in an interview situation. I guess I get too nervous or anxious and just don’t tend to do well in those situations.

In any event the problem was interesting enough to me that once I got home and thought about the problem without being stressed for time, coming up with an eloquent solution on the spot, and with the stress of wanting to get a job offer, I did come up with a solution using recursion. Basically I took the maze data in a matrix concept and extended the maze from a 2D matrix to a 3D matrix with the last matrix dimension used to store whether that coordinate was visited or not during the analysis, a value of 1 or 0. Then once the solution was found marking the maze coordinates that are part of the solution path with a value of 2 in the 3rd dimension.

I also did some research on maze generation algorithms and found the recursive backtracker.

Maze generation algorithm: Recursive backtracker

I combined the maze generation algorithm with my maze solver solution and created a solution using JavaScript to create a maze and provide the solution as well.
See the results below.

Update: I recently had a request to make the source code for this available on GitHub. You can now access the source code via the following link.

MazeCreatorSolver Source Code Via GutHub

Leave a Reply