Tuesday 30 August 2011

A Nerdy Day Out: Maze Algorithms

Every August bank holiday, me and my family take a visit to the Wistow Corn Maze in Leicestershire. It's a huge maze made, humorously, of maize. The design changes every year, and this year (spoiler alert) it was designed like a bee.

Photo used with kind  permission from the owner of the maze

Now it might not surprise you to hear that my family are all big geeks. Neither of my parents did maths A level, but they're both a product of an experimental system called "New Maths" which was where the curriculum suddenly completely changed in the 1970s and 6 year olds were learning set theory. My parents both know some basic group theory, and claim to have been taught Boolean algebra in year seven. My parents seem to know *everything*. They're the cleverest people I know.

One of my brothers did Physics at uni so is a slightly different kind of geek from me. The other one pretends not to be a geek with his cool metal band and all that, but he so is.

What happens when a family of geeks takes a trip to a maze? The first time we went, we took one step inside the maze, and instantly agreed we'd follow the left-hand rule algorithm. We stuck unfalteringly to this path, and looked upon families who were randomly meandering (or worse, reading the map!) with equal parts pity and disdain.

There are 12 boards hidden around the maze with pictures on, and the aim is to find these 12 boards and draw the pictures, then convert the pictures into letters at the end, to spell out a word. Naturally, my family takes this part very seriously.

Let's have some maths, shall we?

Maze Algorithms

The Left (or Right) - Hand Rule (Wall Follower Algorithm)

As long as the walls of the maze are simply connected (every wall is touching the outside wall, so there are no islands), then placing your left (or right) hand on the wall and never letting go as you walk will mean you will always be able to find an exit, or if there isn't one, the entrance. This works because (topology alert) the maze can be deformed (stretched and squished) into a circle, and obviously this rule works on a circle.

This rule fails when there are bits that aren't connected.

Pledge Algorithm

This is the only other algorithm I know (wow, how well-researched is this post!) and it works when the wall-follower algorithm doesn't (on disconnected mazes). This is how you do it: you choose a random direction and walk that way. When you hit an obstacle (a wall), you do the right-hand rule with it and count how many times (or what angle) you turn around it. When you have turned a full 360 degrees (or 0 degrees, or 720, or, ... basically when the angle sum is zero) and you are facing the direction you were when you started (not necessarily the same thing) then you stop doing the right-hand rule and continue to move in the original direction (before you stopped at the obstacle).

So what did my family do this year? Well as usual we started with the left-hand rule. My "cool" borther protested that it would make the maze less fun. But his protests lacked conviction and were easily batted away. He knows deep down that he is one of us. After about twenty minutes, we ended up back at the entrance. Darn. Follow my family's route on the map if you like.

This is the map you're given when you come in. Excuse the crumpledness.

Wistow maze is always a disjoint maze, with an inside track and an outside track. It has two bridges at opposite ends (shown on the map) for you to get from the outside to the inside and vice versa. But as you can see (if you can be bothered), following the left-hand rule means walking past the bridge in the NE but not walking across it. This is why our algorithm failed us. So we had to back track (easily done using the right-hand rule) to the bridge and go across it. Then we resumed the left hand rule until we got to the Mid Point, which has picnic tables and is a good place to stop for a Werther's Original and/or a bag of crisps.

From the Mid Point, there are 6 paths you can take. One is labelled the "quick exit" (the West path) and we came from one of them (the NW path) so we had 4 more to explore. We took the North path because that's what the left-hand rule dictates.

The twelve boards we were trying to find are not usually marked on the map, but this time they were (they're the black crosses, not the numbers), probably to speed people up as it was a busy day. We allowed ourselves to diverge from our algorithm in order to get to a nearby board, but we returned to the original path *immediately*. The left-hand rule is not an algorithm that guarantees to cover every path in the maze. Is there an algorithm that does? Obviously it depends on the maze. In graph theory, I know that you can cover each edge in a graph exactly once as long as the graph has an even number of odd nodes. I'm not sure how to translate that into mazes at the moment. I need to have a think!

School Trip???

Wistow Maze welcomes school trips and even has a lesson pack that you can email to get. However, it's aimed at key stage 1 and 2, and won't have anything to do with maze algorithms. I personally think they are missing a trick there!

I think you could do a really cool school trip with higher level GCSE and A level pupils. When I did D1 there were questions on the exam (MEI) about maze algorithms, so it would be a nice accompaniment to that module. If your school is in Leicestershire or neighbouring counties, definitely consider taking a group there. The maze is open mid July until the end of September, so it would be a good end/start of term treat.

Have you ever been to a maze? Did you geek out about it or did you walk it like a normal person?

Emma x x x

No comments:

Post a Comment