MHB How Does the Euler Circuit Algorithm Solve Mazes?

  • Thread starter Thread starter annie122
  • Start date Start date
  • Tags Tags
    Circuits Euler
Click For Summary
The Euler Circuit Algorithm for solving mazes involves specific rules for traversing edges, particularly emphasizing that from a new vertex any edge can be taken, while from an old vertex, the last edge traversed must be retraced if it was the only option. A key point of confusion arises around the rule that states no edge should be used more than twice, leading to questions about whether using an edge three or more times is permissible. The algorithm constructs a walk that forms an Euler circuit by effectively doubling each edge in the original maze, which is crucial for ensuring all paths are covered without repetition. Clarification is sought on the algorithm's name and the exact textbook reference for better understanding. The discussion highlights the need for clearer explanations of how the algorithm effectively solves maze problems.
annie122
Messages
51
Reaction score
0
I didn't understand the algorithm explained in my textbook. ("Introduction to combinatorics" P.165)

I would an alternative explanation with an example.

Here is the algorithm:

(i) from a new vertex, any edge may be taken;

(ii) from an old vertex, if the edge just traversed was nes, then turn around retake it;

(iii) never use any edge three times.

I used the algorithm in one maze, but at one point it became inevitable for me to take the edge for the third time.
A question regarding (iii); does it disallow me from taking the edge more than three times, or is it okay to take an edge, say, four times?

Also, I don't understand how this works. It was explained that the walk constructed in this way is an Euler circuit in the network formed by doubling each edge in the original. How does this lead to solving the maze?
 
Physics news on Phys.org
Yuuki said:
I didn't understand the algorithm explained in my textbook. ("Introduction to combinatorics" P.165)

Hi Yuuki, :)

Can you please provide the exact title and the author of your book. Also what is the name of the algorithm used to find Eularian Circuits?
 

Thread 'A variant of the Monty Hall problem'

There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...
View full post »

Similar threads

MHB How many edges does the graph have?
  • · Replies 4 ·
Replies
4
Views
2K
Circuit analysis via polyhedron
  • · Replies 5 ·
Replies
5
Views
2K
Euler circuit in a directed multigraph
  • · Replies 2 ·
Replies
2
Views
5K
MHB Does K5 contain Eulerian circuits? (why?) If yes, draw them.
  • · Replies 4 ·
Replies
4
Views
7K
I A way to comprehend the geometry of a hypercube
  • · Replies 2 ·
Replies
2
Views
2K
MHB Problem on Graph Theory and Algorithms
  • · Replies 2 ·
Replies
2
Views
3K
MHB Proof of Euler Tour in Graphs: In-degree($v$)=Out-Degree($v$)
  • · Replies 1 ·
Replies
1
Views
2K
A Can the orientation of a body be defined by Euler angles?
  • · Replies 18 ·
Replies
18
Views
2K
I Can Any Quantifiable Variable Serve as a Coordinate in Euler-Lagrange Equations?
  • · Replies 5 ·
Replies
5
Views
2K
Algorithm for the min. distance over a set of points randomly distributed
  • · Replies 3 ·
Replies
3
Views
1K