Проверьте недопустимые позиции для проблемы N-Queens с платой, хранящейся в одномерном списке в Python

Question

Я делаю GUI версию проблемы N-Queens с Python. В настоящее время доска хранится в одномерном списке. Я знаю, что мог бы преобразовать одномерный список в двухмерный, используя формулу, подобную grid_2d[i][j] = grid_1d[i * NUM_COLUMNS + j], но я бы лучше нашел способ проверить недопустимые ходы, найдя взаимосвязь в одномерных индексах.

I Я начал с функций, представленных ниже, но я думаю, что, возможно, есть гораздо лучший способ go об этом, который я упускаю. Кроме того, часть проверки диагоналей поставила меня в тупик.

Какие-либо предложения по разумным способам проверки столкновений ферзя в одномерном представлении списка на доске, пожалуйста?

def get_rows(board_size):
    results = []
    for i in range(board_size):
        new_row = []
        for j in range(board_size):
            new_row.append(i * board_size + j)
        results.append(new_row)

    return results

def get_columns(board_size):
    results = []
    for j in range(board_size):
        new_column = []
        for i in range(board_size):
            new_column.append(j + board_size * i)
        results.append(new_column)

    return results


print(get_rows(3)) # [[0, 1, 2], [3, 4, 5], [6, 7, 8]] 
print(get_columns(3)) # [[0, 3, 6], [1, 4, 7], [2, 5, 8]] 

Answer 1

Сначала составьте список всех королев:

lst_queens =[(0, 3), (5,7) ...]

Где первый элемент - строка, а второй - столбец.

Затем составьте список всех строк. / столбцы, которые охватывают королевы, wg:

lst_rows = [i[0] for i in lst_queens]

Все значения должны быть уникальными. То же самое для столбцов.

Для диагоналей, реализуйте либо увеличение строки, либо столбца при перемещении по диагонали, либо увеличение или уменьшение одного. Таким образом, вы можете перечислить все диагонали, используя:

diagonals_1 = [i[0] - i[1] for i in lst_queens]
diagonals_2 = [i[0] + i[1] for i in lst_queens]

И снова, оба списка не должны иметь двойных чисел.