Solving mazes
The a-mazing Mihalis Tsoukalos reveals how graph algorithms and backtracking can be used to provide a solution to a maze
The a-mazing Mihalis Tsoukalos reveals how graph algorithms and backtracking can be used to quickly provide a solution to a maze.
This month, we’re going delve into solving maze and dungeon puzzles with the help of graph theory (well, we are all in isolation–ed). The purpose of such puzzles is to determine whether there’s a path that connects two places and find that path, keeping in mind that not all maze puzzles are solvable!
A maze is a path or a collection of paths. When we say that we want to solve a maze, we mean that we should find a way of going from the start cell (entrance), which is predefined, to the end cell (goal), which is also predefined. A similar way of thinking about solving a maze is routing through obstacles of various types from your current place to a given location. A maze might have multiple solutions, too.
To solve a maze, you just have to find a trail between the start and end points of the maze. Note that mazes can be implemented using undirected graphs and that if a maze contains isolated nodes or too many wall cells then it might not be solvable.
The way you represent a maze has nothing to do with the maze itself – it’s just a practical way of working with a maze in your computer programs. The diagram (right) shows a graphical representation of a maze that’s appropriate for humans along with its solution, which is represented by a red line.
A popular way of representing a maze using code is by using an array: a data structure that can be found in almost every programming language. As a result rectangular mazes can be viewed as grids. The biggest disadvantage of arrays is that they can’t be customised, which means that you can either do your job with an array or you can’t – there’s no middle ground. As a result, if the requirements of a problem change, an array might not do the job and you’ll end up doing code changes to support a different and more advanced data structure that’ll be used instead of the array. For the purposes of this tutorial, arrays will do just fine.
Seeing the Matrix
It’s time to expand your mind and realise how a rectangular maze puzzle can be represented in a computer program as a grid. This time we’ll begin with an example: 0 1 1
1 1 1
1 1 0
This output represents an array that represents an undirected graph. The logic behind the array follows two main rules. If node 0 is connected to node 1, then both (0, 1) and (1, 0) places in the array are marked with 1 (or another value that says that they are connected). Otherwise, they’re marked with 0. Last, cells are able to connect left, right, up and down. In the previous example both (0,0) and (2,2) are wall cells – all other cells are connected to each other.
This tutorial will use 0 and 1 for representing walls and valid cells, respectively. Although this has the advantage that we can use boolean values instead of integer values in our maze representations, it’s considered a good practice to only think of 0 as a wall cell and of everything else as a valid cell, which means that we’re going to use integer values for representing our mazes.
The diagram (above) shows a more complex maze with more elements, and its array representation. The upper left cell is accessed as (0,0), the cell on the right of (0,0) is accessed as (0,1), and so on.
Lost in text
To process a maze we first need to know how to read a plain text file that holds a maze – and for this tutorial – using Go. The format of the text file will be similar to the output from the previous section: each line of the plain text file will represent a row in the maze that shows what connects with what in the maze.
The implementation of the loadmaze() Go function that will read that plain text file and put it in a Go slice is presented in the diagram (bottom of page 80). Note that in the Go programming language slices are more popular than arrays due to their flexibility.
Once we know how the maze will be represented we can examine the algorithm that’s going to solve the maze puzzles. Note that maze-solving algorithms operate without the need for user intervention. The only thing required is a representation of the maze in a format that can be understood by the algorithm, a starting point and an end point in the maze. Sometimes we assume that the starting point is the upper left corner of the maze and the finish point is the bottom right corner of the maze. If any of these points is a wall, then we must need another point in its place.
Although there are many algorithms that can help us solve a maze, we’re going to use the Breadth First Search (BFS) algorithm. The BFS algorithm is usually being used as a building block in other algorithms – we do the same in this tutorial. The biggest difference between BFS and DFS algorithms is the way they are “walking” the graph. If you prefer images instead of words, we can say that BFS tries to stay as close as possible to the starting point, whereas the DFS algorithm behaves as if it wants to go as far away from the starting point and as quickly as possible.
We’re going to explain how BFS operates in simple words. The BFS algorithm starts at a given node of a graph and goes to the neighbour nodes (left, right, up and down) first before visiting the neighbour nodes of its neighbour nodes. This goes on until all nodes are visited or we run out of nodes – isolated nodes or graphs that aren’t connected to the current graph, either directly or indirectly, aren’t going to be visited.
In most cases, we use a second array that marks a node after it’s been visited to avoid processing the same node again and avoid generating circles in the graph search process. Finally, most BFS implementations use a queue or something with the same functionality to have the nodes that need to be accessed during the BFS traversal. When this queue is empty, BFS stops.
Go to BFS
Now we can use the BFS algorithm for solving maze puzzles as explained in the previous sections. The name of the Go source file is solvemaze.go and accepts a single command line argument, which is the path of the plain text file with the maze representation. The BFS algorithm is applied to the maze and once the desired end cell is visited, the program stops. The program prints all visited cells even if they aren’t in the path that solves the maze. However, once you have the list of the visited cells, it’s easy to find the solution to the maze.
Both the start and the end cells are chosen randomly – if any of them is a wall cell, the program will fail to solve the maze.
The following shows the output of solvemaze.go:
$ go run solvemaze.go ./maze2.txt
1 0 1 1 1 0
1 1 1 0 1 1
1 0 1 0 0 0
1 1 1 1 1 0
1 0 1 1 1 1
From: 4 5 To: 1 4
-> (4,5) -> (4,4) -> (3,4) -> (3,3) -> (4,3) -> (4,2) -> (3,2) -> (2,2) -> (1,2) -> (0,2) -> (0,3) -> (0,4) -> (1,4) Maze is solvable!
Each cell that is visited is printed on the screen – from the output of the program you can see how you end up going to the desired destination cell. Printing the full path from the begin cell to the destination cell would have made the program more complex, so it’s left as an exercise for the reader.
If the maze isn’t solvable, the last message is going to be Maze is NOT solvable! .
The loadmaze() Go function in solvemaze.go is responsible for reading the text file that contains the representation of the maze – the code was explained in a previous section of this tutorial.
Apart from loadmaze() , the most important part of solvemaze.go contains the following code:
for { t1, t2 := getadj(maze, visited, xx1, yy1) if t1 == -1 || t2 == -1 {
break } else {
visited[t1][t2] = 1 Push(queue, t1, t2) xx1 = t1 yy1 = t2 } }
The previous Go code implements the logic of the BFS algorithm and has to do with the visiting of the adjacent cells of the current cell using the getadj() function, as well as the pushing of new nodes to the queue ready to be examined later on in the process.
Backtrace it
There’s always more than one way to solve a problem. A different approach is using backtracking – for reasons of simplicity the maze definition will be hardcoded in backmaze.go – feel free to change the maze definition. The diagram (above) shows the Go code of backmaze. go. The most important part of backmaze.go is the implementation of the solvemaze() function, which accepts four parameters that are the definition of the start cell and the end cell, respectively.
Executing backmaze.go will generate the following type of output:
$ go run backmaze.go
Maze is solvable!
1 1 1 0
1 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
The first line of the output tells us whether the maze is solvable or not. The remaining output shows the cells that the program has visited in the process.
Pythons in your maze
This section will present a way of solving mazes written in Python 3 that also uses the BFS algorithm. For reasons of simplicity, solvemaze.py won’t read the maze from an external file – the maze definition is hardcoded inside solvemaze.py by adding each node and its connections manually, which is a different and somehow more natural way of defining your maze as a graph. However, the end result is equivalent to the approach that was followed in the Go implementation.
Generally speaking, using an external file for reading your maze is convenient, especially when you want to use that file in other programs. However, the approach found in solvemaze.py is faster because you only define the nodes and the edges that you’re actually going to use. Additionally, adding a new node in solvemaze.py doesn’t require the use of a much bigger array for storing the graph and the equivalent maze.
This output explains how solvemaze.py works:
$ ./solvemaze.py
BFS starting from node 1
1 0 2 3
Note that in solvemaze.py you only specify the start node – the program uses BFS to visit as many nodes as
possible and if your desired node is in that list, then you know that the maze is solvable.
Because the graph that’s used in solvemaze.py is divided into two subgraphs, you can either visit the nodes of one subgraph or the other, depending on the starting node!
The most important part of solvemaze.py contains the following Python code: while queue: s = queue.pop(0) print (s, end = ““) for i in self.graph[s]: if visited[i] == False: queue.append(i) visited[i] = True
So, as long as the queue has nodes in it (the while
loop), the process keeps going and new adjacent nodes are added to the queue using queue.append() . The data type of the structure that’s used for representing the graph is defaultdict, which is a subclass of the builtin dict class.
The figure (above) shows the Python 3 code of solvemaze.py.
Generating mazes
It’s helpful to know that there also exist algorithms for creating mazes. This means that you won’t have to create all your mazes manually. This section will reveal a simple way of generating mazes that uses random numbers. The Go source file is called createmaze.go and accepts two command line arguments, which are the dimensions of the slice that will be used for keeping the generated maze. The output of the program is an ASCII text representation of the maze that you can save and use it later on with solvemaze.go.
The most important part of createmaze.go is the implementation of the newmaze() function, as follows: for i := 0; i < rows; i++ { temp := make([]int, 0) for k := 0; k < cols; k++ { n := rand.intn(3) if n == 0 { temp = append(temp, 0)
} else { temp = append(temp, 1) } }
myslice = append(myslice, temp) }
These two for loops are creating a Go slice that’ll hold the new maze. The value of each cell is randomly generated using the rand.intn() function. If the output of rand.intn(3) is 0 , then the cell will be a wall; otherwise, it’ll be a valid cell. Note that the output of rand.intn(3) can be 0 , 1 or 2 , which means that the probability of having a wall cell is smaller than the probability of having a valid cell. Although the Go code of createmaze.go isn’t very sophisticated, it does the job pretty well. The final diagram (below) shows the output from various executions of createmaze.go.
We’re sure you’ll agree that solving practical problems is a satisfying way of experimenting and playing with programming, learning more about computer algorithms and trying new things!
Best Chromebook 2020
Looking for a low-cost, easy-to-use laptop? We test the latest shiny Google-based, Linux-powered systems.
Inside of RISC-V
Are we going to be running open-source hardware anytime soon? We delve into RISC-V and see where it’s going.
Modelling for fun!
Open-source software loves science. We start looking at modelling and simulation tools for fun and science!
Build a router
Ever wondered how a router works? Probably not, but you’re going to find out as we build our own with Linux!
Contents of future issues subject to change – let’s see if we can mange another two months…