Programming has always been modern computing’s most powerful tool to tackle real life problems and provide a solution. Having given a chance to delve deep and use such an approach to create such a program, I though to create a maze creator and solver program using my knowledge of design and analysis algorithms and data structures. Mazes are fascinating in any problem-solving domain, be it maths or programming or even philosophy. Therefore, creating and solving mazes using coding is very intriguing and I hope this would also motivate my readers to take up similar quests using programming skills.
Here is what I had planned, basically put, generating a maze is like generating sub graphs inside a predetermined connected graph (treating edges as walls and nodes as cells). This is how we would implement the “creation part” of the program, the maze can then be made using many preferred algorithms which in my case is “using backtracker algorithm” using stack data structure and implementing DFS or Depth-First Search technique. Theoretically this should have a time complexity of O(n2).
A few points to remember before we choose an algorithm, a disconnected subgraph wastes region as it does not add to the search region.
And, if the main graph has loops then we use a spanning tree generation method to choose different paths.
On the “solving part” of the program, I chose to use Dijkstra’s Shortest Path Algorithm to implement the solver and implementing a priority queue data structure. In simplest steps, the initial and final nodes of the degenerated graph must be selected and then assume all the nodes to have infinite distance except initial one. One by one considering of the consecutively adjacent node with current node, and then setting the new distance from current to new node, with the condition of only update if the new value is smaller than the older value. The priority queue sets the nodes by order of distance values. Dequeuing and then recursing the process with next node is the approach I have taken.
This is what I came up with to implement the desired approach. I availed this opportunity under my final semester training with much needed guidance from Dr. Tanveer Ahmed. This also would not have been possible without Dr. Deepak Garg’s continuous support. Last but not the least, I would like to convey my heartiest gratitude to Department of Computer, Bennett University for the wonderful chance. Thank you