The story of the Minotaur

Mazes are very ancient and appear many times in history. According to ancient legend, Daedalus constructed the so called "Cretan Labyrinth" in Knossos, to house the legendary Minotaur. The Minotaur was a fearsome creature, half man and half bull killed by Theseus in the famous legend in which he escapes using a ball of string provided by Ariadne.

Although we don't have direct evidence in the form of buried walls for the shape of the Cretan Labyrinth, there is a traditional idea about its shape, and a very nice geometrical construction for drawing one. This gives us our first link between mathematics and mazes. You can draw this on paper, or if you are on a beach it looks very good drawn into the sand with the help of a stick. To draw a traditional Cretan Labyrinth, start with the cross and dots on the right.

The picture below shows you how to complete the Cretan Labyrinth. Notice that the when you connect the lines you alternate left and right round the square. Now you can complete the picture.

Here is a Java Applet showing how to complete the Cretan Labyrinth. Notice how you connect the lines.

Try following the route from the entrance to the centre. This path is surprisingly long and in a full size labyrinth it would have taken some time to get to the centre. However, there is a further surprise in store. Although the path to the centre is very long there is only one way in and one way out! Theseus had to make no difficult decisions at all on his way to kill the Minotaur. Indeed, it was easy with this design to get to the centre and just as easy to get out again. In short there was no need for threads, Ariadne, broken hearts, suicide or any of the other features of the story.

Exactly the same geometric pattern as the Cretan Labyrinth appears in many different cultures and it is quite a common artistic image. Examples of similar mazes have been found scratched into caves in Cornwall (possibly by visiting Phonecian sea farers or by visiting mathematicians in a moment of boredom), on Roman coins and in pictures drawn by native American Indians. The pattern is of interest to mathematicians because it packs a very long path into a small space.

Using other seeds

Using different seeds (or starting shapes) when drawing the maze leads to different labyrinths. An important feature of the Cretan Labyrinth is that there is only one entrance and only one route toward the centre. We can ask the (mathematical) question of whether all seeds lead to Labyrinths with one entrance and route.

Although the Cretan maze is the most common, and probably the oldest, there are lots of others that we can draw. Let's try a different seed such as the one above on the right.

To draw the complete picture remember to alternate drawing the lines from left to right. The resulting maze in this case is shown on the left.

The Rise of the Maze

The term "Labyrinth" is now generally means a construction that leads you from a starting point to a goal by taking you on a tortuous path, but requires no actual decisions. Your whole path is predetermined by the builder of the Labyrinth. Sacred sites were sometimes constructed as labyrinths by people who believed in the action of fate giving you an ultimate destiny which was entirely beyond control. However, following the Christianisation of the Roman Empire, and the belief in the action of free will, a different form of construction came into being. This was the maze.

In a maze intrepid travellers had to make a series of decisions, and their ultimate fates (in particular whether they reached the centre) relied upon the results of those decisions. Mazes were often built into the floors of churches and you were supposed to pray as you found your way towards the centre. The idea of the puzzle maze was developed during the Middle Ages and later into the celebrated hedge maze, often found in the grounds of stately homes.

The modern use of the hedge maze is now purely recreational. The puzzle is usually to find your way to the centre (and out again) starting from the entrance. Many mazes around the world are open to the public and make a great day out. Examples include the Jubilee Maze Centre at Symonds Yat (which has a fine museum of mazes at its centre), and the maze at Longleat, which has bridges and changes its pathways during the day. If you get lost in this maze then clues are available.

Perhaps the most famous public maze in England is the hedge maze at Hampton Court near London, which was constructed in 1690 AD and is still open to the public. If you get the chance, visit the maze at Hampton Court and indeed Hampton Court itself.

We hope that you are convinced that mazes are both fun and important. Now let's think how, as mathematicians, we could try to solve the puzzle of how to get to the centre of a maze (and out again) quickly and reliably.

Mazes and Networks

Next we will explain the link between mazes and networks. In fact we will transform a maze into a network. The result will look very different but the transformation will help us solve the problem of getting to the centre of a maze and then back out again. By doing this we will employ a very useful technique in mathematics:

Transform a hard problem into a simpler one which we can solve more easily.

How to walk round mazes and networks

The point we are trying to reach in a maze is called the centre of the maze. Some mazes can be solved by putting one hand on the hedge and following it round. Unfortunately this doesn't always work. In this section we will show how to transform a maze into a network and give a method for walking round networks which is guaranteed to find the centre. If we've transformed a maze into a network this then solves our problem of finding the way to the centre of the maze. We have chosen the point "M" in our maze. This is where network topology comes in and we will use these ideas to simplify the maze to its essential components.

When you go round a maze it doesn't matter how much you twist and turn, all that does matter are points where you have to make decisions. In a Cretan Labyrinth you don't have to decide anything at all, as once you enter the labyrinth you simply keep walking until you reach the centre. The centre point, the place we are trying to get to, is labeled M. We've put a decision point at the start as you can always decide not to enter the maze.

To simplify the maze we draw a network. In this network we write down all of the decision points as points on a piece of paper. We now draw paths from each of these points to the others, but only if you can go from one to another in the maze without having to make a decision in between. This gives you a network. Here is the maze with all the decision points marked.

Here is the completed network for the maze:

In contrast, here is the network of the Cretan Labyrinth. The only decision points are at the beginning and the end:

Using the network it is MUCH easier to see how to solve the maze. Indeed, we can label the solution just in terms of the decision points that you go through. For the Cretan Labyrinth this gives A -> B. For the more complicated maze one route to the centre is A -> B -> D -> K -> I -> M.

You should be able to find many more routes to the centre using this diagram. How many do you think there are?

The trick of reducing the maze to its bare essentials by finding a diagram which contains all of the information in the maze, is widely used in mathematics. A good example of this is the map of an underground railway system or metro. Often these maps only show the railway lines, stations and interconnections. Distances between stations on the ground do not always correspond to distances on a map. But do travellers on the train care?

Perhaps not, as they often only need to know how to get between stations. In fact, stripping away the unnecessary information might actually help then navigate successfully.

When we think in terms of networks, the problem of solving a maze becomes the following:

Can you find a route in the network which takes you from the beginning to the centre and then back again?

It is worth saying that there are really two different problems here. One is to find the route when you don't have a map of the maze to hand. This is the case in most recreational mazes. The second is to find the route when you do have a map. This case would arise if you were (for example) trying to find your way around a road network or a telephone exchange (or indeed the Underground).

We will consider the case when we don't have a map available.

In a network the decision points are called nodes and the lines connecting nodes are called edges or paths. Given a map of a network, the spaces left between the edges and the space outside are called the faces. If an odd number of paths meet at a node then it is called an odd node and if an even number of paths meet then it is called an even node. A dead end (such as the decision point at C) is an odd node as only one path leads into it.

Networks were first studied by the great Swiss mathematician Leonard Euler. Euler was one of the most productive mathematicians who ever lived and he created a lot of modern mathematics. In 1736 Euler became interested in networks through trying to solve the problem of the Bridges of Königsberg. Königsberg, now called Kaliningrad, is a town in Russia on the Baltic Sea which has the river Pregel running through it with the island of Kneiphof in the middle of the river. The mainland and the island were connected by bridges in the arrangement shown below:

The citizens of Königsberg had noticed that there seemed to be no way of going for a walk in which each bridge was crossed once and once only, but wondered whether they were being stupid and that there might be a route if only they looked hard enough. Euler took up this challenge and started by reducing the problem to a network. In this network, the nodes were the four land masses A, B, C, D and the edges were the bridges. Here is the resulting network:

The problem of the bridges of Königsberg can now be stated as follows:

Can you start from any node and construct a route around the network which will bring you back to the node and go down each path once and only once?

It is possible to ask this question for any network, not just for the one above and Euler came up with a brilliant solution to the general problem. Here it is:

1. If you have any network which has only even nodes then you can start at any node and find a route which returns you to that node which goes down each path once and once only.
2. If the network has exactly two odd nodes then you can construct a route which starts at one odd node and ends up at the other and goes through every path once and once only.
3. If the network has more than two odd nodes then there is no route that goes through every path once and once only.

It is worth pointing out that no network can have only one (or indeed any odd number) of odd nodes. The network for the bridges of Königsberg has four odd nodes so no route is possible which crosses over every bridge once and once only. To make this possible the simplest solution is to demolish the bridge between A and C, then at least you can walk from B to D going over each bridge once and only once (although you can't do this if you want to start and finish in the same place). This is a neat solution mathematically, not a great idea if you happen to live in Königsberg.

We seem to have come a long way from solving a maze, but in fact we have nearly finished. The proof of Euler's theorem actually gives us a way of solving the maze. What we do is use the methods described in the proof to construct a route into the centre of the maze and back out again which goes down each path at most twice. To start we first take the network for the maze. Now, these networks have a collection of odd and even nodes and this makes it awkward to use any of the results of the above theorem. Our first step is to convert the maze into one with only even nodes. This we do by the simple process of drawing each path between two nodes twice. What this means on the ground is that in following our way around the maze we are allowed to take each path twice but no more. Think about this - this is very necessary. If we could only go down each path once then there would be no way out of a dead end! For our example maze this gives the following network:

Doubling up the number of paths in the network corresponding to our maze has converted it into a network with only even nodes. Euler's first result states that in such a network we can construct a path from any node which will return us to that node and which goes down each path once and once only. Now, suppose that we start at the entrance to the maze at point A and find this route. As it goes down every path, sooner or later it will go down a path which leads to the centre of the maze. This is a splendid start. Now continuing along our route we will eventually get back to the start of the maze again. It looks as though we have found a foolproof way of cracking the maze. What is the catch? Well there isn't one really, except that the route we construct may not be optimal (ie. it may be much longer than the shortest route into the centre and back). This makes the method inefficient for solving problems concerned with traffic flow (for which there are much better methods around) but it doesn't matter too much for the networks corresponding to mazes.

As we have not given the proof of Euler's theorem, we can't immediately jump to the solution. Fortunately this has already been done for us and we will describe the method of M. Trèmaux, which is described in the book ``Mathematical Recreations and Essays'' by Rouse Ball. What is nice about the method we are going to describe is that you don't need to use a map of the maze, but you do need to use a packet of peanuts and a bag of crisps.

How to solve a maze using a packet of peanuts and a bag of crisps

You enter the maze, which we will assume has high hedges which you can't see over, and that all paths and nodes (where you make decisions) look very much the same. The peanuts and crisps are used as markers in the maze. Trail the peanuts (here and there) as you go and leave a peanut at all decision points. This will tell you whether you have been to a decision point before or whether you have gone down a path before (without being too ecologically unfriendly). If you go down a path a second time, then trail a path of crisps. If you have a rule that you never go down a path with crisps this will stop you going down that path again. If you reach a decision point which does not have a peanut there we call this a new node. Leave a peanut there, it now becomes an old node. Similarly, a path without peanuts or a path in which you are currently on and dropping peanuts for the first time is a new path. A path with peanuts already on it and on which you are now dropping crisps is called an old path. Here is now how to solve any maze.

1. Start at the entrance and take any path.
2. If at any point you come to a new node then take any new path.
3. If you come to an old node, or the end of a blind alley, and you are on a new path then turn back along this path.
4. If you come to an old node and you are on an old path then take a new path (if such exists) or an old path otherwise.
5. Never go down a path more than twice.

If you follow this procedure then you will eventually reach the centre and then get back out again. This of course only happens if no one eats the peanuts, and here we have to hope for the best! Try it out on the examples in the exercises, for which a pencil mark will substitute for the peanuts. For an example, on the network of our maze the method gives as one possible route, the route:

ABCBDEFEGIMIJIKLKDKIGHGEDBA.

Interestingly enough, if you read the account of Harris' adventures in the Hampton Court maze from the book Three Men in a Boat, you will find that he also used a marker. Instead of a peanut, they used a baby's bun which showed them when they had come back to the same point. Unfortunately as there was only one bun available it didn't help much with solving the maze itself and left the baby hungry. Try this method out and see if you can discover why and how it works.

Other networks

We have seen how to transform a maze into a network. As we mentioned before, you can think of an underground rail system as a network of connected stations. The internet is a network of computers. In fact, there are many other examples of real systems that we can think of as networks.

The aMazing thing about mathematics is its power to Connect them all!

More information on mazes, networks and many other areas of mathematics can be found in our forthcoming book, Mathematics Galore!, Masterclasses, discovery workshops, and team projects in mathematics and its applications by C J Budd and C J Sangwin, to be published soon by OUP.

---

This article is adapted from one originally published on the website of the Newton Institute, as part of the Posters in the London Underground series.

Links

Radio Controlled? by Robert Leese (Plus, issue 8).

Robert Leese explains how the mathematics of colouring graphs (networks) can help avoid interference on your mobile phone.

Call routing in telephone networks by Richard Gibbens and Stephen Turner (Plus, issue 2).

Find out how modern telephone networks use mathematics to make it possible for a person to dial a friend in another country just as easily as if they were in the same street, or to read web pages that are on a computer in another continent.

Theseus and the minotaur

Try your hand at these fantastic web-based maze puzzles.

---

About the authors

Chris Sangwin is a Research Fellow at the School of Mathematics and Statistics, University of Birmingham.

Chris Budd is Professor of Applied Mathematics at the University of Bath, and Professor of Mathematics for the Royal Institution. He is particularly interested in applying mathematics to the real world and promoting the public understanding of mathematics.