Переборная схема. Задача о ферзях
- Понятие о сложности алгоритма
- Оценка сложности алгоритмов поиска и сортировки.
- Сложность задач минимакса («сравнить каждый с каждым»)
- Классическая задача о ферзях:
- формулировка
- «лобовые» методы решения
Домашнее задание
Прочитать о задаче о восьми ферзях в Википедии .Обратите внимание: пример решения на QBasic — «тупой», на C++ — чуть получше - Решить задачу подсчёта количества вариантов
- «В лоб»
- Для поля N×N, избавившись от вложенных циклов за счёт хранения текущей позиции каждого нового ферзя в списке
- Располагая ферзей каждого на своей вертикали (если ещё не:)
- Вместо проверки всей доски проверять, можно ли выставить очередного ферзя на данное поле (если нет, следующих выставлять уже нет смысля, надо двигать этого)
- Вместо функции проверки, можно ли выставить ферзя на данное поле, хранить шахматную доску с отмеченными полями, которые находятся под боем уже выставленных ферзей. Тогда можно считать число свободных клеток и если их осталось меньше, чем ферзей, не пытаться заполнять доску дальше, а менять расположение имеющихся
Решение queens.py
Условные обозначения
— тема по Linux 
— необязательная тема - — теоретическое задание
— тема для самостоятельного изучения