Wizard's Labyrinth

Question

A thief has snuck his way into the wizard's castle. After traversing a plethora of magical traps and illusory walls, he finally spies the wizard's hidden stash of gems beyond the end of a long corridor. He hastily runs toward it, realizing only a moment too late that he has fallen into another trap.

As soon as the thief enters the corridor, a magical flame ignites behind him, and the corridor is divided into segments by thick walls of fog. A message from the wizard appears on the wall of the corridor, lit with a magical glow:

This corridor has 10 segments, each identical and symmetrical in appearance. The first has no special properties, but some of the remaining 9 will turn you around as soon as you enter them. You will feel nothing, but the way forward will become the way back. If you blindly continue, you will end up back where you started. Should you move between segments more than 30 times, you will be trapped in an alternate dimension.

None of the thief's navigational aids are working, and the corridor resists any attempt to mark it. How can the thief guarantee his escape from the labyrinth?

If you move forward from A to B, and B is a reversing segment, you remain in B but going forward again will lead to A. You could move backward while in B and go to the next segment instead. — Woofmao, Jan 29 '20 at 02:25
So you know where each segment's boundaries are? That is, it's a sequence of discrete steps? — Deusovi, Jan 29 '20 at 03:24
I gather that there is no way to distinguish between segments, apart from the initial one that you will recognize if you ever get back to it, right? — Arnaud Mortier, Jan 29 '20 at 08:25
I think the problem description is similar to this one: https://puzzling.stackexchange.com/questions/91671/controlling-a-robot-blindfolded-on-a-9x9-grid , i.e., develop a sequence of steps that bring the thief to the target field, no matter where the magical turing segments are. — daw, Jan 29 '20 at 12:44

score 4 · Accepted Answer · answered Jan 29 '20 at 12:43

4

The following sequence of steps should bring the thieve through the corridor (F=forward, B=backward):

FFBFFFBFFFBFFFBFFFBFFFBFFFBF
Note the periodic pattern: initial FFB followed by (possibly truncated) FFFB sequences. These patterns can also be used for corridors of other lengths. I found this solutions by using a program to find solutions for shorter corridors, noting the pattern, and trying this one. These are 28 steps, slightly shorter than the prescribed upper bound.

answered Jan 29 '20 at 12:43

daw

3,178
6
21

2

I verified by computer that this works. I don't know why, but it does. – Jaap Scherphuis Jan 29 '20 at 13:59
@Jaap Scherpius Those were exactly my thoughts when creating the puzzle! – Woofmao Jan 29 '20 at 15:38

newbie · Answer 2 · 2020-01-29T14:12:48.310

1

I deployed a decision tree search and here's my list for optimal answers. Of course, it's not the best approach possible, but the answers do reveal something.

The optimal numbers of steps are 4 7 10 13 16 19 22 25 28 for 3 4 5 6 7 8 9 10 11 segments.

Update: I found a pattern similar to @daw's: FFBBFFBBFFBBFFBB... or FBBFFBBFFBBFF... (F-Forward, B-Turn & Forward) The proof seems rather hard.

edited Jan 29 '20 at 14:12

answered Jan 29 '20 at 10:13

newbie

907
4
11

My guess is that this is like many ball-weighing puzzles, where the key to the solution is that as you make measurements, you don't only eliminate possibilities directly, but you also group the remaining possibilities in such a way that you can tailor future measurements to eliminate them efficiently. – hdsdv Jan 29 '20 at 11:02
Also, I think your description is a bit off. You don't have red and green buttons, because it's possible to arrive at (say) room 4 without knowing whether you came from room 3 or room 5. But it's also possible to arrive at room 4 knowing for sure that you came from room 3. If the room had red and green buttons, those two cases would be indistinguishable. – hdsdv Jan 29 '20 at 11:05
@hdsdv Yes, my search is rather a decision-tree approach. In short, I'll list all the current possible configurations and where I'm at in those configurations and search subsequent moves. You may check on small numbers. I'm not sure where the description is off tho, take 'move forward' and 'move backward' as left and green buttons, can we really know any more information? I'm unclear about the exact case you're describing. – newbie Jan 29 '20 at 11:42
@hdsdv I think I knew where I'm off, thanks. 'Turning back' is indeed not equivalent to those buttons. So whether you're heading forward or backward needs to be taken account. – newbie Jan 29 '20 at 11:50
I've modified my program. The puzzle looks reasonable to me now. – newbie Jan 29 '20 at 12:01
1

I verified by computer that those two sequences work too. Note that because B is defined differently here to @daw 's solution, the first sequence is essentially identical to daw's. – Jaap Scherphuis Jan 29 '20 at 14:23
That makes sense. @JaapScherphuis – newbie Jan 29 '20 at 14:52

score 0 · Answer 3 · answered Jan 29 '20 at 13:29

This may be an out-of-the-box answer, but here goes:

Assumptions:

The puzzle leaves room for several assumptions

The question states, “None of the thief's navigational aids are working, and the corridor resists any attempt to mark it.”

Nevertheless, the thief can still stand on the ground and he can be considered an object.

The OP didn’t state that the reversing only works for living objects. So we can assume that the reversing can also work for projectiles. Also, from the above statement, the thief has tangible objects (navigational aids he can use)

From the statement, ”... he finally spies the wizard's hidden stash of gems beyond the end of a long corridor,” the following can be observed:

The end of the corridor is in eyesight of the thief. If that is further divided into 10 equal segments, the fog can’t be too thick for not being able to toss/roll an object through.

Solution

With the above assumptions, the solution can be:

Toss/roll an object, say one of those navigational aids, through the thick fog.

Case 1:

If the item passes through, the next segment is not a reversing segment. Walk forward into the next segment.

Case 2:

If the item comes back through the fog, the next segment is a reversing segment. Walk forward into the next segment, then turn around and toss/roll again.

If you follow the actions based on the above two conditions, you should be reaching the end and escaping the corridor in

10 steps.

Not the intended answer, but probably the one the thief ended up with anyway. — Woofmao, Jan 29 '20 at 15:37

Wizard's Labyrinth

3 Answers3

Assumptions:

Solution