One common method for solving a maze is to imagine walking through the maze with

Question

One common method for solving a maze is to imagine walking through the maze with one hand kept in contact with a wall (on either side), and following the wall wherever it leads.

1.) Confirm or refute the claim that if one starts at any doorway to the exterior of the maze, the hand-on-the-wall approach will always find a way back out (even if it is the same as the entrance.)

2.) Confirm or refute the claim that if one starts at any location within the maze and puts a hand on the wall and follows that wall, that an exit out of the maze will be found.

Please Explain your answers. Thank you!

Explanation / Answer

For both the parts, my answer would be a 'Yes' that if one starts at any doorway to the exterior of the maze, the hand-on-the-wall approach will always find a way back out and if one starts at any location within the maze and puts a hand on the wall and follows that wall, that an exit out of the maze will be found.

If someone goes into a maze, becomes disoriented and then tries to use the right-hand rule, he/she might unwittingly follow an island section of wall and this would lead to nowhere. If however, one starts with the entryway right-hand wall and never breaks contact with it, one will never become attached to an island section of the wall.

To give you another perspective into why this wall following works is topological. Assuming the walls are connected, then the wall can be deformed into a loop or circle. The wall following procedure reduces to walking around a circle from start to finish. To explain this further, notice that if we group together the connected components of the maze walls, the boundaries between these maze walls are precisely the solutions, even if there is more than one.

There are various algorithms to explain this, if you're looking for any specific algorithm please let me know.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.