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.
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.