Европа · том I; задача поставлена Беццелем в 1848
Восемь ферзей
Как звучало тогда
Расставить на шахматной доске восемь ферзей так, чтобы ни один не находился под боем другого.
Условие
Сколькими способами можно расставить на доске $8\times8$ восемь ферзей так, чтобы никакие два не били друг друга?
Показать ответ
92 расстановки; с точностью до поворотов и отражений их 12
О чём эта задача
Задачу поставил в шахматном журнале Макс Беццель, а Гаусс, узнав о ней, сперва насчитал 72 решения и лишь потом нашёл все 92 — случай, когда великий математик ошибся в переборе. Ключ к счёту в том, что ферзи стоят по одному в каждой строке и каждом столбце: значит, расстановка есть перестановка восьми чисел, и остаётся отсеять те, где совпадают диагонали. Из $8!=40320$ перестановок годятся 92. Это стандартный пример перебора с возвратом — приёма, с которого начинается всякий курс алгоритмов.
Разбор — «как решали тогда» и «как решают сейчас» — для этой задачи ещё не написан.