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

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

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

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

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]]

python list n-queens
person Robin Andrews    schedule 10.01.2020    source источник
comment
Гораздо проще, если вы вообще НЕ представляете доску, будь то 1d или 2d. Вместо этого имейте в виду, что ферзь всегда поражает весь ряд, столбец и две диагонали, на которых он находится.   -  person Lagerbaer    schedule 11.01.2020

Ответы (1)


arrow_upward
1
arrow_downward

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

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]

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

person Nathan    schedule 10.01.2020