Объяснение решения Python N-Queen

Question

Я рассматривал это действительно изящное решение проблемы n-queen из раздела «Элементы программирования», глава «Динамическое программирование», но, похоже, не понимаю какой-то конкретный фрагмент кода. Если кто-то может объяснить логику здесь, это было бы очень полезно. Если условие проверки конфликтов - это то, что я пытаюсь обернуть здесь, но безуспешно.

def n_queens(n: int) -> List[List[int]]:
    def solve_n_queens(row):
        if row == n:
            # All queens are legally placed.
            result.append(col_placement.copy())
            return
        for col in range(n):
            # Test if a newly place queen will conflict any earlier queens place before
            # I am struggling to make sense of this if condition
            if all(abs(c - col) not in (0, row - i)
                   for i, c in enumerate(col_placement[:row])):
                   col_placement[row] = col
                   solve_n_queens(row + 1)

    result: List[List[int]] = []
    col_placement = [0] * n
    solve_n_queens(0)
    return result

Answer 1

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

Поэтому длядля проверки конфликтов есть только три направления: вверх в том же столбце, по диагонали вверх и влево и по диагонали вверх и вправо.

Условие all(abs(c - col) not in (0, row - i)) проверяет это друг для другакоролева на доске до сих пор. Числа i, c представляют вертикальное и горизонтальное положение каждой королевы соответственно;row, col представляет положение королевы, которая в настоящее время проверяется на наличие конфликтов.

• Конфликт в том же столбце означает c - col == 0.
• Конфликт по диагонали вверх и влево означаетc - col == i - row.
• Конфликт по диагонали вверх и вправо означает c - col == row - i.

Все три из них можно проверить сразу, взяв c - col и проверив,является одним из трех чисел (0, i - row, row - i). Используя функцию абсолютного значения, это эквивалентно проверке, если abs(c - col) является одним из двух неотрицательных чисел (0, row - i).