Puzzle

Prisoner and othello board

Reference:

• https://www.youtube.com/watch?v=1_tJbkG_ckE
• https://www.cantorsparadise.com/a-fascinating-prisoners-puzzle-be874032f43e

#!/usr/bin/python3

# Problem:
#
# Two prisoners are given the chance to be free if they can solve the following problem.
#
# The guardian takes the first prisoner to a room where there is a 8x8 chess board.
# On the board, there are 64 tokens that are white on one side and black on the other side.
# The tokens are flipped at random with no apparent pattern.
# The guardian chooses one of the cell, and hide the prison key in the cell (say in some hidden compartment under the cell).
# The guardian says that the 2nd prisoner will have to guess where the key is hidden by looking at the board.
# The only thing that the 1st prisoner can (and must) do is to flip one of the 64 tokens on the board.
# What strategy the prisoners must follow in order to guarantee that the 2nd prisoner finds the key?
# We assume that the prisoner were aware of the problem of the guardian and could have agreed on a given strategy beforehand.
#
# Solution:
# * We split the problem into 2 sub-problems: find which row and find which column.
# * To find the row, we use the parity of the columns. To find the colum, we use the parity of the rows.
# * The parity of a column is given by the number of (say) white token. 
#   If this number is odd, parity of the column is odd, and even otherwise.
# * By flipping a token, the prisoner can flip independently the parity of one column, and of one row.
# * Prisoner will use these column (resp. row) parities to encode the index of the row (resp. colum):
#   * Prisoner sets index to 0.
#   * Prisoner looks at first column.   If the parity is odd, the prisoner compute index ^= 0b001 (binary notation)
#   * Prisoner looks at second column.  If the parity is odd, the prisoner compute index ^= 0b010 (binary notation)
#   * Prisoner looks at third column.   If the parity is odd, the prisoner compute index ^= 0b100 (binary notation)
#   * Prisoner looks at fourth column.  If the parity is odd, the prisoner compute index ^= 0b011 (binary notation)
#   * Prisoner looks at fifth column.   If the parity is odd, the prisoner compute index ^= 0b101 (binary notation)
#   * Prisoner looks at sixth column.   If the parity is odd, the prisoner compute index ^= 0b110 (binary notation)
#   * Prisoner looks at seventh column. If the parity is odd, the prisoner compute index ^= 0b111 (binary notation)
#   * Prisoner ignores the eighth column.
# * To communicate the index of the secret cell, the prisoner computes the index given the current parities.
#   * If the index is correct, prisoner will flip the parity of the eighth column.
#   * Otherwise, by construction, there is one and only one column that must be flipped in order to obtain the correct parity.
#     This is because the current index and the desired index differ by either one bit (one of the column 1 to 3 must be flipped), 
#     or two bits (column 4 to 6 must be flipped) or three bits (column 7 must be flipped).

def eval(parities):
    "Return the value from an array of 8 parities"
    value = 0
    if parities & 1 != 0:
        value ^= 1 # toggle 001
    if parities & 2 != 0:
        value ^= 2 # toggle 010
    if parities & 4 != 0:
        value ^= 4 # toggle 100
    if parities & 8 != 0:
        value ^= 3 # toggle 011
    if parities & 16 != 0:
        value ^= 5 # toggle 101
    if parities & 32 != 0:
        value ^= 6 # toggle 110
    if parities & 64 != 0:
        value ^= 7 # toggle 111
    # last parity, 128, toggles nothing
    return value

def flip(parity,bit_idx):
    "Flip a bit in the given parity"
    assert((bit_idx >= 0) and (bit_idx < 8))
    return parity ^ (2 ** bit_idx)

def find_flip(parity,value):
    "Find which bit in the parity must be flipped to get value"
    assert((value >= 0) and (value < 8))
    current = eval(parity)
    if current ^ value == 1:
        return 0
    if current ^ value == 2:
        return 1
    if current ^ value == 4:
        return 2
    if current ^ value == 2+1:
        return 3
    if current ^ value == 4+1:
        return 4
    if current ^ value == 4+2:
        return 5
    if current ^ value == 4+2+1:
        return 6
    assert(current == value)
    return 7

for parity in range(256):
    for value in range(8):
        bit_idx = find_flip(parity,value)
        new_parity = flip(parity,bit_idx)
        if eval(new_parity) != value:
            print(f"Wrong flip for parity {parity} value {value} bit_idx {bit_idx} new_parity {new_parity} new_value {eval(new_parity)}")
            assert(eval(new_parity) == value)

print("We are FREE!")