N-Queens II

Q: Какова временная сложность задачи N-Queens II?

Перебор с возвратом ограничен сверху величиной O(n!) : для первой строки есть n вариантов, для следующей — не более n-1 и так далее. Отсечение значительно сокращает фактический объём работы — до 856,189 частично заполненных досок при n = 12 . Объём используемой памяти составляет O(n) .

СложноПоиск с возвратом

+10

Ферзь атакует все клетки в своей строке, своём столбце и на обеих диагоналях независимо от расстояния. Для заданного целого числа n верните количество способов разместить n ферзей на доске n × n так, чтобы ни один ферзь не атаковал другого.

Доски, отличающиеся расположением хотя бы в одной клетке, считаются отдельно; зеркальные отражения тоже.

Функция

totalNQueens(n: integer) → integer

ninteger: размер доски и количество ферзей
Возвращаетinteger: количество способов расставить ферзей так, чтобы ни один не атаковал другого

Ограничения

1 ≤ n ≤ 12
Ответ для n = 12 — 14,200, поэтому оно помещается в 32-битное целое число.

Примеры

Ввод: n = 4
Вывод: 2
Пояснение: Если записать столбец ферзя в каждой строке сверху вниз, получатся доски 1, 3, 0, 2 и 2, 0, 3, 1: зеркальные отражения друг друга, считающиеся двумя решениями. При любом другом выборе два ферзя окажутся в одном столбце или на одной диагонали.

Дополнительный вопрос

Можешь посчитать только те расстановки, которые не переходят друг в друга при повороте или отражении доски? Для n = 8 92 расстановки образуют 12 таких групп.

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Две ферзя в одной строке всегда атакуют друг друга, поэтому на доске должен быть один столбец на строку: n^n списков — примерно 8.9 × 10^12 при n = 12. Вместо этого стройте доску построчно, отбрасывайте частичную доску сразу, как только ферзя оказывается под атакой, и отмечайте занятые столбцы и диагонали, чтобы проверка клетки требовала трёх обращений.

Попробуй все варианты размещения, по одной ферзю в каждой строке

Верно, но не успевает на самых больших тестах

Идея

Задай расстановку в виде списка cols, где для каждой строки указана колонка с ферзём, и перебери все n^n списков, как на счётчике. Ферзи в строках i < j атакуют друг друга, когда cols[i] == cols[j] или |cols[i] - cols[j]| == j - i, поскольку диагональ смещается на одну колонку на каждую строку. Каждый список проверяется один раз, поэтому ни одна доска не будет пропущена или посчитана дважды.

Перебор никогда не останавливается раньше времени: даже если ферзи в первых двух строках бьют друг друга, остаётся n^(n-2) списков. Для n = 8 это 16,777,216 списков для 92 досок; для n = 12 — 8.9 × 10^12, то есть около 2.5 часа при одной наносекунде на список.

Алгоритм

Начни с того, что все значения в cols равны нулю.
Увеличивай счётчик на 1, если нет пары строк i < j, для которой выполняется cols[i] == cols[j] или |cols[i] - cols[j]| == j - i.
Продвигайся, как в счётчике: начиная с последней строки и двигаясь вверх, сбрасывай каждую запись, равную n-1, до 0, затем увеличивай на 1 первую запись, меньшую n-1.
Остановись и верни счётчик, когда каждая запись станет равна n-1.

def totalNQueens(n):
    def is_valid(cols):
        # cols[r] is the column of the queen in row r, so rows never clash.
        for i in range(n):
            for j in range(i + 1, n):
                if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
                    return False
        return True

    cols = [0] * n
    count = 0
    while True:
        if is_valid(cols):
            count += 1
        # Move to the next placement, like an odometer with n digits in base n.
        row = n - 1
        while row >= 0 and cols[row] == n - 1:
            cols[row] = 0
            row -= 1
        if row < 0:
            return count
        cols[row] += 1

Поиск с возвратом с использованием множеств столбцов и диагоналей

Идея

Размещай ферзей по строкам и проверяй каждого сразу после размещения. Заполнение нижних строк не спасёт атакованного ферзя, поэтому пропусти эту клетку. Если ферзь в безопасности, рекурсивно переходи к следующей строке и убирай ферзя после возврата из вызова; достижение строки n засчитывается как одна доска.

Клетку (row, c) могут атаковать только три линии: её столбец, диагональ /, где row + c — константа, и диагональ \, где row - c — константа (прибавь n-1, чтобы индексировать её, начиная с 0). Массивы флагов cols, diag и anti превращают проверку безопасности в три обращения. На каждой линии находится не более одного ферзя, поэтому сброс флагов при возврате точно восстанавливает массивы.

В строке k доступно не более n - k столбцов, поэтому поиск ограничен сложностью O(n!) и требует O(n) памяти.

Алгоритм

Создай массивы флагов cols размером n и diag и anti размером 2n-1, изначально выключенные.
place(row): если row == n, верни 1.
Для каждого столбца c пропусти его, если cols[c], diag[row + c] или anti[row - c + n - 1] включен.
Иначе включи три флага, прибавь place(row + 1) к общему числу и выключи их.
Верни общее число. Ответ — place(0).

def totalNQueens(n):
    cols = [False] * n             # cols[c]: column c holds a queen
    diag = [False] * (2 * n - 1)   # diag[r + c]: that / diagonal holds a queen
    anti = [False] * (2 * n - 1)   # anti[r - c + n - 1]: that \ diagonal holds a queen

    def place(row):
        if row == n:
            return 1  # a queen in every row: one complete board
        count = 0
        for c in range(n):
            if cols[c] or diag[row + c] or anti[row - c + n - 1]:
                continue  # attacked: three lookups, no scan of the board
            cols[c] = diag[row + c] = anti[row - c + n - 1] = True
            count += place(row + 1)
            cols[c] = diag[row + c] = anti[row - c + n - 1] = False  # take it back
        return count

    return place(0)

Возврат с помощью битовых масок

Идея

Поиск с флагами по-прежнему проверяет все n столбцов каждой строки; битовые маски сразу переходят к свободным. Бит c соответствует столбцу c заполняемой строки: cols содержит занятые столбцы, а left и right — клетки, атакуемые по каждой диагонали. Затем free = ~(cols | left | right) & full, где full — младшие n битов, а free & -free — самая младшая свободная клетка. В следующей строке столбец остаётся занятым, а атака каждой диагонали смещается на один столбец.

При n = 4 и первой ферзе на bit = 0010 в строке 1 получаем free = 1000: столбец 3 найден без проверки остальных. При n = 12 856,188 шагов цикла заменяют 10,103,868 проверок клеток. Код R за раз строит целую строку частичных досок, а не использует рекурсию.

Алгоритм

Установите full = (1 << n) - 1.
count(cols, left, right): если cols == full, верните 1.
Вычислите free = ~(cols | left | right) & full.
Пока free не равен 0, возьмите bit = free & -free, удалите его из free и добавьте count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) к общей сумме.
Верните общую сумму. Ответ — count(0, 0, 0).

def totalNQueens(n):
    full = (1 << n) - 1  # bit c stands for column c of the current row

    def count(cols, left, right):
        # cols: columns taken. left, right: squares of this row hit along a diagonal.
        if cols == full:
            return 1  # every column used: n queens placed
        total = 0
        free = full & ~(cols | left | right)
        while free:
            bit = free & -free  # the lowest free square
            free -= bit
            # Moving down a row shifts each diagonal attack one column over.
            total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
        return total

    return count(0, 0, 0)

Ловушки и крайние случаи

Индексация anti с помощью row - c без добавления n-1. Java выбрасывает исключение, C читает за пределами массива, а Python с помощью anti[-2] незаметно читает флаг другой диагонали.
Задание размера диагональных массивов равным n вместо 2n-1. Значение row + c достигает 2n-2.
Не сбрасывать флаги после рекурсивного вызова. В последующих ветвях остаются ферзи, которых уже нет, и счётчик уменьшается.
Не добавлять & full в free. ~x устанавливает биты выше столбца n-1, поэтому цикл выбирает клетки за пределами доски; в Python или Ruby free становится отрицательным, и цикл никогда не заканчивается.

Частые вопросы3

Какова временная сложность задачи N-Queens II?

Перебор с возвратом ограничен сверху величиной O(n!): для первой строки есть n вариантов, для следующей — не более n-1 и так далее. Отсечение значительно сокращает фактический объём работы — до 856,189 частично заполненных досок при n = 12. Объём используемой памяти составляет O(n).

В чем разница между N-Queens и N-Queens II?

N-Queens возвращает все доски, изображённые в виде строк текста; N-Queens II возвращает только их количество. Поиск тот же, но при подсчёте доски не сохраняются, что хорошо подходит для версии с битовой маской.

Можно ли использовать симметрию, чтобы ускорить решение задачи «Задача о N ферзях II»?

Отражение доски слева направо даёт другую допустимую доску, поэтому посчитай доски, у которых первый ферзь находится в столбцах с 0 по n/2 - 1, и удвой это количество. Для нечётного n один раз добавь доски, у которых первый ферзь находится в среднем столбце.

def totalNQueens(n):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

n = 4

Ожидаемый вывод

N-Queens II

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй все варианты размещения, по одной ферзю в каждой строке

Поиск с возвратом с использованием множеств столбцов и диагоналей

Возврат с помощью битовых масок

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи