Skip to main content
Puzzling

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

11
  • 3
    $\begingroup$ See xnor's answer; it is certainly possible (in principle) to create a list of moves which would move you through any maze to the end. This list would, however, be ridiculously long. $\endgroup$
    – frodoskywalker
    Commented Jul 16, 2015 at 8:08
  • 1
    $\begingroup$ @JLee The point you are missing is that it's not really a problem if you guess wrong about where you are in the maze, if you already have guessed wrong about the layout of the maze. $\endgroup$
    – Taemyr
    Commented Jul 16, 2015 at 10:21
  • 1
    $\begingroup$ @frodoskywalker xnor is no doubt brilliant, but most of his answers sound like Greek to me, and my eyes quickly glaze over, and this one is no exception. He reminds me of many of the college professors I had- super smart, but without the ability to put it into terms that less smart people (me) can understand. A small example or two (say, with a 4x4 maze?) would work wonders for my brain, but theoretical answers never provide those. $\endgroup$
    – JLee
    Commented Jul 16, 2015 at 13:56
  • 2
    $\begingroup$ A 4x4 maze has approximately 4 billion arrangements, not excluding invalid (blocked) mazes. The solution would have to give a route for each (group of) arrangements. Maybe I'll try 3x3. That only has 300,000 arrangements... $\endgroup$
    – frodoskywalker
    Commented Jul 16, 2015 at 14:49
  • 1
    $\begingroup$ 3x3 has 12 places where a wall can be placed so we have 2^12 configurations. Multiply this by 8 (or 9?) places where the robot can be placed and we have no more than 8 * 2^12 = 32768 different mazes+starting positions. For 4x4 it would be 15 * 2^24 = 251658240. For 20x20 it's around 2.4e+231 $\endgroup$
    – ypercubeᵀᴹ
    Commented Jul 16, 2015 at 16:48