UK 
EnglishТипова
Polski♛ Задача N Ферзів
Задача N ферзів: розставте ферзів на дошці без взаємних загроз. Пошук з поверненням, евристики та візуалізація всіх розв'язків.
Про задачу N ферзів
Задача N ферзів запитує, як розставити N шахових ферзів на дошці N×N так, щоб жодні два ферзі не ділили рядок, стовпець чи діагональ. Вперше її сформулював для дошки 8×8 шаховий композитор Макс Беццель у 1848 році; для N=8 існує 92 різні розв'язки. Це класичний тест на задоволення обмежень: пошук з поверненням разом із поширенням обмежень (forward checking) різко скорочує дерево пошуку, виключаючи стовпці й діагоналі одразу після розміщення кожного ферзя, звужуючи наївний простір пошуку розміром N^N до прийнятного обсягу.
Цей візуалізатор дозволяє встановити розмір дошки від 4 до 12, а потім переглядати алгоритм покроково або в автоматичному режимі. Клітини з конфліктом підсвічуються червоним у момент розміщення ферзя; кроки повернення показані оранжевим, а дійсні розміщення — зеленим. Лічильник відстежує, скільки розв'язків знайдено і скільки вузлів дерева пошуку відвідано.
Часті запитання
Як алгоритм пошуку з поверненням вирішує, куди поставити кожного ферзя?
Для кожного стовпця алгоритм перевіряє рядки згори донизу, з'ясовуючи, чи новий ферзь ділить рядок або діагональ з уже розміщеним ферзем. Використовується перший безпечний рядок, після чого пошук переходить до наступного стовпця.
Що відбувається, якщо в стовпці немає жодного безпечного рядка?
Якщо кожен рядок конфліктує з уже розміщеним ферзем, алгоритм повертається назад: він знімає попереднього ферзя і продовжує з наступного рядка на його місці — саме це підраховує статистика «Повернень».
Чому зі збільшенням N пошук стає набагато повільнішим?
Кількість способів розставити N ферзів зростає приблизно експоненційно з розміром дошки. При N=8 існує 92 розв'язки, при N=12 — уже 14 200, а кількість кроків пошуку з поверненням, потрібних, щоб знайти їх усі, зростає ще швидше.
Що означають чотири кольори на дошці?
Жовтий позначає ферзя, який зараз перевіряється, зелений — підтверджено безпечних ферзів, червоний підсвічує конфлікт із раніше розміщеним ферзем, а синій спалах відмічає момент, коли всі стовпці заповнено без конфліктів.
Чи знаходить алгоритм усі можливі розв'язки, чи лише один?
Якщо не зупиняти, алгоритм після кожного знайденого розв'язку продовжує повертатися назад і шукати далі, доки не вичерпає все дерево пошуку — тож лічильник «Знайдено розв'язків» підсумовує кожне дійсне розташування для обраного N.