I solved it! And it is great!! The infamous "two switches" puzzle does have a solution, and it isn't a trick; it is a pure logic puzzle. Actually it is a great logic puzzle, because after you work out the solution, you discover a little teeny crummy thing that makes the solution not the solution, and then you have to figure out a way around it. Excellent.
So, first, here's the puzzle [ courtesy of techInterview ]:
I actually think this puzzle is too hard to give in a technical interview. Perhaps many of you are thinking "what's he talking about, that puzzle was trivial" (!) But for me this was a three-bike-ride puzzle, and although some candidates might really enjoy puzzling it out, to expect them to figure it out in fifteen minutes is unrealistic. (As we noted before in Moving Mount Fuji, you want to use puzzles which all good candidates can solve, so as to detect bad candidates.)
Okay, on to the solution. First let me give the "correct except for a little teeny crummy thing" solution:
The prisoners get together and nominate one prisoner as the "leader". All the other prisoners are equivalent. The leader is going to count how many different prisoners have visited the switch room. When the count equals the number of prisoners, he goes to the warden and says "all the prisoners have visited", and everyone goes free. Here's the strategy for the followers and the leader:
That's it! Each prisoner will toggle switch A on exactly once. Only the leader can toggle switch A off, and he will count each time he does so. Each time switch A is on it means a different prisoner has toggled it. When the count equals the number of prisoners, you're done!
Make sure you understand my convoluted explanation before going on. Hopefully you will have clear that the switch room holds one state, and how the leader and the followers interact.
A key complication in the puzzle is that the initial state is not known. If the initial state were known - let's say the switches were both off - then there would not be a problem, and we'd be done. But this complication actually means the strategy outlined above won't work exactly right. Here's why. The initial state of switch A can be either off or on. If switch A is off, there is no problem. If a follower visits first, they'll toggle switch A on, and when the leader visits, he'll toggle switch A to off and the count will be one. If the leader visits first he'll do nothing since switch A is already off. All will be cool. But if the initial state of switch A is on, then there's a problem. Nothing will happen until the leader visits, and he'll toggle switch A off and set the count to one. But - his count will be off by one! The leader cannot tell the difference between 'initial state off, one follower visited' and 'initial state on, zero followers visited'. This matters because if the leader is off by one, he'll either wait forever for a last follower who doesn't exist (prisoners remain prisoners), or he'll tell the warden everyone has visited when one prisoner still hasn't (prisoners fed to alligators). So - what to do?
The crux of the complication is that the leader can't know whether the first "switch A on" was created by a follower. So the solution has to be - nobody can do anything until the leader has visited at least once.
The prisoners get together and nominate one prisoner as the "leader". All the other prisoners are equivalent. The leader is going to count how many different prisoners have visited the switch room. When the count equals the number of prisoners, he goes to the warden and says "all the prisoners have visited", and everyone goes free. Here's the strategy for the leader and the followers:
The additions to the strategy are italicized. Each follower must remember two things, 1) whether they've seen switch A on during any previous visit, and 2) whether they've previously toggled switch A. They must have seen switch A on before toggling it on themselves, and they will only toggle it on once. The leader must remember two things also, 1) whether he toggled switch A on during his previous visit, and 2) the current count of followers who have toggled switch A.
To see how this handles the initial state complication, let's consider the possibilities. If the initial state of switch A is off, then nothing will happen until the leader visits, because no follower will have previously seen an on state. If the initial state of switch A is on, then again nothing will happen until the leader visits, because only he can turn switch A off. Since nothing happens until the leader visits, the initial state ambiguity is settled; the leader can be sure that the state of switch A has not been disturbed since the start.
So there you have it - a terrific logic puzzle, with a depth that is belied by the apparent simplicity of the situation. Note that the solution would be the same no matter how many prisoners there were - I don't know if asking the question with 1000 prisoners or n prisoners would have made it easier. (Somehow the number 23 suggests a specific value, doesn't it?)