Python progam to solve the devil's chessboard problem

devils-chessboard.py

import math
import random


def main():
    board_size_power = 6
    board_size = int(math.pow(2, board_size_power))
    initial_board = []

    # generate a random board
    for i in range(board_size):
        initial_board.append(bool(random.getrandbits(1)))

    # generate a random magic square
    devils_square = random.randint(0, board_size - 1)

    print "devil's square:"
    print devils_square

    print "initial board:"
    print_board(initial_board, board_size_power)

    print "magic square of initial board:"
    print get_magic_square(initial_board)

    # player 1 views the board and flips a single bit
    new_board = flip_bit(initial_board, devils_square)

    print "new board:"
    print_board(new_board, board_size_power)

    # player 2 figures out the magic square from the new board
    print "magic square of new board:"
    print get_magic_square(new_board)


# given a board, work out the magic square it signifies
def get_magic_square(board):
    result = 0
    for i in range(len(board)):
        if board[i]:
            result ^= i
    return result


# given a board and the devil's magic square, flip a bit such that the new
# board signifies the magic square
def flip_bit(board, magic_square):
    bit_to_flip = get_magic_square(board) ^ magic_square
    board[bit_to_flip] = not board[bit_to_flip]
    return board


# prints the board
def print_board(board, board_size_power):
    # check if the board is square or rectangular
    # e.g. a 4 * 8 board of 32 squares is rectangular
    if board_size_power % 2 == 0:  # board is square
        width = height = int(math.sqrt(len(board)))
    else:  # board is rectangular
        height = int(2**(board_size_power / 2))
        width = int(len(board) / height)

    for i in range(height):
        line = ""
        for j in range(width):
            if board[i * width + j]:
                line += "O"
            else:
                line += "X"
        print line


if __name__ == "__main__":
    main()