# Amnesiac in a ring shaped palace

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 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.

• With $N=-\infty$ I have unlimited memory, and nobody will find a smaller $N$.^^ – A. P. Jan 25 '18 at 10:42
• @A.P. Grrr... clarified – boboquack Jan 25 '18 at 10:46
• @PL457 N is not the number of rooms, N is only the number you can remember. The number of rooms is some other unnamed integer. – ffao Jan 25 '18 at 13:03
• In other words, can a Turing machine running on a cyclic tape of unknown length clear its tape? – Henning Makholm Jan 25 '18 at 16:45
• One more information leak to plug: You can encode information into your position, clothing or physical injury. Like "1 for crawling, 2 for standing with a bruise in left arm, 3 for silly crab walk in underpants". Because I love the skit, may I suggest that the silly walks be explicitly allowed, but any instructions as to interpreting their meaning is scrubbed away from the plan by the Monty Python members as you go through the first door? – Bass Jan 26 '18 at 10:51

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.

• I haven't had the chance to run through all the scenarios yet, in particular all possible 1, 2, and 3 room combinations. Please let me know if my state machine fails. – ajee Jan 27 '18 at 3:44
• So you took the greedy start option, integrated the 1-room special case to the initialisation, and got rid of the other initialisation step by choosing the initialisation so that it became unnecessary. I had convinced me that all of those things were at least mutually exclusive. This is pure brilliance. – Bass Jan 27 '18 at 7:53
• For anyone else trying to decipher the method, it starts in the leftmost room and, after an ingenious initialisation step, looks for the next lit room towards the right, switches it off, and comes back to check if the starting room light is still on. States ”start”, ”A L on” and ”A L off” occur in the starting room, states ”A R on”, ”A R off” and ”B L on” occur in the next room to the right. ”B R on” switches off the next light found. The other ”B” states walk through the chain of darkened rooms between the second room and the next lit room to the right. – Bass Jan 27 '18 at 8:09
• This answer can also be converted into a four state solution for the ”can’t tell which door I just used” version OP intended. – Bass Jan 27 '18 at 8:15
• Yep, that's equivalent to my 4 state solution (encoding the movement direction in the state). It works for ≥1 rooms. – ens Jan 28 '18 at 12:55

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.

• No, you start in the middle room, turn on, set $k=1$, then go left. – hexomino Jan 25 '18 at 12:55
• In the second room $k=1$, so you leave the light ON and set $k=2$ and go left again. – hexomino Jan 25 '18 at 12:56
• You may have a problem if room number is equal to 1! – Untitpoi Jan 25 '18 at 12:59
• Ooh, I get it now, just use a completely empty pattern instead of my stupid overcomplicated mess. – ffao Jan 25 '18 at 13:01
• @Untitpoi, yes you are right. I didn't read the question properly and had assumed this case was ruled out. I might have to rethink and edit. – hexomino Jan 25 '18 at 13:03

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 $k=1$. Then repeat the following procedure based on the value of $k$ until the plan says to stop. Upon entering any room, check the light. If there are two lines for your $k$, pick based on the light check. Switch the light ON or OFF according to the switch to field, set $k$ 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$.

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

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.

• Note: You can keep track of whether you are going clockwise/anticlockwise by the painting of the walls, if this helps – boboquack Jan 25 '18 at 22:01
• @boboquack I couldn't work that out - from the wording, it sounded like the rooms were painted one colour inside and the outside (the corridor) was another colour - so you could tell whether you were walking into or out of the room. I also assumed all the rooms were on one side of the corridor. I'll edit. – Lawrence Jan 26 '18 at 3:39
• Well done on this answer. I completely got tripped up by the one room case. – hexomino Jan 26 '18 at 10:46
• @boboquack hmm, that re-write of the question makes things a little more interesting. There's a new piece of information: the entry door, and hence the direction of travel prior to the last episode of amnesia. Can we use this information in our answers? (I had previously assumed that there's a corridor, and just one door into each room. You go out of the room into the corridor, then go into the next room from the corridor, at which point you don't know which side visited last. Now I understand that you do.) – Lawrence Jan 26 '18 at 11:18
• @Untitpoi The guy's got some strange amnesia, though, so he might forget to keep his arm up, or what it's up for :) . I think anything that's used as a counter will need to be folded back into $k$ (or $N$). – Lawrence Jan 26 '18 at 15:53

[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:

• Note: You can keep track of whether you are going clockwise/anticlockwise by the painting of the walls, if this helps – boboquack Jan 25 '18 at 22:02

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.

• This seems to me like you're sneaking some extra information into 'back' and 'forward' which I would argue is part of your memory (i.e, you need to remember whether you came into a room backward or forward). To give an example, instead of using 2 or 3 you could raise your right or left hand before entering a room and then continue depending on whether your left or right hand was raised when you entered, thereby reducing to $N=1$. – hexomino Jan 26 '18 at 10:53
• @hexomino See boboquack's comment on Lawrence's answer; using which direction you're travelling in as a marker of state is definitely legit. – BlueHairedMeerkat Jan 26 '18 at 11:04
• @BlueHairedMeerkat My interpretation of this was that you know which door will next bring you clockwise/anticlockwise based on how the walls are painted. I don't think it necessarily follows that you remember which door you came through or in what direction. However, it is ambiguous. – hexomino Jan 26 '18 at 11:15
• @hexomino, Even though I hadn't noticed the comment BlueHairedMeerkat pointed out, I don't think it's any kind of memory; I obtain that information in the room, after the mind scrub, by checking the colour of the walls. This must be legit, since any way of identifying the "inside" and "outside" walls also automatically identifies the doors, no matter how mnemonically challenged the observer. – Bass Jan 26 '18 at 11:15
• @Lawrence I totally stole the clever initialisation step from your earlier answer, so it's only fair that you should post the full solution from my answer :-) By the way, in case our door-identifying stratagems are deemed OP by the OP, I think the minimality "proving" mumbo jumbo can be used to show that your earlier answer is optimal. – Bass Jan 26 '18 at 12:53

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 '$\rightarrow$' and counterclockwise travel '$\leftarrow$'. 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.

\begin{array}{c|c|c|c|c|c|l} \text{old $k$} & \text{entry} & \text{light check} & \text{set light} & \text{new $k$} & \text{exit} & \text{comment} \\ \hline \text{start} & & \text{ignore} & OFF & 1 & \leftarrow & \text{1-room sentinel B set; go set sentinel A} \\ 1 & \leftarrow & \text{ignore} & ON & 1 & \rightarrow & \text{sentinel A done; doubles as a 1-room check} \\ 1 & \rightarrow & ON & OFF & & \text{stop} & \text{there's only 1 room; call your boss} \\ 1 & \rightarrow & OFF & ON & 2 & \rightarrow & \text{sentinel B done; go look for a light to switch off} \\ 2 & \rightarrow & OFF & OFF & 2 & \rightarrow & \text{light already off; keep looking} \\ 2 & \rightarrow & ON & OFF & 2 & \leftarrow & \text{found a light to switch off; backtrack to sentinels} \\ 2 & \leftarrow & OFF & OFF & 2 & \leftarrow & \text{not hit sentinels yet; keep backtracking} \\ 2 & \leftarrow & ON & OFF & 3 & \leftarrow & \text{hit sentinel B; go check sentinel A} \\ 3 & \leftarrow & OFF & OFF & & \text{stop} & \text{sentinel A was turned off the long way; call your boss} \\ 3 & \leftarrow & ON & ON & 1 & \rightarrow & \text{false alarm; repeat the procedure.} \end{array}

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

• I don't know if you read our discussion under the answer given by @Bass (which is along the same lines) but I am not satisfied that the entry information should be included. However, I do concede that there is some ambiguity here. Personally, I much prefer your $N=5$ because $k$ is the only thing we depend on. These newer answers seem to suggest a trick question. – hexomino Jan 26 '18 at 13:45
• @hexomino Yes, I'm with you on this. I only saw Bass's answer (and your discussion in comments there) after posting this. I also thought this line of reasoning was moving to a degenerate solution, so didn't want to muddy the $N=5$ answer. It feels like with a little tweaking, we can get rid of dependence on $k$ (or $N$) altogether - and I don't think that's what the question is trying to achieve. As it is, $N=2$ is pretty close to my (now deleted) cheeky initial comment to the question of $N=1$, when it wasn't yet made clear that 'proof not necessary' applied only to $N$ being minimal. :) – Lawrence Jan 26 '18 at 14:26

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.
• When you don't specify movement, I assume you mean "continue moving in the same direction as before"? – Deusovi Jan 27 '18 at 8:56
• You assume correctly. But it would be better if I was more specific, thanks! Edit: edited. – Lemma Jan 27 '18 at 8:57
• Oh, also - welcome to Puzzling! :D – Deusovi Jan 27 '18 at 8:59
• It seems as though this won't work for the case where there is just one room. – hexomino Jan 27 '18 at 9:17
• Now this is identical to ajee's answer with k=2 instead of A and k=1 instead of B, and clockwise instead of L and counterclockwise instead of R. – boboquack Jan 27 '18 at 9:53