Here's a much harder variation. There are three changes:
(1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy.
(2) The prisoners are all given coins, so that they can make random decisions.
(3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room.
(1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy.
(2) The prisoners are all given coins, so that they can make random decisions.
(3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room.
It has a very elegant solution.