MHB How Does the Euler Circuit Algorithm Solve Mazes?

  • Thread starter Thread starter annie122
  • Start date Start date
  • Tags Tags
    Circuits Euler
AI Thread 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?
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top