The 100 prisoners puzzle

#!/usr/bin/env python
import itertools

# The 100 prisoners problem statement:
#
# The warden places 100 numbers in 100 boxes, at random - with equal
# probability that any number will be in any box. Each convict is assigned
# a number. One by one they enter the room with the boxes, and try to find
# their corresponding number. They can open up to 50 different boxes. Once
# they either find their number or fail, they move on to a different room
# and all of the boxes are returned to exactly how they were before the
# prisoner entered the room.  The prisoners can communicate with each
# other before the game begins, but as soon as it starts they have no way
# to signal to each other. The warden is requiring that all 100 prisoners
# find their numbers!
#
# At first glance, since each of them has 50% chance (0.5), the probability
# of all of them succeeding is (0.5)^100 = .... zero.
#
# And yet, with the approach described below, the chance of success
# (i.e. ALL of them finding their number) is 31.2% !!!
#
# In fact, for N prisoners, with N=2*k, the probability of success is:
#
#            p(success) = 1-(1/M + 1/(M+1) + ... + (1/N))
# where
#            M = N/2 + 1        
#
# So, for N=8:   1-(1/5+1/6+1/7+1/8)      = .36547619047
#     for N=10:  1-(1/6+1/7+1/8+1/9+1/10) = .35436507936
#     for N=100: 1-(1/51+1/52+...+ 1/100) = .31182782069
#
# Brilliant description of the puzzle's solution here:
#   http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf

def CheckSolution(prisoners, perm):
    for i in xrange(prisoners):
	attempt = 0
	idx = i
	found = False
	while attempt < prisoners/2: # You have N/2 attempts...
	    if perm[idx] == i:  # Look in your box...
		found = True    # you found your number, great!
		break
	    else:
		idx = perm[idx] # else "seek" to the number inside the box
	    attempt += 1
	if not found:
	    return False # This permutation failed, it had a cycle>N/2
    return True # This permutation was a good one...
		
def main():
    for prisoners in xrange(4, 12, 2): # Do the experiment for 4,6,8,10
	total = 0
	success = 0
	for perm in itertools.permutations(xrange(prisoners)):
	    total += 1
	    if CheckSolution(prisoners, perm):
		success += 1
	print "When", prisoners,"prisoners,",
	print "Saved:", success, "/", total,
	print "(%5.2f)" % (100.0*success/total)

if __name__ == "__main__":
    main()