One hand rule. How to find a way out of the maze The result of the procedure

At intersections, give preference to unmarked trails. Whenever you come to an intersection, take a moment to look at the markings on each trail. Some of them may be unmarked, while others will show that you have already selected them once (or twice). It is worth giving preference to trails without marks. This way you are more likely to move forward. If all trails are marked once, choose one at random.

Avoid trails marked twice. If you are forced to follow a path that you have already marked once, you should mark it a second time. According to the Luc-Tremaux algorithm, a double-marked trail will not lead you to the exit. If you find an intersection where the same path is marked twice, always take the other path, even if it means you have to turn back.

Go back if you hit a dead end. If you reach a dead end, you need to return to the last intersection you crossed. Don't forget to mark the path so you know it leads to a dead end. Once you reach the crossroads, choose one of the remaining paths and continue through the maze.

Good day, dear community.

background

One fine day, while walking through the Internet, a labyrinth was found. It became interesting to find out its passage and after walking around the network, I still did not find a working software implementation, a solution to the labyrinth.

Here he is:

The working day was boring, the mood was excellent. The goal, the means and the will are there. The conclusion is obvious, we will pass.

Story

For a convenient solution, it is necessary to bring the existing image of the labyrinth to the type of a two-dimensional array. Each element of which can take one of 3 values:

Const WALL=-1; BLANK=-2; DEADBLOCK=-3;

First, I want to show the functions for scanning the image of the maze, followed by writing data to the array, and the function for generating a new image based on the data from the array:

Image scan:

varN:integer=600; LABIRINT:array of integer; ... varbit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Free; ... end; end; ...

Image generation:

varN:integer=600; LABIRINT:array of integer; ... procedure genBitmap; varbit:TBitmap; i,j: Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack else bit.Canvas .Pixels:=clRed; end; bit.SaveToFile("tmp.bmp"); bit.Free; end; ...

First, you need to re-save the image as a monochrome bmp in order to have 2 colors white or black. If you look closely at the maze, it has a 2 pixel thick wall and a 4 pixel thick road. It would be ideal to make the thickness of the wall and the road 1 pixel. To do this, you need to rebuild the image, divide the image by 3, that is, remove every 2nd and 3rd, row and column of pixels from the picture (this will not affect the correctness and passability of the maze).

Prepared drawing:

Image width and height: 1802 pixels.

1. Use the image scanning function.
2. Rebuild the image:

varN:integer=1801; LABIRINT:array of integer; ... procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3)) do for j:=0 to ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; end; ...

3. We generate the rebuilt image.

The result of the procedure:

Image width and height: 601 pixels.

And so, we have an image of a maze of the desired type, now the most interesting thing is the search for all options for passing the maze. What do we have? An array with the written values ​​WALL - wall and BLANK - road.

There was one unsuccessful attempt to find the passage of the maze using the wave algorithm. Why unsuccessful, in all attempts this algorithm led to the “Stack Overflow” error. I am 100% sure that using it, you can find a walkthrough, but there was a fuse to come up with something more interesting.

The idea did not come immediately, there were several implementations of the passage, which in time worked for about 3 minutes, after which an insight came: “what if we look not for paths of passage, but for paths that do not lead to the passage of the maze and mark them as dead ends.”

The algorithm is this:
Run a recursive function over all road points of the maze:
1. If we are standing on the road and there are 3 walls around us, we mark the place where we are standing as a dead end, otherwise we exit the function;
2. We pass to a place that is not a wall from point No. 1, and repeat point No. 1;

Software implementation:

varN:integer=600; LABIRINT:array of integer; ... procedure setBlankAsDeadblockRec(x,y:integer); vark:integer; begink:=0; if LABIRINT=blank then begin if LABIRINT<><><><>BLANK then k:=k+1; if k=4 then LABIRINT:=DEADBLOCK; if k=3 then begin LABIRINT:=DEADBLOCK; if LABIRINT=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; ...

Conclusion

I got a "complete" working algorithm that can be used to find all the way through the maze. The latter exceeded all expectations in terms of speed. I hope my little work will benefit someone or push to new thoughts.

Program code and passed maze:

//Please don't kick me for the programming language I used. unit Unit1; interface uses Windows, Graphics, Forms, Dialogs, ExtCtrls, StdCtrls, Controls, Classes; const WALL=-1; BLANK=-2; DEADBLOCK=-3; type TForm1 = class(TForm) Button1: TButton; OpenDialog1: TOpenDialog; procedure Button1Click(Sender: TObject); private ( Private declarations ) public ( Public declarations ) end; var Form1: TForm1; N:integer=600; LABIRINT:array of integer; implementation ($R *.dfm) procedure genBitmap; varbit:TBitmap; i,j: Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack else bit.Canvas .Pixels:=clRed; end; bit.SaveToFile("tmp.bmp"); bit.Free; end; procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3)) do for j:=0 to ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; end; procedure setBlankAsDeadblockRec(x,y:integer); vark:integer; begink:=0; if LABIRINT=blank then begin if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if k=4 then LABIRINT:=DEADBLOCK; if k=3 then begin LABIRINT:=DEADBLOCK; if LABIRINT=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; procedure TForm1.Button1Click(Sender: TObject); varbit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Free; setDeadblock; genBitmap; end; end; end.

To find the shortest path, it is planned to apply the wave algorithm to the found passages of the maze. It would be interesting to hear what other algorithms can be applied to quick finding a way in a big maze?

One of the simplest rules for passing the labyrinth is the rule of "one hand": moving through the maze, you must always touch its wall with your right or left hand. This algorithm was probably known to the ancient Greeks. You will have to go a long way, going into all the dead ends, but in the end the goal will be achieved. Although this rule has one drawback, we will talk about it later.

Let's try to describe a robot acting in accordance with the "right hand" rule.

At the beginning of its work, the robot must find a wall to follow. To do this, he can simply move forward until he hits an obstacle.

After the robot hits an obstacle, it starts to move in accordance with the "right hand" rule.

Moving along the wall, the robot checks if there is a passage on the right. If there is a passage, the robot must follow it so as not to break away from the wall on the right.

If there is no passage - there is a wall ahead - the robot turns left. If there is no passage again, he turns left again, thus turning 180 degrees, and goes in the opposite direction.

The block diagram of the algorithm for a robot operating according to the "right hand" rule is shown in the figure.

Let's try to check the operation of this algorithm and write a program for it. For this purpose, let's turn to the programming environment. This environment is a convenient tool for modeling various algorithms related to robot control. It has a turtle performer, which at its core is nothing more than a real robot. The turtle has a very convenient set of commands - forward, right, left, back. In addition, there is a sensor in the center of the turtle that takes a value from 0 to 100, depending on the tone of the surface on which it is located.

The Logo language dialect we will be using is very simple and similar to Basic. You can get acquainted with the commands of the language. A free download of the GameLogo programming environment - . The size of the distribution is small - only 1 Mb.

The GameLogo archive contains backgrounds with labyrinths, one of which we will use.

At the very beginning of the program, we will give the command to the turtle to raise the feather (by default, the turtle leaves a trail behind itself).

The field size is 800 x 600 dots. The starting position for the turtle is at coordinates 115, 545 (white square).

The color of the labyrinth tracks is light, on them the sensor will take values ​​greater than 50. The color of the walls of the labyrinth is dark, the sensor value will be less than 50. The exit from the maze is represented by a black square, the sensor value above which will be equal to 0.

Let's declare a flag variable, with the help of which we will control whether the exit from the maze has been reached.

Let's write a program and run it using the big red button labeled "Run".

Variable background flag = maze1.gif raise pen spot 115, 545 "search for the first wall repeat until gauge > 50 (forward 12) "right hand rule repeat until flag = 0 (right 90 forward 12 if sensor = 0 then flag = 1 otherwise if sensor

If it is known that the maze does not have separate walls, that is, there are no closed routes along which you can return to the starting point, then such a maze is called simply connected and it can always be bypassed completely by applying the "one hand" rule.

If the labyrinth contains free-standing walls, then, using the "one hand" rule, it is not always possible to go through all the corridors and dead ends. Labyrinths with separate walls and closed paths are called multiply connected. At the same time, multiply connected labyrinths can be divided into two groups: without a "loop" around the goal (a closed route does not pass around the goal) and with a closed "loop" around the goal (the goal can be bypassed along a closed route).

In multi-connected labyrinths of the second group, the "one hand" rule does not work, and using it, it is impossible to achieve the goal. But even these labyrinths can be passed relying on an exact algorithm.

The solution of the problem of such labyrinths belongs to a relatively late time, and it was initiated by Leonhard Euler. Euler, not without reason, believed that a way out of any labyrinth could be found, and moreover, in a relatively simple way.

The universal algorithm for passing through any labyrinths was described only a century later in the book of the French mathematician E. Luc "Recreations matematiques", published in 1882. Interestingly, when describing the algorithm, Luca pointed to the primacy of another French mathematician, M. Tremaux. Thus, the algorithm became known as Lucas-Tremo algorithm.

Tremo proposes the following rules: leaving any point of the labyrinth, you must make a mark on its wall (cross) and move in an arbitrary direction to a dead end or crossroads; in the first case, go back, put a second cross, indicating that the path has been traveled twice - back and forth, and go in a direction that has never been traveled, or traveled once; in the second - go in an arbitrary direction, marking each intersection at the entrance and at the exit with one cross; if there is already one cross at the crossroads, then you should go a new way, if not, then the path traveled, marking it with a second cross.

Knowing the Tremo algorithm, you can correct the behavior of the legendary Theseus. Inspired by the gift of his beloved Ariadne, he confidently walks through the labyrinth. Suddenly, a passage appears in front of him, along which a thread has already been stretched ... What to do? In no case do not cross it, but return along the already known path, doubling the thread, until there is another untraversed move.

Using a variant of the Tremo algorithm, the father of information theory, Claude Elwood Shannon, built one of the first self-learning robots. Shannon gave him the sonorous name "Theseus", but in history "Theseus" became better known as Shannon's "mouse". The "mouse" first explored the entire maze, and then (for the second time) went all the way much faster, avoiding sections that had been passed twice.

At the first Russian Robot Olympiad, competitions were held, the purpose of which was to pass a kind of labyrinth: in the shortest possible time, moving through the "open doors" in the walls, the robot had to get from the start to the finish. The robot could control its movement along the black lines drawn on the floor of the labyrinth.

This picture is now circulating all over the Internet. This is often accompanied by the following text: The Israeli military intelligence has a special unit in which boys and girls serve with various disorders of the autism spectrum. Autistic people mostly analyze maps and aerial photographs that appear on computer screens. Due to the peculiarities of their thinking, they pay attention to the smallest details, the consideration of which in the preparation of military operations on the ground makes it possible to prevent possible losses of personnel. In this way, autistic scouts save the lives of soldiers."

Have you tried this maze?

Let's find out more about this issue.

even at the mention of this labyrinth it is specified that " An autistic person is able to process visual and textual information several times faster than a person who does not suffer from autism spectrum disorders. This feature of theirs turned out to be indispensable in high-tech. At Specialisterne, a Danish technology consulting firm, 75 percent of its employees are autistic and have Asperger's syndrome, also on the autism spectrum. They differ from ordinary workers in their incredible attention to detail, superhuman concentration, and the ability to quickly process huge amounts of information. These skills are especially useful for software testers. The quality of work of autistic people engaged in this work is several times higher than the quality of work of ordinary people. Autistic people can check 4,000 pages of technical documentation 10 times faster than normal people and never miss a single mistake."

But let's leave the autistic people aside and find out in the end how you can get through this maze! That's how...

The task is unsolvable! We have 3 rooms with an odd number of doors (an analogy with drawings "without lifting your pencil"). In order for the problem to have a solution, it is necessary that there be no more than 2 points (in our case, rooms) with an odd number of lines (in our case, passages)

If we build a graph of this labyrinth, we will see that this is the Euler path, since it has 3 vertices with an odd number of edges (doors), and there can be only two of them to fulfill the test conditions.

The problem of the seven bridges of Königsberg or The Königsberg bridge problem(German Konigsberger Bruckenproblem) is an old mathematical problem that asked how it is possible to pass over all seven bridges of Königsberg without passing over any of them twice. It was first solved in 1736 by the German and Russian mathematician Leonhard Euler.

For a long time, such a riddle has been spread among the inhabitants of Königsberg: how to pass through all the bridges (across the Pregolya River) without passing through any of them twice. Many Königsbergers tried to solve this problem both theoretically and practically during walks. However, no one could prove or disprove the possibility of the existence of such a route.

In 1736, the problem of seven bridges interested the outstanding mathematician, member of the St. Petersburg Academy of Sciences, Leonhard Euler, about which he wrote in a letter dated March 13, 1736, to the Italian mathematician and engineer Marioni. In this letter, Euler writes that he was able to find a rule by which it is easy to determine whether it is possible to pass over all the bridges without passing over any of them twice. The answer was "no".

On a simplified diagram, parts of the city (graph) correspond to bridges with lines (arcs of the graph), and parts of the city correspond to points of connection of lines (vertices of the graph). In the course of reasoning, Euler came to the following conclusions:

• The number of odd vertices (vertices to which an odd number of edges lead) must be even. There cannot be a graph that has an odd number of odd vertices.


• If all the vertices of the graph are even, then you can draw a graph without lifting your pencil from the paper, and you can start from any vertex of the graph and end it at the same vertex.


• A graph with more than two odd vertices cannot be drawn with a single stroke.

The graph theory created by Euler has found very wide application in transport and communication systems (for example, for studying the systems themselves, compiling optimal routes for delivering goods or routing data on the Internet).

In 1905, the Imperial Bridge was built, which was subsequently destroyed by bombardment during World War II. There is a legend that this bridge was built by order of the Kaiser himself, who could not solve the problem of Königsberg bridges and became a victim of a joke played with him by the learned minds who were present at the secular reception (if you add the eighth bridge, then the problem becomes solvable). The Jubilee Bridge was built on the supports of the Imperial Bridge in 2005. At the moment, there are seven bridges in Kaliningrad, and the graph built on the basis of the islands and bridges of Kaliningrad still does not have an Euler path

Here is another solution offered by xlazex

Let's look at picture 1: we will surround each separate part with squares, exclude the "extra" points, i.e. those points, the use of which would increase the possible number of paths, and the exclusion of which will not affect the number of doors passed by the line and the closedness of the contour. For the beginning of the path, take, for example, the point 2 .
Let's look at picture 2: on it, I depicted the same contour, but in such a way that the connections of the starting point with the subsequent ones were more visible. The image clearly shows that the part of the contour outlined in blue cannot be closed once, i.e. even if this part of the contour were the only one, there would be no paths along which it would be possible to construct a closed line.
Bottom line: the problem has no solution in a two-dimensional coordinate system.

But there is a solution in 3D :-)

Okay, joke, joke...