Алгоритмы, Шахматы | Михаил Арно, Олег Брагинский
Сможете расположить на шахматной доске восемь ферзей таким образом, чтобы ни один не находился под ударом? Основатель «Школы Траблшутеров» Олег Брагинский и ученик школы Михаил Арно показывают второе решение известнейшей шахматной задачи.
Развитие информатики упрочило популярность проблемы восьмёрки ферзей в исследовании алгоритмов: предоставляло хороший пример для демонстрации методов перебора и оптимизации. Этюд стал одной из классических задач, решаемых с помощью метода «ветвей и границ».
Задачу можно сформулировать и в других измерениях, например, математически. Это может выглядеть примерно так: «Заполните матрицу размером 8х8 нулями и единицами таким образом, чтобы сумма всех элементов в столбце, строке или диагональном ряде не превышала единицы».
Один из типовых алгоритмов решения задачи – использование поиска с возвратом: начальный ферзь ставится на первую горизонталь, затем каждая следующая фигура – на следующую строку так, чтобы находиться в безопасности и не быть битой ранее установленными королевами.
Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад: переставляется ранее установленный ферзь. Рассмотрим второй «ручной» вариант решения. Первый доступен по ссылке (ссылка на первую часть).
В первом варианте мы начинали ходить с самой верхней левой клетки А8. Теперь с этой же позиции посмотрим куда бы сходила фигура коня, но королеву в угол доски не ставим. Вариантов мало: только С7 или В6. Ввиду движения по порядку – сверху вниз, выбираем вариант С7 (N1).
Пропущена первая строка – осуществим ход конём. Ход Е8 (N2). Из этой же позиции С7 конём выставим ферзя на третью строку А6 (N3).
Из А6 конём не сможем поставить на четвёртую строку – встанет под удар. Пойдём ходом коня сразу на следующую (пятую сверху, или порядковую №4) строку. Ход В4 (N4).
Остаётся всего 10 свободных клеток, в которые нужно установить четыре оставшиеся королевы. Заметим, что симметричные ферзям клетки на противоположной стороне доски свободны. Займём свободные места! Восемь цариц красиво выстроились в виде наклонённого прямоугольника (N5).
Снимем красную бахрому с шахматного поля. Стянем диагонали и центры сторон. Увидим великолепную отработку стратегии «голубого океана»: никто ни с кем не толкается, у каждого своя одинаковая доля (N6).
Для усидчивых и любознательных читателей собрали все 23 уникальных варианта:
H1 G5 F8 E6 D3 C7 B2 A4 H1 G6 F8 E3 D7 C4 B2 A5 H1 G7 F4 E6 D8 C2 B5 A3
H1 G7 F5 E8 D2 C4 B6 A3 H2 G4 F6 E8 D3 C1 B7 A5 H2 G4 F6 E8 D5 C7 B1 A3
H2 G5 F7 E1 D3 C8 B6 A4 H2 G5 F7 E4 D1 C8 B6 A3 H2 G6 F1 E7 D4 C8 B5 A3
H2 G6 F8 E3 D1 C4 B7 A5 H2 G7 F3 E6 D8 C5 B1 A4 H2 G7 F5 E8 D1 C4 B6 A3
H2 G8 F6 E1 D3 C5 B7 A4 H3 G1 F7 E5 D8 C2 B4 A6 H3 G5 F2 E8 D1 C7 B4 A6
H3 G5 F2 E8 D6 C4 B7 A1 H3 G5 F7 E1 D6 C8 B2 A4 H3 G5 F8 E4 D1 C7 B2 A6
H3 G6 F2 E5 D8 C1 B7 A4 H3 G6 F2 E7 D1 C4 B8 A5 H3 G6 F8 E1 D4 C7 B5 A2
H3 G6 F8 E1 D5 C7 B2 A4 H3 G6 F8 E2 D4 C1 B7 A5
За годы исследований математиками и шахматистами было найдено немало других алгоритмов и методов решения. Преимущественно описанные математически, с применением формул и функций, такие изложения являются достаточно сложными для начинающих.
Мы рассмотрели лишь пару приёмов мануального скоростного решения расстановки ферзей. Любой из этих двух способов позволит страждущему раскидать фигуры королев по полю в рамках минуты, удивив и восхитив зрителей. Задача про ферзей продолжает оставаться популярной.