Talk:Maze-solving algorithm

Random mouse algorithm

It is incorrect that random mouse algorithm "will always eventually find the solution". In most cases such algorithm would trap the mouse indefinitely in a section the only exit from which is in the middle of the wall. I would suggest changing the wording to smth along the lines of "may eventually find the solution". --Louigi Verona (talk) 10:05, 10 October 2011 (UTC)

The Random Mouse algorithm as currently described will never trap the solver so that it can't reach the exit. It proceeds until a junction is reached, meaning if it's on a straightaway and there's a path off to the side, it will stop and potentially take the side passage. The Random Mouse will not necessarily pass all side passages until it rams into a wall. (If it did do that, then it could indeed get trapped, for example in a passage shaped like a capital "T", with the two sides being dead ends and the base of the "T" being the only way out, where the solver would go back and forth across the top of the "T" forever.) This means Random Mouse will eventually solve any standard Maze, although it may take arbitrarily long to do so if it keeps getting bad luck with the randomly chosen passages. Thanks, - Cruiser1 (talk) 04:14, 12 October 2011 (UTC)

Trémaux

The description auf the Trémaux algorithm is incomplete. It does not work. The original rules by Trémaux. -- RTH (talk) 15:49, 24 April 2009 (UTC)

Corrected --Ein student (talk) 17:44, 12 March 2010 (UTC)

"When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start."

This is directly contradicted by the gif in this section. 10:04, 24 November 2016 (UTC) — Preceding unsigned comment added by 124.171.84.237 (talk)

I find the description to be somewhat vague. The "otherwise" instruction subsection is as difficult to follow as the maze Im trying to solve. Furthermore, there seems to be some inconsistencies (perhaps variants exist) with other sources Ive found online. I have found some documents that suggest the importance of marking which path one came down originally each time a new junction is arrived at, and that other path taken, though marked, must be marked uniquely from the path that got you there. 50.35.103.217 (talk) 18:47, 27 June 2017 (UTC)

Maze blog

It was an ad page. Searched for similar blog, but someone else may find a better one. —Preceding unsigned comment added by 62.47.162.12 (talk) 07:11, 26 July 2010 (UTC)

Solution vs Traversal

This article refers to both solution and traversal. To my mind, solution simply involves finding a route from the start to the finish but does not necessarily find the best solution and will probably not find every branch. Traversal finds a complete description of the maze, including all branches. This distinction should be mentioned. treesmill (talk) 21:43, 16 May 2011 (UTC)

Maze with two solutions

The example Maze with two solutions seems way to complicated. What it it's purpose? If it's just there to show a maze with two solutions then a smaller simpler maze would be better. Currently it's just an example of a large maze because any details are lost. How can I even verify it has only two solutions? It leads me to come to the conclusion that all mazes with two solutions must be very large, although I know this isn't the case. -87.114.252.206 (talk) 01:03, 29 May 2013 (UTC)

One-way door mazes

The most interesting of all mazes, IMO, is mazes with one-way doors. This is not a complication for a computer, in that it can efficiently find solutions for such mazes. However, a person in such a maze finds themselves in a far more challenging situation than when in a similar sized traditional maze. A simple chain of N rooms with one door forward and one leading back to the start will cause a child running randomly to have to go through an expected 2^N doors before getting out. Even with a map, such a maze takes O(N^2) transitions. I've come up with a solution and posted an implementation in C on github. I hope that since I can find no other algorithms described for one-way door mazes that the section I added can stay, though it clearly can be improved.WaywardGeek (talk) 18:56, 20 June 2013 (UTC)

I see that the one-way door section was deleted. That seems pretty normal for Wikipeda. So now this page has exactly zero on one-way door mazes. Whatever...WaywardGeek (talk) 19:14, 5 May 2014 (UTC)

Breadth-First Search

The Java example given is simply a breadth-first search. This should probably be replaced with a more general discussion of how that algorithm applies to mazes. --2601:1:1B80:234:8800:19CF:8130:A1DA (talk) 03:32, 17 March 2015 (UTC)

Oddity in references

Between reference 5 and reference 6 occurs this text: "Charles Tremaux (° 1859 – † 1882) Ecole Polytechnique of Paris (X:1876), French engineer of the telegraph". Does it belong there? 86.132.223.212 (talk) 15:38, 4 June 2016 (UTC)

Minimal examples

Hello. I am a newbie to the subject, and here is my feedback.

1. I would welcome simple (minimal? though not trivial) examples of the concepts introduced. For example:
   • Simply connected
   • Not simply connected, and more specifically:
     • One where "the start or endpoints are in the center of the structure surrounded by passage loops", and
     • One where "the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops"
   • Mazes with more than one solution. The current example is humongous, and I am hoping one can find smaller examples. I don't object keeping the pretty picture of the humongous example, but a minimal one should be given as well.
2. Also, the picture of the Pledge algorithm shows a "Left-turn solver trapped", but the left-turn rule was never introduced. On the other hand, I would also welcome an example where the Pledge algorithm succeeds and the wall follower fails.

Thanks. 160.83.42.135 (talk) 17:01, 7 March 2017 (UTC)

Human or Computer, Distinctions to be made

I feel as though some of these algorithms should have their own page. Or perhaps be specifically distinguished with their own major and devoted section. I originally came here looking for techniques for real humans to solve real labyrinths using logic and strategics. Instead what I find are algorithms for computers with an omniscient view of the maze. There is a huge difference and distinction here that is being obfuscated, and it saddens me to see that people cannot think outside of computation and cyberspace. There should be a breakdown on the type of solution processes that are available. Which require omniscient birds-eye views. Which require foreknowledge of an exit location. Which require vast memory, or vast calculation skills, etc. What each are optimized for, whether they are meant for humans or computers, etc. And how each can fail. There is a lack of meaningful content in this article as its mostly meant for programming. 50.35.103.217 (talk) 18:47, 27 June 2017 (UTC)

Pledge Algorithm

The pledge algorithm needs clarification.

The pledge algorithm starts out by saying wall-following fails sometimes, which is why pledge is needed. But then it goes on to give an example of a simple maze that fails because of a left-turn algorithm, not a wall-following algorithm. If the wall were followed an exit would be found. And no distinction is made by the example between a wall-following and a pledge algorithm. 50.35.103.217 (talk) 18:55, 27 June 2017 (UTC)

I realize this is an old post, but I agree the example needs clarification. It took me an embarrassingly long time to understand what was going on, as my wall follower algorithm in my game would not get stuck in a loop with the example maze. It wasn't until I saw a video of robot using a left-turn algorithm before I understood it was the example here that was misleading me. Rdsarson (talk) 13:13, 27 October 2023 (UTC)

I had another question: what does the Pledge Algorithm do when it needs to do a 180 degree turn? Does this count as +0.5 rotations or -0.5 rotations on the angle-counter? Charmoniumq (talk) 20:30, 7 May 2018 (UTC)

It depends on whether the implementation of Pledge Algorithm is following the left or right hand walls. Pledge Algorithm doing a 180 degree U-turn only happens when moving in the primary direction, and hitting a corner which turns in the opposite direction of the wall following choice, so that when wall following is started upon the far wall that's hit, it immediately makes one follow the wall back up the passage away from the corner. There's nothing special about the U-turn, and it being +/- 0.5 rotation happens the same as any more gradual turning around. Thanks, - Cruiser1 (talk) 18:03, 9 May 2018 (UTC)

Question: Picture in section "Shortest Path algorithms"

The section and the description of the picture deal with mazes with multiple solutions. A solution should be a path between start and finish of the maze. The maze in the picture doesn't seem to have neither a start nor a finish - what would be a solution in this case? A path between any two places in the maze? A path between any two places on the edge of the maze? Or am I missing something here? Katzenpfote (talk) 01:58, 3 January 2019 (UTC)

Indeed, this isn't the best example picture, since a Maze should clearly indicate its start and end points. A common practice is to have the start in the upper left corner, and the end in the lower right corner. The viewer should assume that's the case, or else pick their own start and end points. A shortest path algorithm will be able to work regardless of the start and end points chosen (assuming at least one solution exists). Thanks, Cruiser1 (talk) 23:42, 14 March 2019 (UTC)

"Maze-solving algorithm"

The algorithm listed under "Maze-solving algorithm" doesn't seem to work reliably. I was looking for a maze solver with bounded memory requirements, and implemented that one. If you're going from one corner to another in a square grid, and there's an obstacle in the center, you get stuck wall-following round and round the center obstacle.

The source cited at [1] is paywalled, but there is a copy of that paper online at CMU at [2]. The version of the algorithm in the paper ("Algorithm 1", page 4) is somewhat different than the one in the Wikipedia article. I think the problem is, at least, that the paper has a line MDbest←MDbest−1 which isn't in the Wikipedia article. Not sure yet. But I'm not going to debug code in Wikipedia; that would be OR.

This algorithm was put into Wikipedia by an anon at [3]. That's the only edit ever seen from that IP address. So there's no one to ask. --John Nagle (talk) 04:09, 28 June 2019 (UTC)

I got a version working. The termination test for wall-following in the paper is sightly off, rendering the proof unsound. But it would be WP:OR to fix it. Here's my working version in Python.[4]. But, again, WP:OR. It's really a variant of Pledge's fix to wall-following, which is already in the article. John Nagle (talk) 23:54, 28 June 2019 (UTC)

Origin Shift algorithm

What about the Origin Shift algorithm, as described in [5] by CaptainLuma? Is this a new maze creation algorithm? — Preceding unsigned comment added by 193.191.180.235 (talk) 09:39, 2 July 2024 (UTC)

We cannot include material without published reliable sources. A YouTube video does not meet that standard. —David Eppstein (talk) 17:21, 2 July 2024 (UTC)