Временная сложность
O(N!)
Задача о N ферзях формулируется следующим образом: как разместить N шахматных ферзей на доске размером N×N так, чтобы ни один из них не угрожал другим?
Ферзь может атаковать любую фигуру, находящуюся в той же строке, столбце или на той же диагонали. Поэтому решение должно гарантировать, что никакие два ферзя не находятся в одной строке, столбце или на одной диагонали.
Как это работает (поиск с возвратом):
1. Размещать ферзей по одному, начиная с первой строки
2. Для каждой строки проверять каждый столбец
3. Проверять, является ли позиция безопасной (нет ли конфликтов)
4. Если позиция безопасна, разместить ферзя и перейти к следующей строке
5. Если безопасного столбца нет, вернуться к предыдущей строке и изменить расположение ферзя
Эта визуализация показывает задачу о 4 ферзях на доске размером 4×4.
Временная сложность: O(N!) — в худшем случае
Пространственная сложность: O(N²) — для хранения доски
Задача о N ферзях — классический пример алгоритмов поиска с возвратом и задач удовлетворения ограничений.
Похожие алгоритмы
Частые вопросы
- Что такое Задача о N ферзях?
- Задача о N ферзях формулируется следующим образом: как разместить N шахматных ферзей на доске размером N×N так, чтобы ни один из них не угрожал другим?
- Какова сложность Задача о N ферзях?
- Время (среднее): O(N!) · Память: O(N²)
- Для кого предназначена визуализация Задача о N ферзях?
- Визуализация Задача о N ферзях рассчитана на продвинутый уровень в категории «Поиск с возвратом». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Задача о N ферзях?
- В той же категории (Поиск с возвратом) вы можете изучить: Sudoku Solver, Maze Pathfinding. Каждый из них имеет интерактивную визуализацию.