Escape From a Maze ...

"We'll just go in here, so that you can say you've been, but it's very simple. It's absurd to call it a maze. You keep on taking the first turning to the right. We'll just walk round for ten minutes, and then go and get some lunch."

THREE MEN IN A BOAT (To Say Nothing of the Dog) by JEROME K. JEROME

Harris hero from the famous story by J.K. Jerome boasted a bit. When he was leading a group of visitors through the Hampton Court maze he wandered there practically for a day till the watchman helped them to get out (meanwhile this watchman used a stepladder to climb on the maze walls).

In general we all know a lot of well-known maze – a building with a rather complicated plan. Our task is to find escape from a flat maze or to set that it has no it.

We need a bit of logic and a few of MS Excel VBA code.

Download VBA project (test maze)

Download VBA project (Hampton Court maze)

Perhaps we are in a start position (point S) of a maze (Fig. 1) and we decided to select direction according to following scheme (Fig. 2): downwards - if possible (direction 1), otherwise rightwards - if possible (direction 2), otherwise leftwards - if possible (direction 3), otherwise upwards - if possible (direction 4). So, if your current position (point S) has no walls around the next motion will be downwards. Opposite situation if all the directions are closed by walls - you are in impasse.

We see that motion direction depends on walls. If we are in a start point having walls on the left side and at the bottom (Fig. 1) - the next motion will be rightwards (according to priority levels described on a previous step). Let's look at similar situation (Fig. 2). We have walls on the left and on the bottom but the current position is not start point - we've come here from the right side. The logic says that instead of two opened ways (rightwards and upwards) we have only a one - upwards (rightwards leads to a retreat - it's a cowardice!).

Such a simple logic gives us ability to find escape from a trivial maze which has no alternative ways (Fig. 1). But what we need to do if the choice of way is not so simple? To make so change a start position in a same maze (Fig. 2). We have two possible ways - leftwards and upwards. Which one to choose? Won't it lead to a dead end?

According to priority levels we need to go leftwards and we will come to impasse (Fig. 1) and need to go back. It's time to remember about Harris to prevent multiple visiting of dead ends. We can manage it by putting the wall before the entrance into the dead end (Fig. 2). Next time when we reach this place we couldn't enter impasse. But.. may be we will also stay in an impasse. May be BUT this impasse will be a step close to start point. And we can exclude this dead end by the same way as previous one - with additional wall (Fig. 3). So, we can get a trivial situation in a start point and be able to find escape (Fig. 4). Certainly, using stepladder the right way could be find more quickly but we can't see the whole plan of maze staying inside of it.

Another ambiguous situation - rooms in a maze. We can go around the room without escape (Fig. 1). It is really so, we go downwards from a start point then move counterclockwise (according to priority levels) and reach ... an initial point without any impasse. But impasse is in a crossing of a current pathway in any place (not only in a previous point). So in a cross point we can put additional wall to prevent circling motion (Fig. 2). Next time during the next cycle we will reach a simple impasse and could manage situation as described in a previous step (Fig. 3, 4).

Summarizing the whole above we can make a general logic scheme to find escape from the plane maze.

At initial point we start to record pathway and try to move to a next point according to priority levels (bottomwards, rightwards, leftwards, upwards). If we have a wall on the trajectory we select the next direction. If not so we control the intersection with a current pathway. If the intersection is found we put the wall at this place and return to a start point for a new pathway. Otherwise if intersection is not found we occupy a new point and add it to a current pathway. According to a last variant we also control current location (perhaps we are out of maze limits and find escape!) and continue motion according to priority levels.

This project is realized in MS Excel. User draws a maze and sets initial point on sheet "Task". All the walls are forming by the group of standard tools "MS Excel > Home > Borders". Initial point is setting by cell color using "MS Excel > Home > Fill color (Yellow)". Sheet "Task" also contains a "Start" button for appropriate code running. The escape pathway will be displayed on a sheet "Solving". Programming code according to a logic scheme (see previous step) we put in a Visual Basic for Application (VBA) module ("MS Excel > Developer (ribbon tab) > Visual Basic > Insert > Module"). Programming module contains a start procedure "main()". Program gets the maze structure by analyzing all the cell borders on a "Task" worksheet. We put a "Start" button on the "Task" worksheet by the following tool: "MS Excel > Developer (ribbon tab) > Controls > Insert > Button". The "main()" procedure is connecting to a "Start" button by the context command "Assign Macro". We can use context command "Protect Sheet/Unprotect Sheet" for all worksheets to prevent any accidental user actions.

Download VBA project (test maze)

Download VBA project (Hampton Court maze)

The project is ready. Let's see how to use it for specific maze. First of all we need to give permission to run VBA-code by the command "Enable Content" in a pop-up window during the first Excel-file running. Then go to the "Task" worksheet and draw all necessary walls around appropriate cells according to a maze plan ("MS Excel > Home > Borders"). Then set initial position in your maze by shading a single cell ("MS Excel > Home > Fill color (Yellow)"). Finally press "Start" button to run the main procedure for escape searching. You can control current position on each step ("Solving" worksheet), continue or stop the program. If you want to make any changes in a maze plan or to set another start point go to a "Task" worksheet and work with borders and filling for appropriate cells.

Download VBA project (test maze)

Download VBA project (Hampton Court maze)

It's time to return to Hampton Court and find escape from its famous maze using our logic scheme. We start from the central room and make a few failure hikes leading us to impasses which we mark with additional walls (dashed lines on a scheme). Finally we get a trivial structure and go out without any difficulties.

p.s. You can see that the way we get is not the shortest (especially in a top right side). It depends on priority levels for motion direction. But we've found guaranteed escape! That's primary!

Download VBA project (test maze)

Download VBA project (Hampton Court maze)