Maze-Solving Algorithms and Practical Applications in the Physical World — Keith Burroughs and Vanessa Klotzman

The Origin of Maze-Solving

The term “maze” dates back to the thirteenth century, and “labyrinth” dates back to the fourteenth century. The concept of mazes dates back to the era of the Greek mythological hero Theseus — an ancient hero who successfully traveled through the Labyrinth of Crete and slayed the Minotaur.

However, within a more modern context, mazes scarcely relate to the slaying of mythological creatures. Instead, mazes most often describe a gridded puzzle consisting of twists and turns that eventually lead to an exit. And just as the ancient hero Theseus traveled through a Labyrinth to slay the Minotaur, the modern human solves mazes not just to accomplish the task of solving a maze but also for the much more generalized purpose of solving related problems most efficiently and feasibly possible.

Introduction

Mazes are an integral part of our reality. Although mazes within the physical world seldom follow the typical description of a maze (a gridded black and white puzzle), the general idea and concept of mazes commonly appear. Throughout our everyday lives, we often encounter situations in which one must deduce the fastest and most efficient route to a given destination. In a grocery store, for example, to find the milk aisle, one can simply look at every single aisle until the milk is found. However, this is not the most efficient method. If one utilizes the signs within the store or previously stored memories of where different paths within the store lead, finding the milk can become a much more efficient process. In a sense, we must use this same process when solving actual mazes. The technique/algorithm that one chooses to solve a maze can affect the efficiency of the process.

Efficiency

The efficiency of a computational algorithm is the number of computational resources used by the said algorithm and the time it takes to produce the desired result. One can improve the efficiency of an algorithm by removing nested for-loops, caching immediate or previous results, and reducing the algorithm’s time complexity.

Time Complexity

Time complexity measures the time to execute each code statement in an algorithm. When analyzing a piece of code for its time complexity, Big O notation is used. Time complexity is given by time as a function of the length of the input. “There exists a relation between the input data size (n) and the number of operations performed (N) concerning time.”

Constant time — O(1)

Linear time — O(n)

Logarithmic time — O(log(n))

Quadratic time — O(n²)

Cubic time — O(n³)

Typically, one aims to program an algorithm with a constant time complexity: O(1). This indicates that the algorithm’s runtime is the same regardless of the size of the dataset or the number of inputs. A logarithmic time complexity–O(log(n)) — indicates that as the input size grows, the number of operations grows logarithmically or fairly slowly. On the other hand, an algorithm containing cubic time complexity–O(n³) — has a runtime proportional to the cube of the size of the dataset. As a result, a conscientious programmer will attempt to minimize the time complexity of his or her algorithms and methods to reduce runtime and redundancy.

The graph below exhibits the varying time complexities:

Code Length

One must not confuse time complexity with the number of lines of code. The number of lines of code is extremely easy to measure but almost impossible to interpret. This is primarily because one algorithm can have a lower time complexity with greater lines of code than another with fewer lines. Essentially, time complexity should not be confused with and mistaken as directly correlated to the number of lines of code.

For example, given the programming problem: given an array of integer nums and an integer target, return the indices of two numbers that add up to the target, a variety of time complexities can be achieved.

With time complexity O(n²):

With time complexity O(n):

Both of these approaches return the same output. However, one can see that despite having an extra line of code, the second example accomplishes the task with O(n) time complexity rather than O(n²), which is much faster in the vast majority of cases.

Despite this, algorithms with fewer lines of code are often less complex and easier to use and understand. Also, we will be looking only at different algorithmic approaches to the same problem, so one would expect each of the maze-solving algorithms to be similar in length. Therefore, the length of a maze-solving algorithm’s code should still be considered a criterion when comparing and contrasting the identified algorithms.

Maze-Solving Algorithms and Criteria

Maze-solving algorithms are an automated method for solving mazes. Given a maze, many different algorithms could be used to solve it. This paper will discuss and analyze the following well-known maze-solving algorithms:

• Bruteforce
• Trémaux’s Algorithm
• Random Mouse Algorithm
• Wall-Follower Method
• Dead-End Filling

Bruteforce Algorithm

A brute force maze-solving algorithm explores every path and avenue until it finds the correct one. Bruteforce maze-solving algorithms generally consist of checking every possible path through a maze and restarting when a path generated is unsuccessful. This approach often leads to a high time complexity and an inefficient program, though, as redundant code is typically run. As a result, the time complexity of an algorithm of this type is often O(n!). On the other hand, a brute-force algorithm is often easy to program, as it does not require marking junctions (which is required for Trémaux’s algorithm) and usually just involves repeating loop statements.

Trémaux’s Algorithm

Invented by Charles Pierre Trémaux, Trémaux’s Algorithm is a method of maze-solving that draws lines and dots along the maze to mark its path. There are a set of rules one must follow when performing this algorithm:

• When a junction is met in the path, it must be marked (as seen below) at both ends.
• Do not enter a path if it has two marks.
• If a junction has no marks, choose an unmarked path to follow and mark said junction.
• If the path you came in on only has one mark, turn around and return along that path and mark it again.
• If not, choose one of the remaining paths with the fewest marks, follow it, and mark it.

This algorithm is limited by its requirement that each junction is marked. However, this program is more efficient and has a lower time complexity than brute force or random mouse algorithms–it is simply more difficult to program and implement. Eventually, this algorithm would be generalized and called “depth-first search.”

Trémaux’s Algorithm Code Example

*Example of Trémaux’s Algorithm

Random Mouse Algorithm

A random mouse algorithm is a very unintelligent and unsophisticated algorithm. Often, it is implemented as a fast and easy algorithm to solve a maze. Within this algorithm, once the algorithm starts moving through the maze and reaches a junction, the “random-mouse” chooses a random direction to turn and continue:

• Proceed following the current passage until a junction is reached
• Then make a random decision about the next direction to follow.

This algorithm leaves one blind when attempting to solve a maze and normally takes an extremely long time to complete. Despite this, this algorithm will always lead to a solution, as the algorithm/mouse will eventually find the correct path through the maze. The randomness and inefficiency associated with random mouse algorithms almost always cause high time complexity. However, if the random mouse algorithm, by chance, finds the correct path on its first attempt/loop, the algorithm has the potential for an O(1) time complexity. More likely than not though, this algorithm will cause code to be run that has already been run and found to be unsuccessful.

Random Mouse Code Example

Wall-Follower Method

One of the most commonly-known maze-solving methods is the wall-follower method. Commonly known as the “left/right-hand rule,” this method relies on the outer-connectedness of a maze–all of the walls are connected to the outer boundary of the maze. If this is true, then one can find always find the end of a maze if one continuously follows either the left or right side throughout the entirety of the maze (one must begin the method at the entrance). However, in cases where each boundary is not connected to its outer boundaries, this method will not always be successful. This method/algorithm is useful if one knows that the maze is simply connected. The algorithm is highly efficient, as it does not require marking junctions or restarting based on unsuccessful attempts; the algorithm simply follows the left or right side of the maze. Programming the wall-follower method would likely be relatively simple and would not require many lines of code. As a result, the time complexity will undoubtedly be better than that of a brute force or random-mouse algorithm. Still, the sheer inability of this method to solve a lot of mazes sets it back.

Wall Follower Code Example

Dead-End Filling Algorithm

Dead-end filling algorithms take a different approach to solving mazes. Rather than attempting to go through the maze quickly and efficiently, dead-end filling algorithms work to fill all of the dead-ends, leaving only the correct path(s) remaining. The rules of this algorithm are:

• Find all dead-ends within the maze
• Fill each path from each dead-end
• The last path (remaining) is the correct path

The benefits to using a dead-end filling algorithm are that they can find multiple solutions to a maze if they exist, and the algorithm should work for any maze. Despite this, the algorithm is very inefficient–especially if the maze is large. The algorithm has to check every dead end and then fill/mark each dead end. This is time-consuming and leads me to believe that the time complexity of at least O(n²) is required for any reasonable program with this algorithm. A video of the algorithm in action can be viewed below:

Example of Dead-End Filling

Robotic Application

By implementing the mentioned maze-solving algorithms, I decided to task a robot with solving mazes. With the use of a Raspberri Pi Pico and MicroPython, this was made possible. The robot design used for this project is the Yahboom Raspberry Pi Pico Robot:

Some knowledge of Python is recommended for this project. The Yahboom Pico Robot comes with a Raspberry Pi Pico, but many additional sensors can be purchased in the Pico Sensor Kit. The sensors in the Sensor Kit will be unused for this project, so purchasing only the Pico Robot is sufficient.

Using the manual, the Yahboom Robot can be assembled with its parts along with the Raspberry Pi Pico and then configured to run MicroPython. The wheels must be aligned consistently to avoid imperfect movements when running code. MicroPython is a programming language written in C that is optimized to be run on microcontrollers and control hardware. This allows one to manage the hardware connected to the Raspberry Pi Pico without dealing with the difficulties associated with a lower-level language, such as C or C++.

Once everything is installed, we can test different algorithms with a real-life maze created from colored sheets of paper and styrofoam.

Installing Software

The Raspberry Pi Pico can be programmed by connecting it to a computer via a micro-USB cable. We must first install MicroPython to begin programming on the device. The latest MicroPython UF2 files can be found in Raspberri Pi’s MicroPython documentation.

*Note that BOOTSEL must be held on the Pico for the library to pop up in Windows/Mac

Additionally, the Thonny Python and MicroPython compiler must be installed. Thonny will allow us to communicate with the Raspberry Pi Pico and the devices connected to its pins. If MicroPython is installed on the Raspberry Pi Pico, its option should be available in Thonny’s interpreter settings:

After successfully connecting to Thonny, one can begin accessing and programming the Raspberry Pi Pico. The Python library that the Pico Robot manufacturers recommend is “Pico_Car.” This can be downloaded here under “library” and subsequently installed onto the Raspberry Pi Pico through Thonny. Also, the manufacturers mentioned using an IOS app, YahboomRobot, to control the robot. To use the app, “Bluetooth Control.py” must be saved and run on the Raspberry Pi Pico. The file can be downloaded here under the directory: “3. Robotics Course.” If all is run and installed correctly, the app should look like this and be able to control the robot in live time:

To control the Raspberry Pi Pico without being forced to use this restrictive IOS app that does not allow us to run code, we need to implement Bluetooth control ourselves. To do this, we must use an Android app: Serial Bluetooth Terminal. This app allows us to connect to the robot’s Bluetooth module on the Raspberry Pi Pico. Once the Pico receives an input, certain code can be run or stopped. It allows us to start and stop programs wirelessly and without having to connect the Pico to a computer every time a piece of code is run.

The M1 and M2 values must be set to hex 31 and 32, respectively to start and stop the maze.

We will now implement the previously discussed algorithms onto the robot. To start, we will modify the brute force code to match the hardware of the Raspberry Pi Pico. In this first case, we will not worry about using a color sensor, as we are just using an already initialized 2D array as our maze. Using the steps that the program returns to solve the maze (ex: left, right, up, or down), we can make the robot move in those directions. The modified code can be viewed here.

Using the implemented brute force maze-solving algorithm (linked above), a pre-configured maze can be solved by the robot. When the dimensions and size of the maze are altered within and are entered within the code’s 2D array labeled maze, the algorithm can be fit to solve any maze. The walls/boundaries are represented as 1s within the array, while the open space for the robot to travel through is represented as 0:

If it were a typical maze it would look like the following (start from the top left index):

Since the Raspberry Pi Pico and its code are now set up, we can recreate the maze in real life for our robot to solve. Note that, for bruteforcesolverRPIPICO.py, variables speed and runtime may need to be adjusted according to the scale and dimensions of one’s maze. The default is:

runtime = 2 #seconds

rotate_pause = 2 #seconds

speed = 175

The robot can now successfully solve the maze above. However, we must recreate the maze in real life. In this case, styrofoam blocks are used to construct the maze’s walls.

An example of the robot going through the maze can be found in the youtube video. https://youtu.be/fvIggWbnA5U

The above section summarized:

1. Assemble robot
2. Install required software (MicroPython and Thonny)
3. Ensure MicroPython is installed on the Raspberry Pi
4. Configure and run the script or use the pre-configured iOS app
5. Construct a maze and run the script with Thonny with a robot connected to the PC

Real-Life Scenarios

The ability to solve mazes with a robot is exciting, but it may be difficult for one to realize the alternative applications of these algorithms to real life. Maze-solving is a simplified version of navigation, so the implementation of algorithms for navigation requires the same concepts as maze-solving.

In this Google Maps navigation example from Mcdonald’s to Walgreens, Google uses an algorithm to determine the fastest route through the roads. The roads, in this case, are equivalent to the open areas within a maze (the indexes with values 0 in the maze array). Google also attempts to find the fastest route–typically the route with the least turns and overall distance.

Additionally, in 2022 Uber experimented with delivering food with robots; using pathfinding and GPS technology, a colorful cooler on wheels will present customers with their food.

The point is that similar processes and algorithms used for maze-solving are used in interesting and useful real-world applications. One should not view the concept of maze-solving as an isolated field with few valuable real-life applications.

Conclusion

Maze-solving robots are a concept many might consider uninteresting or of little value to society. However, this project was accomplished with only about a hundred lines of code. Also, if the brute force maze-solving algorithm had been configured with a light or color sensor, the robot could have solved any maze without requiring its dimensions and wall placements. If I had an extended timeframe, I would certainly incorporate this idea within the project. During this investigation, I discovered the world of algorithms, time complexity, and efficiency in programming. This project allowed me to discover, at my own pace, a previously unexplored area of study and its relation to GPS systems and fascinating ideas/start-ups. In a world that may soon be ruled by AI and complex robots, I feel somewhat fulfilled knowing I was provided with crucial experience experimenting with the basics of robotics and algorithms.

Glossary

Bruteforce — enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.

Trémaux’s Algorithm — a maze-solving method that requires drawing lines on the floor to mark a path–guaranteed to work for all mazes that have well-defined passages.

Random Mouse Algorithm — a maze-solving method that randomly chooses which path to follow at a junction until it is solved.

Wall-Follower Method — a maze-solving method that involves following a chosen side of the maze it is solved–only works for simply-connected mazes.

Dead-End Filling — a maze-solving method that solves a maze by filling each all of its deadends, leaving only the correct path.

Efficiency — the number of computational resources used by an algorithm and the time taken by it to produce a desired result.

Time Complexity — a measure of the time taken to execute each statement of code in an algorithm (O(n)).

Code Length — the number of lines of code in a program.

Bibliography

“A Brief History of Mazes: National Building Museum.” National Building Museum |, 17 Mar. 2017, https://www.nbm.org/brief-history-mazes/.

“Simple Maze Solution (Brute Force, Depth First), Python.” Gist, https://gist.github.com/Chuwiey/1e34ed9e65d41b735d8c.

mikeburnfire. “Trémaux’s Algorithm.” YouTube, YouTube, 10 July 2020, https://www.youtube.com/watch?v=RjWSlz-aEr8.

Maze Solution #3 — Tremaux’s Algorithm: V19FA Intro to Computer Science (CIS-1100-VU01). https://vsc.instructure.com/courses/6476/modules/items/713459.

Anubabajide. “Anubabajide/Maze-Runner: Autonomous Maze Navigation Robot Using a Raspberry Pi.” GitHub, https://github.com/anubabajide/Maze-Runner.

Genetic Algorithm for Maze Solving Bot — GitHub Pages. https://shepai.github.io/downloads/GeneticAlgorithmVsBrute_by_Dexter_Shepherd.pdf.

“Trémaux’s Algorithm” Sample Maze Solved [1] — Researchgate. https://www.researchgate.net/figure/Tremauxs-algorithm-sample-maze-solved-1_fig8_315969093.

Cedars-Sinai Medical Center. “With Smiles and Beeps.” Robots Help Nurses Get the Job Done, Cedars-Sinai Medical Center, 26 Nov. 2021, https://www.cedars-sinai.org/newsroom/robots-help-nurses-get-the-job-donewith-smiles-and-beeps/.

“Raspberry Pi Documentation.” MicroPython, https://www.raspberrypi.com/documentation/microcontrollers/micropython.html.

McFarland, Matt. “Uber to Test Delivering Food with Robots.” CNN, Cable News Network, 13 May 2022, https://www.cnn.com/2022/05/13/cars/uber-robot-delivery-la

Jarednielsen. “Big O Factorial Time Complexity.” Jarednielsencom RSS, https://jarednielsen.com/big-o-factorial-time-complexity/.