Timeline for Maze Solving Robot
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2016 at 12:02 | comment | added | trichoplax is on Codidact now | xnor's answer can be understood from the initial paragraph, without needing to worry about the symbolic notation in the proof. (1) Start with a list of every possible maze, including the same layout with a different starting position as a different maze. (2) For the first maze, write down the moves that will take you from start to exit. (3) For the next maze, you know that starting point, but you also have the list you wrote down of what you already tried. That list tells you where you would be if this was the correct maze, so write down how to get from there to the exit. (4) Repeat for all | |
| Jul 16, 2015 at 17:26 | comment | added | JLee | @ypercube The walls of the finishing square (aka the room) are always there and cannot be removed. So, aren't your original figures more accurate? | |
| Jul 16, 2015 at 17:21 | comment | added | ypercubeᵀᴹ |
And I forgot to factor the finishing square so my numbers are lower. For 3x3, it should be 9 * 8 * 2^12 = 294912 and for 4x4 around 4 billion. So @frodoskywalker was correct!
|
|
| Jul 16, 2015 at 16:51 | comment | added | JLee | @ypercube Yes, that's right. I think frodo might have been factoring in the outer wall of the room too, but your figure is accurate. Although, this info doesn't help me much with my main question. | |
| Jul 16, 2015 at 16:48 | comment | added | ypercubeᵀᴹ |
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
|
|
| Jul 16, 2015 at 14:59 | comment | added | JLee | @frodoskywalker I understand there are many possible mazes, and I understand that you could start anywhere in the maze, and that you don't have any way of telling where you are, even after making a move. So, there are 20x20-1= 399 different cells that can be the start square. So, for each of the trillions of trillions of possibilities, we can append to a huge list 399 solutions, 1 from each cell. So, my confusion is, how do we know what order to execute these in? Not knowing where we are in the maze is messing up my ability to work out how this list is guaranteed to find the solution. | |
| Jul 16, 2015 at 14:49 | comment | added | frodoskywalker | 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... | |
| Jul 16, 2015 at 14:14 | comment | added | frodoskywalker | @JLee that's a good point; intellectual brilliance is very different from brilliance at teaching. I'll see if I can produce an example, though even the 4x4 one might be too large; the 20x20 solution is enormous. | |
| Jul 16, 2015 at 13:56 | comment | added | JLee | @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. | |
| Jul 16, 2015 at 10:21 | comment | added | Taemyr | @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. | |
| Jul 16, 2015 at 8:08 | comment | added | frodoskywalker | 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. | |
| Jul 16, 2015 at 3:52 | history | answered | JLee | CC BY-SA 3.0 |