El problema de las 8 reinas con Python

Hoy pase un rato intentando hacer un algoritmo para chequear que un tablero con 8 reinas dispuestas en distintos casilleros no se tocaran entre ellas.

Aunque mi solución no es la más ideal ni la más eficiente, funciona. Igual aviso, el codigo es horroroso y se puede mejorar en cualquier aspecto. (El que avisa no traiciona)

Les dejo el codigo y tambien el link para que me dejen comentarios en gist.

valid = [
    # a  b  c  d  e  f  g  h
    [ 0, 0, 0, 0, 0, 1, 0, 0 ], # 1
    [ 1, 0, 0, 0, 0, 0, 0, 0 ], # 2
    [ 0, 0, 0, 0, 1, 0, 0, 0 ], # 3
    [ 0, 1, 0, 0, 0, 0, 0, 0 ], # 4
    [ 0, 0, 0, 0, 0, 0, 0, 1 ], # 5
    [ 0, 0, 1, 0, 0, 0, 0, 0 ], # 6
    [ 0, 0, 0, 0, 0, 0, 1, 0 ], # 7
    [ 0, 0, 0, 1, 0, 0, 0, 0 ]  # 8
]

def is_a_valid_8_queen(board):
    attacked_pos = []
    for row, columns in enumerate(board):
        for column, piece in enumerate(columns):
            if piece == 1:
                if set(attacked_pos).intersection(set([number_to_column(column) + str(row + 1)])):
                    print("Invalid")
                    return False
                attacked_pos += get_queen_attacked_pos(row,column)
    print("Valid")
    return False
            

def number_to_column(number):
    columns = ["a","b","c","d","e","f","g","h"]
    return columns[number]

def get_queen_attacked_pos(row, column):
    return set([number_to_column(column) + str(row + 1)] + \
            get_vertical(column) + \
            get_horizontal(row) + \
            get_main_diagonal(row, column) + \
            get_main_diagonal_back(row, column) + \
            get_anti_diagonal(row, column) + \
            get_anti_diagonal_back(row, column))

def get_vertical(column):
    return [number_to_column(column) + str(row) for row in range(1, 9)] 

def get_horizontal(row):
    return [number_to_column(column) + str(row + 1) for column in range(0,8)]

def get_main_diagonal(row, column):
    column_counter = column
    attacked_pos = []
    for row_number in range(row + 2, 9):
        column_counter += 1
        if column_counter > 7:
            break
        attacked_pos.append(number_to_column(column_counter) + str(row_number))

    return attacked_pos

def get_main_diagonal_back(row, column):
    column_counter = column
    attacked_pos = []
    for row_number in range(row, 0, -1):
        column_counter -= 1
        if column_counter < 0:
            break
        attacked_pos.append(number_to_column(column_counter) + str(row_number))

    return attacked_pos

def get_anti_diagonal(row, column):
    column_counter = column
    attacked_pos = []
    for row_number in range(row + 2, 9):
        column_counter -= 1
        if column_counter < 0:
            break
        attacked_pos.append(number_to_column(column_counter) + str(row_number))

    return attacked_pos

def get_anti_diagonal_back(row, column):
    column_counter = column
    attacked_pos = []
    for row_number in range(row, 0, -1):
        column_counter += 1
        if column_counter > 7:
            break
        attacked_pos.append(number_to_column(column_counter) + str(row_number))

    return attacked_pos

is_a_valid_8_queen(valid)

El enlace a gist: https://gist.github.com/farebord/e262937d4a6195a0e3b32295716aea29


< Atrás