Timeline for Maze Solving Robot
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 31, 2022 at 2:46 | answer | added | Hemant Agarwal | timeline score: 1 | |
| Jul 17, 2015 at 22:29 | comment | added | Nathan Merrill | FYI, this question has spawned another, which has an answer for the 3x3 grid in 91 moves: codegolf.stackexchange.com/q/53310/20198 | |
| Jul 17, 2015 at 16:40 | comment | added | COTO | @Lopsy: For a general maze, with no restrictions on where the common exit square is placed, it's a simple matter to come up with even e.g. a pair of $3\times 3$ mazes that can't be synchronized. However, your "south-west corner" exit stipulation is curious. I quickly proved to myself that one can synchronize all legal $2\times 2$ mazes with this restriction. After a modest bit of experimentation, I was also unable to find any subset of legal $3\times 3$ mazes that couldn't be synchronized. It may be that a synchronizing word always exists subject to your exit condition. I just don't know. | |
| Jul 16, 2015 at 22:53 | comment | added | Lopsy | @COTO: Do you know there's a synchronizing word? | |
| Jul 16, 2015 at 22:14 | comment | added | Conor O'Brien | Why can't the robot have a camera and complete the maze like that? :/ | |
| Jul 16, 2015 at 21:57 | comment | added | COTO | @Lopsy: This is the synchronizing word technique xnor mentions in his solution. The upper bound on the word length needed to synchronize all possible $20\times 20$ mazes would probably cause the grad student tasked with writing the program to soil himself. | |
| Jul 16, 2015 at 20:53 | history | edited | Quark | CC BY-SA 3.0 |
edited body
|
| Jul 16, 2015 at 16:31 | comment | added | Lopsy | Here's a hard variant (possibly too hard for this site?) You know that the finish square is the south-west corner of the maze. There's no trap door: instead, you must guarantee that at the end of the list of directions, the robot is standing on the finish square. Surprisingly, this is possible. | |
| Jul 16, 2015 at 16:27 | comment | added | Bob | The answer doesn't really make clear the distinction between what is taking place before entering the maze and what is happening whilst in the maze. | |
| Jul 16, 2015 at 16:20 | comment | added | Mike Earnest | @Bob The robot doesn't do any simulation. The grad student does the mentioned simulation when writing the program. This is just a mental tool the programmer is using to concoct the list of directions, which will guide the unintelligent robot through every possible maze without it having to think | |
| Jul 16, 2015 at 16:14 | comment | added | Bob | It sounds like you are saying the robot is only given a list of compass directions to follow which it will follows (where possible) without question or deviation the list, but the accepted answer talks about simulating mazes and figuring out where you are in the maze. | |
| Jul 16, 2015 at 13:54 | answer | added | Nautilus | timeline score: 1 | |
| Jul 16, 2015 at 10:20 | answer | added | Dolhescu Stefan | timeline score: -6 | |
| Jul 16, 2015 at 9:49 | answer | added | ypercubeᵀᴹ | timeline score: 11 | |
| Jul 16, 2015 at 4:13 | vote | accept | Mike Earnest | ||
| Jul 16, 2015 at 3:52 | answer | added | JLee | timeline score: 2 | |
| Jul 16, 2015 at 3:51 | answer | added | xnor | timeline score: 35 | |
| Jul 16, 2015 at 3:33 | history | edited | Mike Earnest | CC BY-SA 3.0 |
reworded to clarify that you need to figure whether a program exists, not actually find it
|
| Jul 16, 2015 at 3:25 | comment | added | Mike Earnest | @JLee Recursion, for loops, conditionals, GOTO commands or anything like that are NOT allowed. Only a list of directions, which the robot will follow if able | |
| Jul 16, 2015 at 3:17 | history | asked | Mike Earnest | CC BY-SA 3.0 |