gistfile1.txt

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15|
  ----------------------------------------------|
     0  0     0           0                     | 0
  1        1     1           1                  | 0
  2        2        2           2               |   1
     3  3              3           3            |   1
  4              4  4                 4         |     2
     5        5        5                 5      |     2
        6     6        6                    6   |        3
           7     7  7                          7|        3
  8                          8  8     8         |        3
     9                    9        9     9      |        3
       10                10       10       10   |     2
          11                11 11             11|     2
             12          12             12 12   |   1
                13          13       13       13|   1
                   14          14    14       14| 0
                      15          15    15 15   | 0

gistfile2.txt

# Implementing chessboard prisoner puzzle

# generate_table() below generates pictures
# beware: these quickly become big

import math
import sys
import random

length = 8
board_size = length**2

def generate_chessboard():
  return random.getrandbits(board_size)

def generate_magic_square():
  return random.getrandbits(math.frexp(board_size-1)[1])

def print_chessboard(board):
  for line in [format(board, '0' + str(board_size) + 'b')[j:j+length]
               for j in range(0, board_size, length)]:
    print '-' * (length*4 + 1)
    print '| ' + ' | '.join(list(line)) + ' |'
  print '-' * (length*4 + 1)

def h(board):
  result = 0
  for j in range(board_size):
    if (1 << j) & board:
      result ^= j
  return result

def flip_coin(board, coin):
  return board ^ (1 << coin)

def first_prisoner(board, magic_square):
  return h(board) ^ magic_square

def second_prisoner(board):
  return h(board)

def generate_table(x_cutoff=32, y_cutoff=512):
  if board_size > 2**4:
    raise Exception("That's gonna become too big")

  size = 2**board_size
  x_cutoff_size = min(x_cutoff, size)

  for j in range(x_cutoff_size):
    sys.stdout.write(format(j, '3'))
  sys.stdout.write("|\n")
  sys.stdout.write('-'*3*x_cutoff_size + "|\n")

  for k in range(min(size, y_cutoff)):
    flips = [flip_coin(k, coin) for coin in range(size)]
    for j in range(x_cutoff_size):
      if j in flips:
        sys.stdout.write(format(k, '3'))
      else:
        sys.stdout.write('   ')
    sys.stdout.write("|")
    guess = h(flips[-1])
    sys.stdout.write(" "*2*guess + format(guess, '2') + "\n")


def run():
  #generate_table()
  #return

  board = generate_chessboard()
  print ("""First prisoner sees board {0}
  (in binary: {0:0{board_size}b})""").format(board, board_size=board_size)
  print_chessboard(board)

  print "h(board) =", h(board)

  magic_square = generate_magic_square()
  print "Magic square is {0}".format(magic_square)

  coin = first_prisoner(board, magic_square)
  print "First prisoner chooses coin", coin

  print "\n * * * \n"

  new_board = flip_coin(board, coin)
  print ("""First prisoner sees board {0}
  (in binary: {0:0{board_size}b})""").format(new_board, board_size=board_size)
  print_chessboard(new_board)
  print "Second prisioner guesses magic square", second_prisoner(new_board)

  if magic_square == second_prisoner(new_board):
    print "And they survive!"
  else:
    print "And both die."

if __name__ == '__main__':
  run()

Oliver Nash about this problem: http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle/ (includes rings and modules! <3)