Про задачу N ферзів
Задача N ферзів полягає у розміщенні N шахових ферзів на дошці N×N так, щоб жодні два ферзі не атакували одне одного (не ділили рядок, стовпець або діагональ). Вперше вона була поставлена для дошки 8×8 шахістом Максом Беззелем у 1848 році і має 92 різних розв'язки для N=8. Задача є класичним орієнтиром задоволення обмежень: відстеження з поширенням обмежень (перевірка вперед) різко скорочує дерево пошуку, усуваючи стовпці та діагоналі під час розміщення кожного ферзя.
Цей візуалізатор дозволяє встановити розмір дошки від 4 до 12, а потім покроково або автоматично переглядати алгоритм відстеження. Конфліктні клітини підсвічуються червоним при розміщенні ферзя; ходи відстеження показані оранжевим, а валідні розміщення — зеленим. Лічильник відстежує знайдені розв'язки та кількість відвіданих вузлів дерева пошуку.
Часті запитання
Скільки розв'язків існує для задачі N ферзів на дошці 8×8?
Існує рівно 92 різних розв'язки для N=8. З урахуванням лише принципово різних розташувань (без обертань та відображень дошки) залишається 12 унікальних розв'язків. Для N=1 тривіально існує 1 розв'язок; N=2 та N=3 не мають розв'язків; кількість швидко зростає: N=12 має 14 200 розв'язків, а N=15 — 2 279 184.
Як відстеження з поширенням обмежень розв'язує задачу N ферзів?
Алгоритм розміщує ферзів по одному в кожному рядку. Перед розміщенням ферзя у стовпці він перевіряє, чи вже атакований цей стовпець або будь-яка з діагоналей. Якщо так — пропускає цей стовпець. Коли у рядку немає валідного стовпця, алгоритм повертається до попереднього рядка і пробує наступний стовпець. Це відсікання скорочує роботу від O(N!) до значно меншої на практиці.
Чи є задача N ферзів NP-повною?
Задача визначення, чи можна розширити часткове розміщення ферзів до повного розв'язку («Доповнення N ферзів»), була доведена як NP-повна Дженом, Джефферсоном та Найтінгейлом у 2017 році. Однак знаходження одного розв'язку стандартної задачі N ферзів можна виконати за O(N) часу за допомогою явних конструкцій, тому задача доповнення є суворо складнішою.
Яка явна конструкція O(N) для задачі N ферзів?
Існує кілька явних конструкцій O(N). Одна з них: якщо N mod 6 не дорівнює 2 і N mod 6 не дорівнює 3, розміщуємо ферзів у стовпцях 2, 4, 6, ..., N, 1, 3, 5, ..., N-1 (спочатку парні стовпці, потім непарні). Особливі впорядкування обробляють випадки N mod 6 = 2 і mod 6 = 3. Ці конструкції дають один валідний розв'язок без будь-якого відстеження.
Як скорочення симетрії прискорює пошук?
Наївний пошук з відстеженням знаходить усі 92 розв'язки для N=8. Використовуючи 8-кратну групу симетрії квадрата (4 обертання та 2 відображення), потрібно шукати лише у першій половині першого рядка (стовпці 1-4), а потім відображати кожен знайдений розв'язок. Це скорочує пошук приблизно у 8 разів і є стандартним методом розриву симетрії у комбінаторному пошуку.
Що таке перевірка вперед у контексті задачі N ферзів?
Перевірка вперед — це техніка завчасного перегляду: після розміщення ферзя алгоритм одразу видаляє всі атаковані клітини з областей (доступних стовпців) майбутніх рядків. Якщо область будь-якого майбутнього рядка стає порожньою, поточна гілка одразу відсікається. Для N ферзів це еквівалентно відстеженню трьох бітових векторів: атакованих стовпців, лівих та правих діагоналей.
Чи може маніпуляція бітами прискорити розв'язувач задачі N ферзів?
Так. Класичний розв'язувач за допомогою бітових операцій (Мартін Річардс, 1997) представляє атаковані стовпці, ліві та праві діагоналі як цілі числа і використовує побітові AND, OR та зсуви для обчислення доступних позицій. Кожне розміщення — це один біт, очищений з маски доступних стовпців; відстеження відновлює маску. Це дозволяє сучасним процесорам досліджувати мільйони позицій за секунду і знаходити всі 92 розв'язки для N=8 за мікросекунди.
Чи є практичні застосування задачі N ферзів?
Задача N ферзів використовується як тест для розв'язувачів обмежень та паралельного пошуку. Системи обмежень Choco, Gecode та OR-Tools включають її як стандартний тестовий випадок. Базова техніка — розміщення неконфліктних елементів на структурованій сітці — має аналоги у проектуванні мікросхем VLSI, плануванні (невзаємозамінні часові слоти) та передбаченні вторинної структури РНК.
Скільки розв'язків має задача N ферзів для великих N?
Точна кількість розв'язків Q(N) зростає приблизно експоненційно; послідовність є OEIS A000170. Q(20) = 39 029 188 884, а Q(27) = 234 907 967 154 122 528. Для N більше або рівного 28 точні підрахунки не опубліковані станом на 2024 рік; обчислення Q(28) вимагало б потужності петафлопного масштабу. Асимптотичні оцінки припускають Q(N) приблизно (0,143 N)^N, але точна асимптотика залишається відкритим науковим питанням.
Який зв'язок між задачею N ферзів та латинськими квадратами?
Розв'язок задачі N ферзів, де ферзі також займають різні зламані діагоналі (тороїдальні діагоналі, що обертаються навколо дошки) — це «тороїдальний» або «модульний» розв'язок задачі N ферзів, і він відповідає трансверсалі циклічного латинського квадрата. Такі розв'язки існують лише для N, не кратного 2 або 3. Цей зв'язок пов'язує комбінаторику, теорію груп та дизайн ортогональних латинських квадратів у статистичному проектуванні експериментів.