Fisher Random starting positions

fisher_random.py

"""Generate and validate starting positions for Fischer Random Chess,
also known as Chess960. Fischer Random Chess is a variant of
traditional chess invented by the former World Chess Champion Bobby
Fischer. It was introduced to add variety to the game and reduce the
reliance on opening memorization by randomly shuffling the positions
of the back-row pieces (rooks, knights, bishops, queen, and king)
while adhering to certain rules to ensure the game remains balanced
and playable.

Fischer Random Chess follows these specific rules for setting up the
back row:

1) Bishops must be placed on opposite-colored squares. This rule
ensures that each player has one bishop that moves on white squares
and one that moves on black squares.

2) The King must be placed on a square between the two rooks. This
setup is crucial for enabling the possibility of castling on either
side of the board.

3) All pieces are placed on the back row (the 1st row for White and
the 8th row for Black), with the pawns placed on the row in front of
them, just like in traditional chess.
"""

def heap_permutation(data, length):
    """
    Generates all permutations of a given list `data` using Heap's algorithm.
    """
    
    if length == 1:
        yield ''.join(data)
    else:
        for i in range(length):
            yield from heap_permutation(data, length - 1)
            if length % 2 == 1:
                data[0], data[length - 1] = data[length - 1], data[0]
            else:
                data[i], data[length - 1] = data[length - 1], data[i]

def is_valid_permutation(perm):
    """
    Determines if a given permutation of chess pieces is a valid starting 
    arrangement for Fischer Random Chess. The rules for validity include:
    - The bishops ('B') must be placed on opposite-colored squares.
    - The king ('K') must be placed on a square between the rooks ('R').
    """
    
    try:
        k_index = perm.index('K')
        r_indices = [i for i, letter in enumerate(perm) if letter == 'R']
        k_between_rs = r_indices[0] < k_index < r_indices[-1] if r_indices else False

        b_indices = [i for i, letter in enumerate(perm) if letter == 'B']
        b_positions_valid = len(b_indices) == 2 and b_indices[0] % 2 != b_indices[1] % 2

        return k_between_rs and b_positions_valid
    except ValueError:
        return False

def filter_permutations(word):
    """
    Filters permutations of chess pieces to find all valid Fischer 
    Random Chess starting arrangements.
    """
    
    all_permutations = set(heap_permutation(list(word), len(word)))
    valid_permutations = filter(is_valid_permutation, all_permutations)
    
    return list(valid_permutations)

# Find and count all legal Fischer Random Chess starting positions
classic_starting_position = 'RNBQKBNR'

valid_permutations = filter_permutations(classic_starting_position)
print(f"Number of valid Fischer Random Chess starting positions: {len(valid_permutations)}")