Публикация Школы траблшутеров

Второе решение про хитрых ферзей покажет сегодня вам яркий дисплей

Время чтения: 5 мин 5 сек
29 сентября 2023 г. Просмотров: 285

Алгоритмы, Шахматы | Михаил Арно, Олег Брагинский

Сможете расположить на шахматной доске восемь ферзей таким образом, чтобы ни один не находился под ударом? Основатель «Школы Траблшутеров» Олег Брагинский и ученик школы Михаил Арно показывают второе решение известнейшей шахматной задачи.

Развитие информатики упрочило популярность проблемы восьмёрки ферзей в исследовании алгоритмов: предоставляло хороший пример для демонстрации методов перебора и оптимизации. Этюд стал одной из классических задач, решаемых с помощью метода «ветвей и границ».

Задачу можно сформулировать и в других измерениях, например, математически. Это может выглядеть примерно так: «Заполните матрицу размером 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

За годы исследований математиками и шахматистами было найдено немало других алгоритмов и методов решения. Преимущественно описанные математически, с применением формул и функций, такие изложения являются достаточно сложными для начинающих.

Мы рассмотрели лишь пару приёмов мануального скоростного решения расстановки ферзей. Любой из этих двух способов позволит страждущему раскидать фигуры королев по полю в рамках минуты, удивив и восхитив зрителей. Задача про ферзей продолжает оставаться популярной.