Алгоритмы, Шахматы | Михаил Арно, Олег Брагинский
Сможете сходу расположить восемь враждебных друг другу ферзей на шахматной доске, так чтобы ни один не находился под ударом? Основатель «Школы Траблшутеров» Олег Брагинский и ученик школы Михаил Арно раскладывают в деталях решение известной шахматной задачи.
Исторический и классический пример в области комбинаторной математики и информатики хорошо известен шахматистам. Постановка задачи: «расставить на доске восемь ферзей таким образом, чтобы ни один их них не находился под ударом другого».
История задачи зародилась в XIX веке. Немецкий шахматист Макс Базель предложил первые вариации в 1848 году для досок меньших размеров. Французский теоретик Франсуа-Антуан Андре Филидор через пару лет поставил проблему о расстановке ферзей на стандартной доске 8x8.
Этюд получил широкое распространение с подачи американского шахматиста Пола Морфи, который в 1857 предложил её как задачу для размышления. Таким образом, требовалось выйти за рамки нескольких схематичных расстановок ферзей, найти все вариации и предложить алгоритм.
Только спустя 17 лет(!), в 1874 году, было найдено и предложено первое полное решение Эрнестом Бергером. Комбинаторик вывел 92 возможных варианта расстановки ферзей на игровой доске 8x8. Отсутствие иных решений позднее подтвердил полный компьютерный перебор.
Впрочем, если впервые знакомиться с проблемой, то на раскладку даже первого решения могут уйти часы, новичок утонет в размышлениях, не приблизившись к правильной последовательности. А ведь такая задачка попадается и на школьных олимпиадах, где каждая минута бесценна.
Зачастую поиски решения заходят в тупик на 6-7 ходе, когда становится невозможным поставить очередную фигуру: все клетки шахматной доски находятся под ударом. Нервы сдают, ферзи в гневе летят со стола, громко пульсируют вены. Решающий не может найти и одной расстановки, а их 92.
В ходе исследования этой задачи в материалах данной статьи будут представлены простейшие алгоритмы, трюки и нюансы, которые легко помогут разрулить задачу по щелчку пальцев, даже человеку далёкому от шахмат, если таковому доведётся с ней встретиться.
Общее число возможных комбинаций восьми ферзей на 64-клеточной доске равно 4’426’165’368, без проверки на бой. Даже компьютеру на перебор такого множества потребуется значительное время. Язык не повернётся назвать рациональным решение, полученное методом перебора.
От неравнодушных и пытливых требуется найти и реализовать алгоритм, который позволил бы существенно сократить объём лишних операций. Как всем известно, ферзь бьет все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям.
Очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной линии.
Такое простое правило уменьшает число возможных расположений до 16’777’216. Генерируя перестановки, являющиеся решениями задачи о восьми ладьях, и проверяя затем атаки по диагоналям, можно сократить число возможных расположений всего до 40’320.
Если же при генерации позиций также учитывать условие нападения по диагонали, то скорость счёта возрастает на порядок и максимальное число циклов для решения задачи составит 4’022.
Мы не компьютеры, и бывает требуется решить задачу без использования ЭВМ. Что стоит помнить:
- Антиподом ферзя является конь. Соответственно, любая следующая постановка ферзя будет как минимум на расстоянии хода коня.
- Ферзей 8, шахматная доска 8х8. Логично, что в одной колонке и в одной строке может находиться только один ферзь. Расставим напротив каждой строки по ферзю.
Восемь грозных фигур в боевом порядке застыли с левой стороны доски:
Большинство людей на планете читает слева-направо, сверху-вниз. Так и начнём: ход А8. Красным отметим клетки, которые будем отсекать для следующих ходов (N2).
В верхней строке (восьмой) невозможно поставить второго ферзя, спускаемся на следующую строку (седьмую). Двигаясь слева-направо, попадаем в первую свободную клетку С7. Ставим второго на доску. Красным подсветим новые неприступные для следующих ходов места (N3).
Повторяя предыдущие действия, третья фигура царицы займёт клетку Е6 (N4). Четвёртая по прежнему алгоритму встанет на G5. Образовалась уникальная ситуация, при которой первые четыре ферзя полностью выбили колонку H – диагоналями и горизонталями (N5).
Многие не заметят этого и пойдут ставить ферзей на оставшиеся свободные ячейки, но этого не получится осуществить, ведь две королевы останутся не у дел. Что же делать?
Помним, что одна колонка должна содержать единственную фигуру. Провернем трюк – условно «переместим» эту колонку в левую часть доски, так что бы она заняла место колонки А. Соответственно фигуры сдвинутся вправо на шаг (N6).
Хитрость дала две свободные клетки для постановки королевы (А3 или А2). Но идём по порядку. Четыре строки заполнены, на пятую по порядку идёт пятая фигура. Ход С4 (N7).
Не нарушая алгоритма ходом А3, ставим шестого универсала. Постоянно обновляем ячейки, на которые нельзя ходить (N8).
Седьмым ходом ставим ферзя на единственную свободную ячейку седьмой строки (N9). И невооруженным взглядом видим оставшуюся последнюю свободную ячейку для восьмой фигуры Е1. Завершаем решение первой раскладки (N10 и N11).
Простой алгоритм движения «слева-направо-сверху вниз» позволил осуществить раскладку известной задачи, над которой долго бились просвещённые умы.
На этом этапе стоит догадаться, что шахматная доска с четырьмя сторонами, имеет четыре симметричных решения. Трижды перевернув на 90 градусов, получим ещё три раскладки.
Из этого также можно рассчитать количество уникальных раскладок от общего числа решений: 92/4=23. Всего 23 уникальные раскладки, остальные образуются путём поворотов.
Взять на заметку изложение второго примера ручного алгоритма решения задачи, а также набор раскладок ферзей на доске 8*8 можно по ссылке.