Задача о восьми ферзях
Задача о восьми ферзях требует расставить на шахматной доске восемь ферзей так, чтобы никакие два не били друг друга. Шахматный композитор Макс Беццель опубликовал её в 1848 году, и она стала классическим первым примером поиска с возвратом.
Шахматная головоломка 1848 года
Макс Беццель, немецкий шахматный композитор, предложил задачу в берлинском шахматном журнале в 1848 году. Франц Наук опубликовал все 92 решения в 1850 году и задал тот же вопрос для досок большего размера. Карл Фридрих Гаусс с интересом следил за задачей и обсуждал её в своих письмах.
Один ферзь в каждом ряду и столбце
Восемь ферзей, которые не бьют друг друга, должны стоять в восьми разных рядах и восьми разных столбцах. Поэтому решение — это числа от 1 до 8 в перемешанном порядке, то есть перестановка, с одним дополнительным правилом: никакие два ферзя не могут стоять на одной диагонали. Из 40 320 перестановок подходят только 92.
Поиск с возвратом
Поиск с возвратом строит решение по частям и отступает назад, как только заходит в тупик. Для ферзей это так: поставьте ферзя на первую безопасную клетку следующего ряда, а когда в ряду нет безопасной клетки, вернитесь к ряду выше и сдвиньте того ферзя дальше. В 1972 году Эдсгер Дейкстра объяснял на этой задаче структурное программирование именно с помощью такого поиска.
Симметрия
Поверните доску на четверть оборота или отразите её, и решение останется решением. Так у каждого решения получается до восьми вариантов. 92 решения распадаются на 12 таких семейств: в одиннадцати по 8 решений, а в одном только 4, потому что это решение выглядит так же после поворота на пол-оборота.
Задача об n ферзях
На доске n×n вопрос тот же, только ферзей n. Решения есть для любого n начиная с 4, и их число быстро растёт: 2 для 4×4, 92 для 8×8 и 14 200 для 12×12. Формула для их числа неизвестна; рекордные значения получены большими компьютерными переборами.
Попробуйте в PictorX
Откройте «Восемь ферзей» и щёлкните клетку, чтобы поставить ферзя; щёлкните её ещё раз, чтобы убрать. «Показать битые клетки» отмечает точкой клетки, которые бьют ваши ферзи, а красные ферзи бьют друг друга. «Решить» шаг за шагом выполняет поиск с возвратом и оставляет на месте поставленных вами ферзей. «Следующее решение» перебирает все решения по порядку, а «Размер» меняет доску от 4×4 до 12×12.
Часто задаваемые вопросы
Кто придумал задачу о восьми ферзях?
Макс Беццель, немецкий шахматный композитор, в 1848 году. Франц Наук опубликовал первый полный набор решений в 1850 году.
Сколько всего решений?
92 на стандартной доске. Если повороты и отражения считать за одно, их 12.
Почему у доски 6×6 так мало решений?
Их всего 4, и все из одного семейства. У меньшей доски 5×5 их 10. У больших досок их всё больше: 40 на 7×7 и 92 на 8×8.
PictorX что-нибудь загружает?
Нет. Доска рисуется на холсте в браузере. Кнопка «Сохранить» скачивает PNG, а кнопка «Редактировать» открывает это изображение в редакторе PictorX.
Сопутствующие инструменты
Восемь ферзей
Расставьте восемь ферзей на шахматной доске так, чтобы ни один не бил другого. Попробуйте сами, посмотрите, как поиск с возвратом шаг за шагом находит решение, и переберите все 92 решения.
Ход коня
Проведите шахматного коня по всем полям доски, побывав на каждом ровно один раз. Играйте сами с подсказками Варнсдорфа или смотрите, как «Решить» завершает открытый или замкнутый маршрут. Сохраните путь в PNG.
Задача о ходе коня
История и математика задачи о ходе коня: Эйлер и Варнсдорф, открытые и замкнутые маршруты, почему на нечётных досках нет замкнутого маршрута и как компьютер его находит.
Ханойская башня
Перенесите в браузере башню из дисков между тремя стержнями. По одному диску, никогда больший на меньший. Кратчайшее решение — 2ⁿ − 1 ходов.
Ханойская башня
Ханойская башня: три стержня, по одному диску, и никогда больший на меньший. Кратчайшее решение — 2ⁿ−1 ходов. Эдуард Люка представил головоломку в 1883 году.
Муравей Лэнгтона
Запустите муравья Лэнгтона в браузере. Посмотрите на симметрию, хаос и шоссе с циклом в 104 шага, а затем попробуйте многоцветные правила, нескольких муравьёв, шестиугольную сетку и турмитов.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать «Восемь ферзей»