N-королів: Як згортка обрізає експоненційний пошук

Невеличка, але хитра задача

Розмістіть N королевих на шахівниці розміром N×N так, щоб жодні дві не ділили одну лінію, стовпчик або діагональ. Для N=8 найбільш очевидний підхід – спробувати всі можливі способи розміщення 8 королевих серед 64 квадратів – це C(64,8), більше ніж 4 мільярди комбінацій. Обмежуючи одну королівку на рядок і стовпчик (королева атакує вздовж обох, тому жодне допустиме рішення не може повторюватися ні в якому з цих параметрів), це зменшується до 8! = 40320 перестановок, але вам все ще потрібно перевірити кожну з них на наявність діагональних конфліктів, якщо ви не шукаєте розумніше.

Зворотне відстеження: будуємо, перевіряємо, скасовуємо

Зворотне відстеження розміщує королевих по черзі, рядок за рядком, і відмовляється від часткової розкладки, як тільки стає неможливим продовжити її — ще до того, як усі N королеви будуть розміщені. Це суть: поступове побудови з раннім відхиленням, що перетворює експоненційне грубе брутфорсівське пошукування на те, що завершується за мілісекунди для N=8.

функція розв’язати(рядок, стовпці, діагональ1, діагональ2): якщо рядок == N: записуємо рішення; повертаємо для стовпця від 0 до N-1: d1 = рядок - стовпець + N // "/" ідентифікатор діагоналі d2 = рядок + стовпець // "\" ідентифікатор діагоналі якщо стовпець у стовпці або d1 у діагональ1 або d2 у діагональ2: продовжувати // конфлікт — пропускаємо, не рекурсуємо розмістити королеву в (рядок, стовпець) розв’язати(рядок + 1, стовпці ∪ {стовпець}, діагональ1 ∪ {d1}, діагональ2 ∪ {d2}) видалити королеву з (рядок, стовпець) // ← крок "зворотного відстеження" Обидва напрямки діагоналей відстежуються за допомогою одного цілого числа для кожної діагоналі — клітин на одній "/" діагоналі діляться рядком+стовпцем, а клітин на одній "\" діагоналі діляться рядком-стовпцем — тому перевірка конфлікту потребує трьох пошуків у наборі, кожен з яких O(1), а не сканування розміщених королів. Ця одна зміна пояснює, чому невміле рекурсивне розміщення без цих наборів ідентифікаторів помітно повільніше за версію, показану тут, навіть якщо обидві технічно є зворотним відстеженням.

function solve(row, cols, diag1, diag2):
    if row == N: record solution; return
    for col in 0..N-1:
        d1 = row - col + N        // "/" diagonal id
        d2 = row + col            // "\" diagonal id
        if col in cols or d1 in diag1 or d2 in diag2:
            continue               // conflict — skip, don't even recurse
        place queen at (row, col)
        solve(row + 1, cols ∪ {col}, diag1 ∪ {d1}, diag2 ∪ {d2})
        remove queen at (row, col)   // ← the "backtrack" step

Як велика кількість обрізання насправді відбувається

Пошукове дерево для розміщення N королів на рядок за рядком в принципі має N^N листів, якщо ігнорувати всі обмеження. Обрізка стовпця та діагоналі стискає це надзвичайно: N=8 має 92 рішення (12 до симметрії), досяжні після відвідування лише кількох тисяч часткових розміщень, і навіть N=20 — з 39×10^15 початковими порядками перестановки, якщо обмежується лише стовпцем — вирішується за менше секунди з методом відступу рядок за рядком, оскільки майже кожен гілку вмирає вже на кількох перших рядках. Кількість рішень сама по собі зростає приблизно як константа до степеня N (емпірично близько 2,5 до 2,7 для кожної додаткової королеви у діапазоні, який було обчислено точно), але ніхто не довів закриту формулу — кількість рішень вище N≈27 відома лише завдяки великим масштабним пошуковим зусиллям, а не з виведення.

Чому це є прикладом для значно більшої категорії проблем

Проблема N- королів (N-Queens) – це класичний приклад задачі про пошук у згоді з обмеженнями (CSP): змінні (одна на кожен рядок), області видимості (який стовпчик) та обмеження (відсутність спільних стовпчиків або діагоналей). Одна й та ж сама схема відслідковування назад (backtracking) із обробкою помилок, з заміною логіки перевірки обмежень, вирішує судочки, розфарбовування графів, складання графіків для іспитів та проєктування схем. Дві загальні пришвидшення CSP безпосередньо застосовуються до N-Queens: просування обмежень (перевірка на основі попереднього перегляду – після розміщення короля негайно зменшуйте кандидатські стовпчики для майбутніх рядків замість того, щоб чекати, поки не буде виявлено конфлікт) та евристики порядку змінних, такі як мінімальна кількість значень (розміщуйте найобмеженіший рядок наступним), обидва з яких обрізають дерево раніше і можуть перетворити вже швидкий пошук на набагато швидший при складніших задачах CSP, навіть якщо це майже не має значення для чистої проблеми N-Queens.

Поза зворотною відстановкою

Для дуже великих N локальний пошук перевершує систематичну зворотну відстановку: почніть із усіх N королів, розміщених (по одному на рядок і колонці, дозволено конфлікти), та повторно переносьте короля з найбільшою кількістю конфліктів у той стовпець, який мінімізує конфлікти – це форма hill climbing, яка називається min-conflicts. Він вирішує дошки з мільйоном королів приблизно за лінійний час, що є вражаючим контрастом до експоненційного найгіршого випадку зворотньої відстановки, оскільки він ніколи не повинен будувати рішення поступово з порожньої дошки; він виправляє вже-завершену, але несправну.

Це підхід, який уникає основної проблеми зворотньої відстановки – перебору всіх можливих варіантів. Min-conflicts є ефективним алгоритмом для великих задач, де кількість можливих ходів становить значну частину простору пошуку.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте N-Queens і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.