300000
English  Français  فارسی
When working through the Food for Thought section, new buttons are available above. These buttons are different tools and features that were created for the use of enhancing the learning experience when working with our mazes. They will not be available during a contest, as they are just for learning purposes. A short explanation of the purpose of each button is written below. During a contest, only the buttons 'Clear', 'Zoom In' and 'Zoom Out' are available.
In formal mathematics, all content is grouped into definitions, hypothesis, lemma, theorems, proofs and conclusions. The role of definitions is played here by the following:
Mazes shown on this web page have two properties which make them somehow special.
As mentioned above, all walls that are connected to each other form a tree.
Each one of the two ☺ squares in the puzzle is surrounded on 3 sides by either the border or by walls belonging to only one tree.
To visualize a tree one can click 'Enable Wall Colouring' and then click a wall either with the left or right mouse button and with or without Shift and thus colour the tree either in red, blue, orange or green. The trees surrounding the two ☺ may either be the same tree or two different trees. Try to find a maze where the two ☺ lie in the same tree and a maze where the ☺ are in different trees.
We will first discuss the case where the two ☺ squares are surrounded by two different trees. The rare and simpler case that the two ☺ are surrounded by the same tree will become clear in the process.
To see the power of the following algorithms, it is useful now to maximize the maze size and click 'New Maze'.
After clicking 'Step 1' if you see only one blue tree then click 'New Maze' and again 'Step 1'. Repeat that until you see a red and a blue tree. After clicking 'Step 2', the two roots are shown.
The two roots separate the border into two sections, one section from the red root clockwise to the blue root, and one from the blue root clockwise to the red one. If one clicks 'Step 3', then the border and all trees with their root in the first section are coloured orange, and the border and all trees with their root in the second section are coloured green.
If a path should link both ☺ then that path should first get from ☺ out of its cave to the surface of its tree. This gives two more special squares on the maze.
Click a number of times 'New Maze' followed each by clicking 'Step 1,2,3' and get a feeling for the possible locations of the red and blue trees and the orange and green forests. We suggest you keep doing it until you come to the situation that there is only one green forest and only one blue tree which houses both ☺ squares. After having seen many mazes with their red and blue trees and orange and green forests coloured, can one group them into few cases?
After having discovered rules that describe the shortest path qualitatively we now need to prove these rules.
 Enable Filling  When this is enabled, a rightmouseclick marks squares in red which can be used conveniently to mark deadend paths for yourself. Red squares are not counted as part of a solution.
 Enable Wall Colouring  When enabled, one can click on a wall to colour its whole tree in one of four different colours, through left or right mouse click, with or without pressing the 'Shift' key at the same time.
 Step 1  When clicked repeatedly, the solution path is determined step by step by following an algorithm described below.

The purpose of this Food for Thought is to discover in which sense are our maze problems special, and which structures our mazes have as a consequence. We will find that:
 Although a maze looks random and chaotic, there are 6 distinctive points in it.
 These 6 points are helpful to find the solution path.
In formal mathematics, all content is grouped into definitions, hypothesis, lemma, theorems, proofs and conclusions. The role of definitions is played here by the following:

On this web page we will use the following technical terms:
 Maze  the whole square or rectangle, including everything inside.
 Border  the surrounding line of the whole maze.
 Wall  a short vertical or horizontal line within a maze that cannot be crossed.
 Square  a small area in a maze that is not a wall and not a border, on a NxM maze there are NxM squares.
 Tree  a set of walls that are connected to each other within the maze, not through the border of the maze.
 Cave  all squares connected to each other that are surrounded only by the walls of one tree.
 Root  the point where a tree connects to the border.
 Gate  a side of a square that is not a wall and does not belong to the border.
 Path  sequence of squares in the maze that are all connected without crossing a wall.
 Solution  the shortest path that connects the two originally identified ☺ squares on the maze.
 Forest  a connected part of the border together with all trees that are connected with this part of the border.
 Surface  for a given tree/forest, a single path which consists of all the squares that have among their 4 sides and 4 corners at least one (wall of that tree)/(wall or border belonging to that forest) and have one (wall NOT belonging to that tree)/(wall or border NOT belonging to that forest).
Mazes shown on this web page have two properties which make them somehow special.

Hint 1: Start with a small maze and try to find two squares in the maze that can not be linked by a path. If you have an opinion about that possibility, try again with a different maze to confirm it.
 First property: Each square can be linked through a path to each other square. In other words, no part of the maze is cut off from the rest of the maze.
Hint 2: Start again with a small maze. This time try to find two squares in the maze that can be linked by two different paths. If you have an opinion about that possibility, try again with a different maze to confirm it.
 Second property: There are no paths with a loop, i.e. two paths linking the same two squares differ only by extra deadend paths which are traversed an even number of times, equally often in each of the two directions.
What is not easily seen is that the two squares ☺ are selected so that the length of their connecting path is either the longest possible or close to the longest possible path.
As mentioned above, all walls that are connected to each other form a tree.

Each tree has exactly one root, i.e. one point where it touches the border.
 Because then the surface of the tree would form a loop which does not exist for our mazes.
 Because then one part of the maze would be cut off from the rest of the maze. The cut off part would lie between the two roots and be surrounded by the border and the tree.
 Because each tree has exactly one root, we can find the number of trees by counting all points along the border where a wall intersects the border.
Each one of the two ☺ squares in the puzzle is surrounded on 3 sides by either the border or by walls belonging to only one tree.
 The reason is that the two ☺ are selected as those squares with the longest possible distance, i.e. the longest path linking them. If one of the ☺ would have two of its 4 sides open then it could be moved to enlarge the distance to the other ☺.
To visualize a tree one can click 'Enable Wall Colouring' and then click a wall either with the left or right mouse button and with or without Shift and thus colour the tree either in red, blue, orange or green. The trees surrounding the two ☺ may either be the same tree or two different trees. Try to find a maze where the two ☺ lie in the same tree and a maze where the ☺ are in different trees.
We will first discuss the case where the two ☺ squares are surrounded by two different trees. The rare and simpler case that the two ☺ are surrounded by the same tree will become clear in the process.
To see the power of the following algorithms, it is useful now to maximize the maze size and click 'New Maze'.
After clicking 'Step 1' if you see only one blue tree then click 'New Maze' and again 'Step 1'. Repeat that until you see a red and a blue tree. After clicking 'Step 2', the two roots are shown.
The two roots separate the border into two sections, one section from the red root clockwise to the blue root, and one from the blue root clockwise to the red one. If one clicks 'Step 3', then the border and all trees with their root in the first section are coloured orange, and the border and all trees with their root in the second section are coloured green.

Now all trees are coloured.
 We already showed that each tree has one root to the border because otherwise its surface would be a loopy path. So if we coloured all trees with a root then we coloured all trees.

Hint: Click 'Step 4'.
 The two squares are the only ones that have trees or the border of 3 different colours as neighbours.
If a path should link both ☺ then that path should first get from ☺ out of its cave to the surface of its tree. This gives two more special squares on the maze.
 If ☺'s are not already located at the surface of their tree then clicking 'Step 5' and 'Step 6' shows the path out of the ☺'s caves to the surface of their respective tree with the two special points at the end.
Click a number of times 'New Maze' followed each by clicking 'Step 1,2,3' and get a feeling for the possible locations of the red and blue trees and the orange and green forests. We suggest you keep doing it until you come to the situation that there is only one green forest and only one blue tree which houses both ☺ squares. After having seen many mazes with their red and blue trees and orange and green forests coloured, can one group them into few cases?

There can only be four situations. How can one find the complete solution path for each case?

Then the orange and green forests touch, i.e. they share surface squares. Squares surrounded by trees of 3 different colours (3colour squares) are marked with a red square in the maze and are circled purple in the schematic diagram below.
Click again 'New Maze' and when such a maze arises then click 'Step 1,2,...'.
What is the relation between the solution path and the differently coloured trees, forests and the 3colour squares?
The solution path can be seen as a sequence of 5 paths:
 From ☺ in the red/blue tree to its respective surface.
 When on the tree surface an orange/green wall is encountered then on the surface of a red tree turn right/left and on the surface of a blue tree turn left/right, followed by a path to the next 3colour square.
 A path linking the two 3colour squares.
Try to identify these 5 paths as part of the solution in the maze on your screen.

The solution path can be seen as a sequence of 5 paths:

Then the orange and green forests do not touch, i.e. do not share their surface squares. Also in this case there are two 3colour squares, which are circled purple in the schematic diagram below.
Click again 'New Maze' and 'Step 1' until such a maze arises. Then click 'Step 2,...'.
What is the relation between the solution path and the differently coloured trees, forests and the special squares?
The solution path can be seen as a sequence of 3, 4 or 5 paths:
 From ☺ in the red/blue tree to its respective surface (same as in the previous case).
 Same turning rules and same proceeding to 3colour squares as in previous case, except when leaving the red/blue tree and the blue/red tree is encountered then wait.
 If by now one and the same 3colour square is reached twice then the solution path is complete.
Try to identify these paths as part of the solution in the maze on your screen.
If only one triple square is reached, then continue on the redblue surface to the other exit square.
If no triple square is reached, then search on the redblue surface first in one direction until you reach either the other exit point, or a 3colour square. If the other exit point is reached, then the path is complete. If a 3colour square is reached, then search in the other direction until the other exit square is reached to complete the solution.

The solution path can be seen as a sequence of 3, 4 or 5 paths:
3. There is one single square which is in the surface of the red and blue tree and the orange and green forest.
This situation is very rare but principally possible.
In this case again paths associated to steps 1. and 2. of case 1 apply.

This situation does occur but not very often.
The two ☺ squares are either linked by a path lying completely within the blue tree, or by 2 paths leading from each of the ☺ squares to the surface of the blue tree and one path on the surface of the blue tree which links both paths.

If a ☺ square is right at the border, or is enclosed by 2 trees then it is already on the surface of its tree.
All earlier instructions apply except that there is no path needed from ☺ to the surface of its tree.

Then the orange and green forests touch, i.e. they share surface squares. Squares surrounded by trees of 3 different colours (3colour squares) are marked with a red square in the maze and are circled purple in the schematic diagram below.

To have fun and test your understanding:

 Change the maze Width to 50 and Height to 50.
 Change 'Gate Density' to 0.
 Repeat clicking 'New Maze' and 'Step 1..9', but before clicking the next step, imagine which special points and paths will be coloured in the next step.

 Change the maze Width to 50 and Height to 50.
After having discovered rules that describe the shortest path qualitatively we now need to prove these rules.

What needs to be answered is the following question:
Why does, apart from case 4 above, the path always lead from the ☺ squares to the surface of their respective tree, and then stay on the shared surface of trees or forests?
Let us look at a tree and its surface. Click 'New Maze' and 'Enable Wall Colouring' and then click a wall somewhere in the middle of the maze (to get a big tree). Next, mark with the left mouse button the surface of that tree as a purple path. If you follow that surface you will see gates that lead into the coloured tree.
Pick one such gate, click 'Enable Filling' and colour (by using the right mouse click to have a different colour) all squares within that tree that can be reached through this gate.

It turns out that one is stuck in this tree. That means one can leave that tree only through the same gate through which one entered the tree. We call this a cave.

If one could enter a tree through one gate on its surface, and leave this tree through another gate on its surface, then that would create a closed loop. This loop would consist of a path linking both gates within the tree, and also along the surface of the tree.
One reason that this is not possible is that our mazes do not have loops. But even in more general mazes with loops this could not occur. Because such a loop would surround walls that are disconnected from the walls outside of the loop, so what the loop surrounds could not be a part of an outside tree because a tree contains walls that are all connected with each other.
Therefore one can always leave a tree only through the same gate through which one entered it.
The same reasoning is true not only for trees but also for forests.
This proves that the shortest path between two squares lying on the shared surface of trees or forests is located as a whole on the shared surface of trees and forests. Any detour entering a tree or forest would only increase the length of the path.

If one could enter a tree through one gate on its surface, and leave this tree through another gate on its surface, then that would create a closed loop. This loop would consist of a path linking both gates within the tree, and also along the surface of the tree.

It turns out that one is stuck in this tree. That means one can leave that tree only through the same gate through which one entered the tree. We call this a cave.

Let us look at a tree and its surface. Click 'New Maze' and 'Enable Wall Colouring' and then click a wall somewhere in the middle of the maze (to get a big tree). Next, mark with the left mouse button the surface of that tree as a purple path. If you follow that surface you will see gates that lead into the coloured tree.

When searching for a path linking a ☺ to the surface of its tree, it is faster to start searching from ☺ than to starting searching from the surface. The reason is that if you start the search from ☺, then at most one cave is to be searched, whereas starting the search from the surface might require to search all caves, i.e. the entire tree.
As shown earlier the two trees and two forests cover all walls in the maze. Therefore, it is enough to determine the red and blue trees, and only for case 1, in addition one of the two forests, which automatically determines the other forest.
 One only knows the size of the forest after it is fully determined, but an indicator for its size and thus for the effort to determine it is the length of the part of the border to which all trees of that forest are connected.

This section is for further personal or guided study.
Above we found a nice characterization of the shortest path if a maze has no loops, and no areas cutoff from each other.
 When colouring all trees with border contact, some trees will be uncoloured. Each one of them is now to be coloured too, each with a different colour, which gives us more 3colour squares. Next we determine the lengths of the paths that link any two neighbouring 3colour squares and the two gates to ☺'s caves. These paths run all along the joint surface of differently coloured trees/forests. Once one has these distances, one can draw a socalled graph consisting of dots (all 3colour squares and the two gates to ☺'s caves) and straight lines linking these points, each with a length measure. One then has to perform an algorithm like Dijkstra's Algorithm to find the shortest path linking the two gates to ☺'s caves by visiting 3colour squares in between.
 For a path to exist at all the two ☺ squares need to be in the same connected part of the maze. If the cut off part is connected to the border, then the border of the rectangular maze is replaced in part by the border of the cut off area. If the cut off area is an island within the maze, then a path around the surface of this island exists. All trees linked to the border of that island are coloured with one colour, and then the algorithms mentioned above are followed.

We found that under the assumption of simple connectedness of all parts of the maze, i.e. the absence of loops, the choice of start and end squares creates a lot of structure on the maze: two trees, two forests, two 3colour squares, two gates to ☺'s caves, and most of the solution apart from the two short paths from the ☺ squares to the surface of their tree. To find these two short paths requires only a very small fraction of the complete search, because a large maze has many trees, and only two caves have to be searched, which is a fraction of their respective trees.
Of course, the benefit of knowing the theory comes only if trees are known or can be quickly determined. In contest questions, trees are not known and cannot be easily determined.
On the other hand, the forests do not have to be determined completely. To find the shared surface between the orange forest and the green forest, it is enough to know whether a wall links to the green or orange section of the border, and thus to pass that wall on the left or the right.