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.

10
  • $\begingroup$ @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 $\endgroup$
    – Mike Earnest
    Commented Jul 16, 2015 at 3:25
  • 1
    $\begingroup$ @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 $\endgroup$
    – Mike Earnest
    Commented Jul 16, 2015 at 16:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lopsy
    Commented Jul 16, 2015 at 16:31
  • 1
    $\begingroup$ @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. $\endgroup$
    – COTO
    Commented Jul 17, 2015 at 16:40
  • 2
    $\begingroup$ FYI, this question has spawned another, which has an answer for the 3x3 grid in 91 moves: codegolf.stackexchange.com/q/53310/20198 $\endgroup$
    – Nathan Merrill
    Commented Jul 17, 2015 at 22:29