4by12

Prisoners’ Escape - The Solution

(you can find the original riddle here)

Let’s begin with a draft solution, one that doesn’t work but will start us in the right direction. And to keep things simple, let’s say all the tasks are done the minute the prisoners leave the meeting, so all they have left is to notify someone that they’re done.

Prisoner 1 is responsible for telling the guard once all the tasks are complete. We’ll call him the Leader. He keeps a counter called ‘num_done‘ which starts at 1 (denoting that prisoner 1 himself is done). When the leader enters the room, this is what he does:

if light is on:
    num_done = num_done + 1
    turn light off
else:
    do nothing
-

When any other prisoner enters the room, this is what he does:

if light is off and not turned_light_on:
    turn light on
    turned_light_on = true
else:
    do nothing
-

And each such prisoner maintains a flag called turned_light_on, initialized to ‘false’.

At the end of this, num_done should show the number of prisoners whose task is complete. And when num_done = n, prisoner 1 will notify the guard.

The problem is that this algorithm has an off-by-one error. If the light was originally on before any prisoner entered the room, then when the leader enters the room he will count that on-light as one prisoner. Therefore he’ll reach a count of n while only (n-1) prisoners reported in.

To solve this problem we need to modify the algorithm a bit, to handle the possible initial states of the light switch. We want to give the leader a chance to see the initial state before anyone else touches it. So the other prisoners start by doing nothing, until they get some sort of signal from the leader. This signal will be ‘flicking the switch’: They first want to see the light turned on, and then, when the time is right, they will turn it on themselves.

So now, each prisoner other than the leader maintains another flag called saw_light_on, which starts as ‘false’. The algorithm is:

if light is on:
    saw_light_on = true
else if saw_light_on and not turned_light_on:
    // light is OFF
    turn light on
    turned_light_on = true
else:
    do nothing
-

Next, the leader maintains an extra flag: saw_initial_state initialized to ‘false’. Her algorithm is:

if saw_initial_state:
	if light is on:
	    turn light off
	    num_done = num_done + 1
	else
	    // flick the switch to signal the others
	    turn light on
	    num_done = num_done - 1
else:
	// This is the first time the leader enters the room
	turn light off (if it's on)
	saw_initial_state = true
-

Note that the leader needs to continue flicking the switch forever. Otherwise, latecomers will never turn the light on. Also note that the leader must discount for his own flicking by decrementing num_done. Finally, as before, when num_done = n, the leader notifies the guard and the prisoners escape. There you have it!