23 Prisoner Puzzle Solution

The Problem
There are 23 prisoners in a prison. The guard tells them that whenever he wants, at random, as often as he wants, he will take 1 random prisoner to a room where there are 2 switches. Each switch is either on or off. The prisoner must switch one of the switches and then go back to his cell. At any time if a prisoner correctly tells the guard that all 23 of the prisoners have been to that room at least once, then they will all be freed. Any wrong answer will lead them all to death. The prisoners will have a one time meeting together to decide on their strategy before this process starts. Nobody knows the initial state (on or off) of the switches. What should be their strategy to become free?

The Solution Explained
Basically, one prisoner has to be a Leader, who’s only purpose is to turn off Switch B (If it’s on, otherwise just flip Switch A), counting every time that he turns it off. All the other prisoners have only one purpose, if Switch B is turned off, and they haven’t turned it on before… turn it on. Otherwise, just flip the bullshit switch, Switch A. Now, to be safe, one prisoner (other than the leader) should turn the switch on twice in order to counter the fact that Switch B may start ON in the first place. Once the leader has turned off Switch B 23 times,… he can announce safely that all prisoners have been in the room at least once.

In Code, it looks like this.
int main()
{
//Prepare variables
srand((unsigned int)time(0));
bool SwitchA, SwitchB;
SwitchA = SwitchB = false;
int i = 0;

//Make 23 Prisoners
int Prisoner[23] = { 0 };
//Make amount of times all prisoners have visited cell
int PrisonerVisit[23] = {0};
//Number of Visits
int Visits = 0;

//Set the switches to random off or on
if(rand()%2)
{
SwitchA = true;
}
if(rand()%2)
{
SwitchB = true;
}

//While the leader prisoner is less than 23 visits
while(Prisoner[0] < 23 && Prisoner[1] < 2)
{
//Grab the next random prisoner
i = rand()%23;

//He’s going for a visit, increment visits
Visits++;
PrisonerVisit[i]++;

cout << "The guard came around and visited Prisoner number " << i+1 << ".n";

cout << "Prisoner " << i+1 << " switched ";
//If this is the leader
if(i == 0)
{
//If B is on
if(SwitchB)
{
cout << "B!n";
//Turn it off
SwitchB = !SwitchB;
//Count this turn off
Prisoner[i]++;
}
//If B wasn’t on…
else
{
//Just flip A
cout << "A!n";
SwitchA = !SwitchA;
}
}
//If it’s the 2nd guy
else if(i == 1)
{
//If the Switch is off
if(!SwitchB)
{
//And I’ve not switched it enough
if(Prisoner[i] < 2)
{
SwitchB = !SwitchB;
Prisoner[i]++;
}
else
{
SwitchA = !SwitchA;
}
}

}
//Otherwise it’s just some random prisoner
else
{
//If B is off, and I’ve never turned it on
if(!SwitchB && Prisoner[i] == 0)
{
//Turn it on
cout << "B!n";
SwitchB = !SwitchB;

//Mark that I’ve done this
Prisoner[i]++;
}
//Else just flip A
else
{
cout << "A!n";
SwitchA = !SwitchA;
}
}
}

cout << "All Prisoners have visited the room at least once.nn";
for(unsigned int j = 0; j < 23; j++)
{
cout << "Prisoner " << j+1 << " visited the room " << PrisonerVisit[j] << " times.n";
}
cout << "nTotal Number of Visits: " << Visits << " nn";
system(“Pause”);
return 0;
}