Amnesiac in a ring shaped palace

Question

_{Related: Turn off all lights in a ring-shaped palace}

---

Your boss has trapped you inside a ring-shaped palace, and all you know about the palace is that there are some number* of identical rooms, each of which contains a light which you can toggle on and off, and two doors which lead to adjacent rooms on either side (possibly back into the same room if there is only one). You don't know which lights are on or off to start with. The rooms happen to have the wall bordering the inside of the ring painted black and the wall bordering the outside of the ring painted white, so you can tell which direction is which.

Your job is to switch all the lights off, and once this is done, report to your boss via phone. The caveat is, if there is still a light on, you will be executed. The boss is also impatient, so you can't just keep walking forever.

Unfortunately, you suffer from short-term memory loss. Specifically, after walking through a door, you can only remember a single integer between 1 and N^# inclusive at any time, and must do so. Luckily, you have a few minutes in which you can write down a plan to take around, but you can't continue to edit the plan once you pass through your first door.

_{* An arbitrary unknown positive integer, this could include 1
^# You choose N (which must be a positive integer), see below}

---

What is the minimum N that allows you to escape?^{^}

_{^{^} The first answer with the smallest N out of all current answers will be accepted, but this may change if an answer with a smaller N is submitted. Proof is not required that this N is necessarily the smallest possible N.}

---

NB: This is not a lateral-thinking puzzle. Below are some loopholes I have closed (loopholes I will not accept are not limited to these).

• There are thick doors between the rooms, so you cannot see light from between adjacent rooms, and the door closes behind you as soon as you step through it, so you can't stand in a doorway and look between rooms
• Magical fairies clean any rooms you do not occupy, so you can't leave things behind except from the state of the light
• You don't have any location tracking devices to help you, nor memory storing devices except your planning paper (which cannot be torn or folded), including the state of your body (when the door closes behind you, it hits you so that you fall down and instinctively you fall into the same position every time, and more magical fairies heal your body and redress you in exactly the same clothes you had)
• The lightbulbs are too high for you to detect their temperature
• The rooms are too long for you to detect any curvature in them
• The castle is completely impervious to information exchange (e.g. there are no windows) between inside and out except for you notifying your boss that you are finished
• There is no fuse box for you to turn off, and you can't access the wiring from the switch

---

Congratulations to @Lawrence and @Bass for independently discovering a loophole in the question that I think is a feature and shouldn't be closed. I will award the checkmark to the first lowest N regardless of whether this loophole is used or not, but will be awarding a small bounty (+50) to the first lowest N that doesn't make use of this loophole since some people have already put in quite some effort into their solutions.

Currently, @ajee is the first with both a solution for N=2 with the loophole and a derived solution for N=4 without the loophole.

Answer 1

N = 2

By referencing the wall colors, you should be able to deduce which direction you were going (CW/CCW or R/L) when entering your current room. I used that assumption to come up with a state machine that should be able to accomplish the task with just two states.

Looking at the other answers, my solution does use the "double sentinel" method, although I think that may be unavoidable when iterating through the rooms. A single room serving as an initial marker fails if it's the only lit room, while any more than two rooms is excessive.

Answer 2

Edit: A lot of credit is due to @ffao for devising a better way to deal with the case where there is just one room and reducing the solution by one. (Subsequently, @Lawrence has managed to do even better in their answer).

I now think it can be done with

$N=6$

Strategy

Throughout, we call the number we have to remember $k$.
1. Initialise by switching light in initial room to OFF and set $k=6$, then move one room anti-clockwise.
2. For each subsequent step,
   (i) if $k=1$, switch light in room to ON, set $k=2$ and move one room anticlockwise,
   (ii) if $k=2$ and light is OFF, move one room anticlockwise,
   (iii) if $k=2$ and light is ON, switch light OFF, set $k=3$ and move one room clockwise,
   (iv) if $k=3$ and light is OFF, move one room clockwise,
   (v) if $k=3$ and light is ON, set $k=4$ and move one room clockwise,
   (vi) if $k=4$ and light is ON, set $k=1$ and move one room anti-clockwise,
   (vii) if $k=4$ and light is OFF, set $k=5$ and move one room anti-clockwise,
   (viii) if $k=5$, and light is ON then switch light to OFF and finish.
   (ix) if $k=5$ and light is OFF then switch light to ON, set $k=1$ and move anti-clockwise one,
   (x) if $k=6$ then switch light to ON, set $k=5$ and move one room clockwise.

If we are allowed to assume that there is more than one room, then it can be done with

$N=5$

Strategy with more than one room

1. Initialise by switching light in initial room to ON and set $k=1$, then move one room anti-clockwise.
2. For each subsequent step,
   (i) if $k=1$, switch light in room to ON, set $k=2$ and move one room anticlockwise,
   (ii) if $k=2$ and light is OFF, move one room anticlockwise,
   (iii) if $k=2$ and light is ON, switch light OFF, set $k=3$ and move one room clockwise,
   (iv) if $k=3$ and light is OFF, move one room clockwise,
   (v) if $k=3$ and light is ON, set $k=4$ and move one room clockwise,
   (vi) if $k=4$ and light is ON, set $k=1$ and move one room anti-clockwise,
   (vii) if $k=4$ and light is OFF, set $k=5$ and move one room anti-clockwise,
   (viii) if $k=5$, switch light to OFF, then finish.

Explanation of why this works in the general case

After the initialisation and first subsequent steps, you have two consecutive rooms with the light turned ON. Then, you continue anti-clockwise until you find the next room with the light turned ON, turn it OFF and head back in the other direction. Once you find the room with the light turned ON again, that is the second room. If the room beside it has the light turned OFF, then you are essentially finished because that is the last light you turned off when travelling anti-clockwise. Otherwise, you start the procedure again.

Answer 3

N=5

This builds on @ffao's on-on pattern and is a slight optimisation over @hexomino's 7-step 6-step solution.

I'm assuming that in a 1-room scenario, stepping out of that room will lead to the corridor, and walking around the corridor in either direction consistently will lead back to the same room.

Here's a summary of the strategy:

• You have no unbounded counter, so you rely on backtracking to a sentinel to check whether you turned off a light in a room that you purposely left on. You need 2 lights ON as a sentinel condition. If you only had 1 light ON, then went all the way around and switched that light OFF (so all lights are now OFF), you'd be going in circles endlessly on the backtrack.
• You check the single-room condition first (states 1 and 2), then move to the main plan.

Use $k$ as the counter. Assume the rooms are always visited in the same order in each direction, with the order reversed if the direction changes. Each time you exit a room, face the center of the ring and move to the room either on its immediate left (L) or immediate right (R).

Start in any room, switch OFF the light and initialise 𝑘=1. Then repeat the following procedure based on the value of 𝑘 until the plan says to stop. Upon entering any room, check the light. If there are two lines for your 𝑘, pick based on the light check. Switch the light ON or OFF according to the switch to field, set 𝑘 accordingly, then move into the room in the direction indicated. Your amnesia kicks in, so you repeat the whole process based on the remembered value of 𝑘.

k	light check	switch to	set 𝑘 to	next move
start		OFF	1	L - go set sentinel A
1		ON	2	R - go set sentinel B; doubles as a 1-room check.
2	ON	OFF		Stop - there's only 1 room. Call your boss.
2	OFF	ON	3	R - sentinel B is set; go look for a light to switch off.
3	OFF	OFF	3	R - light already off; keep looking.
3	ON	OFF	4	L - found a light to switch off; backtrack to sentinels.
4	OFF	OFF	4	L - not hit sentinels yet; keep backtracking.
4	ON	OFF	5	L - hit sentinel B; go check sentinel A.
5	OFF	OFF		Stop - sentinel A was turned off the long way. Call your boss.
5	ON	ON	2	R - false alarm. Repeat the procedure.

Note that the state (2,OFF) condition (that starts the plan proper) matches the 'do again' condition once you move back to the sentinel B room from state (5,ON), which is why we can loop back. That condition has the sentinels in an (A=ON,B=OFF) 2-sentinel configuration.

Answer 4

[EDIT: hexomino points out in their answer that we can just use a completely off pattern instead of an alternating pattern to eliminate most of the states here, which makes this answer unnecessarily inefficient.]

Assuming the following is correct, it is a solution for

$N = 7$, assuming we can deduce the direction we came from when entering a room. Otherwise $N = 13$.

To begin, remembering only one integer means that the amnesiac behaves according to a finite state machine, and we are interested in minimizing the number of states. So, instead of talking about the meaning of numbers I'll just describe how my FSM works and the reader is free to assign numbers to states according to their own preference.

While you forget everything upon crossing a doorway, you should be able to deduce which direction you came into that room from. This gives us some wiggle room to remember less numbers.

The main idea of the algorithm is that we create an alternating pattern of on and off lights as we go along, except for a signpost at the very beginning consisting of two on lights.

Whenever we enter a new room, we first check the adjacent room to see if we have an on-on pattern. If we do, this might be the signpost we placed at the beginning, indicating we looped.

We can check if that is the case by doing the following: change the on-on pattern to off-off and go back along the alternating pattern to check the first break in alternation: if it is on-on the signpost was not touched and we go back to making the alternating pattern, but if it is off-off this must mean we must have looped around and ruined our signpost.

This in turn means that the rest of the ring is now a huge alternating pattern, in which case we can just go around one more time until we turn the whole alternating pattern off.

Moving right transitions:

Moving left transitions:

Answer 5

The other answers have done all the hard work, so all that's left is to read the question again to use all the available information to minimise the highest number to remember. I got it down to

3.
(EDIT: hexomino pointed out in the comments that in order for this solution to work, the doors need to work like regular mind scrubbing doors. If they also teleport you to a random position inside the next room, this solution needs two more states. Unless I'm mistaken, that would make it identical with Lawrence's answer. EDIT OF EDIT: Out of Lawrence's answers, I meant the one posted before this one. The one posted an hour and a half after this one happens be identical already :-)

When you get your assignment, you are already in a room. Call that "room 1". Orient yourself so that the black wall is on your left. Call the direction you are facing "forward". The "forward" door leads to "room 2", the room behind you is "room 0". Your overall strategy is to

leave the light on in rooms 0 and 1, then go forward to the next room with the light on, turn it off, and backtrack to check if it that room was room 0. If it wasn't, repeat until it was.

Here's what you need to write on the plan, before turning off the light, remembering the number 1, and going through the "back" door:

At the top, in big bold letters write:

STOP RIGHT THERE! READ THIS NOW! (preferably write this in glow-in-the-dark ink)

And then, below that:

If you already moved, go stand at the door you came through, and face the room, just like you did when you entered the room. Then read on. You have a task from your psycho boss. If you want to live, etc etc.

And below that, the important bit:

You are now remembering a single number. It's called "STATE", it's very important, keep it in mind. The first thing to do is check the colour of the wall to your left. If that wall is black, you are facing forward. If it's white, you are facing back. Also, keep in mind the state of the light when you entered the room. (You may have already needed to turn the light on in order to read this paper)

Below that, put a state transition table like with instructions like this:

Choose your next action according to these rules:

 STATE | FACING  | LIGHT | SET LIGHT | NEXT STATE | NEXT MOVE | Explanation
 ------+---------+-------+-----------+------------+-----------+------------------------------------------------------
 none  | none    | any   | off       | 1          | back      | Just got the task from boss.
 1     | back    | any   | on        | 1          | forward   | First time in room 0
 1     | forward | on    | off       |       CALL BOSS.       | Only 1 room.
 1     | forward | off   | on        | 2          | forward   | In room 1, came from room 0. Start search.
 2     | forward | off   | off       | 2          | forward   | Looking for a light to turn off..
 2     | forward | on    | off       | 2          | back      | Found one. Double back to check if it was room 0.
 2     | back    | off   | off       | 2          | back      | On the way back to room 1
 2     | back    | on    | off       | 3          | back      | Back in room 1. Turn light off and check room 0.
 3     | back    | off   | off       |       CALL BOSS.       | Back in room 0, light was off. We are done.
 3     | back    | on    | on        | 1          | forward   | Back in room 0, light still on, not done yet. Repeat.
 ------+---------+-------+-----------+------------+-----------+------------------------------------------------------
 

And finally, after that table:

When you walk through the next door, remember to keep these instructions in your field of vision, and your flashlight pointed to it, if you have one. This will help you quite a lot, since completely losing your memory in a perfectly dark room will probably do quite a number on your psyche.

To show that you need to remember at least that high a number with this approach, you need to observe that

State 2 is obviously "full": every direction/light combination is assigned to a different action. State 1 is also full: after going through the first door, you need to act the same way whether the light is on or off, so that case "eats up" two direction/light combinations. Even if you tried to rearrange the states, the "only one room" special case eats up at least one state/direction/light combination, so adding that to the required "initialize (eats 2), start search, searching, found, backtracking, back in room 1, checking for end" cases, you always end up with at least 9 cases. With only two numbers, you can only distinguish between 8 cases, so that should be impossible.

Answer 6

Here's an N=2 solution that can be stated fairly simply. The plan:

Before going through any doors, make sure the light is on. Initalise memory to k=2 and step through the counterclockwise door.

Upon stepping through a door, follow these rules while k=1:

• If facing counterclockwise, continue until we find a room lit. Turn off the light, turn around and continue.
• If facing clockwise, continue until we find a room lit. Turn off the light, set k=2 and continue.

Upon stepping through a door, follow these rules while k=2:

• If facing clockwise and the room is dark, call the boss, we're done.
• If facing clockwise and the room is lit, turn around and continue.
• If facing counterclockwise and the room is dark, turn on the light, set k=1 and continue.
• If facing counterclockwise and the room is lit, turn off the light, turn around and continue.

Answer 7

Optimisation of my previous answer with the assumption that we know which room we came from, and hence the last direction of travel. (This is a qualitatively different assumption, based on either changes to the question or my understanding of the original question, so I'm posting it as a different answer. Happy to merge the two answers if required.)

N=3

Start in the middle of any room, switch OFF the light and travel left. We call clockwise travel '→' and counterclockwise travel '←'. In each room, use the first 3 columns to choose the appropriate row (rule) to use. When entering any room, keep a hand on the door you entered, so that you know which direction you were travelling in before.

old 𝑘	entry	light check	set light	new 𝑘	exit	comment
start		ignore	OFF	1	←	1-room sentinel B set; go set sentinel A
1	←	ignore	ON	1	→	sentinel A done; doubles as a 1-room check
1	→	ON	OFF		stop	there's only 1 room; call your boss
1	→	OFF	ON	2	→	sentinel B done; go look for a light to switch off
2	→	OFF	OFF	2	→	light already off; keep looking
2	→	ON	OFF	2	←	found a light to switch off; backtrack to sentinels
2	←	OFF	OFF	2	←	not hit sentinels yet; keep backtracking
2	←	ON	OFF	3	←	hit sentinel B; go check sentinel A
3	←	OFF	OFF		stop	sentinel A was turned off the long way; call your boss
3	←	ON	ON	1	→	false alarm; repeat the procedure.

If we could use an unassigned 𝑘, we can reduce N to 2 by making all the current 𝑘=1 unassigned, and renumbering 𝑘 to take on values from the set {unassigned,1,2}.