Есть такой класс задачек: о расстановке шахматных фигур. Сколько ферзей можно расставить так, чтобы они не били друг друга? А коней? А на доску другого размера?
Несмотря на кажущуюся искусственность постановки, задачки полезны сразу с нескольких точек зрения. Методы и подходы к решению, варианты и как вариация условий влияет на ответ и на саму задачу, ну и сам ответ может быть небесполезен.
Давайте глянем на названия фигур, это тоже любопытно.
- Ферзь происходит из персидского и означает "советник, визирь"; по-английски это "королева", queen; по-итальянски просто "женщина", donna. Женщина, получается, самая сильная фигура у итальянцев.
- Король, king, re везде король.
- Ладья, rook, torre: лодка(?), от персидского "колесница", башня.
- Слон, bishop, alfiere: видимо, боевой слон, епископ, знаменосец. Есть антиклерикальные шахматы, доска 6х6, без слонов. Загадка, при чём тут клирики, если не знаешь английского.
- Конь, knight, cavallo: ну, всадник имеется в виду, конечно; по-англйиски "рыцарь", по-итальянски "лошадь".
- Пешка, pawn, pedone. Всё означает пешего воина или просто пешехода.
Начнем с ферзей. Сколько ферзей можно поставить на доску так, чтобы они не били друг друга?
Ясно, что не более восьми, так как каждый ферзь может быть только один на своей горизонтали. При этом восемь расставить можно.
Второй вопрос: сколько способов есть расставить восемь ферзей на обычной шахматной доске?
Эта задача чисто переборная, ее рассуждениями не решить. Ответ: 92 способа.
Однако хитрость в том, чтобы сократить перебор. Во-первых, преобразования симметрии позволяют размножать решения. Например, если перевернуть доску или зеркально отразить, то решение может получиться другое. Если такие решения считать за одно (фундаментальные решения), то их всего 12. Все они приведены в английской Википедии.
Во-вторых, есть способы перебирать лучше, но это отдельная наука.
Минимальное число ферзей, контролирующих всю доску, тоже легко определяется и это тоже восемь, так как ферзь держит только одну горизонталь, а их восемь.
Давайте посмотрим на доски произвольного размера nxn и надо расставить n ферзей. На доске 2х2 и 3х3 решений нет: на первой один ферзь бьет все поля, на вторую можно поставить два ферзя, но не больше. Для 4х4 есть одно фундаментальное решение:
oqoo
oooq
qooo
ooqo
из которого получаются два симметричных. Для 5х5 фундаментальных решений два, из которых получается десять, для шести одно (и четыре), а вот потом число решений начинает быстро расти. Полностью обсчитаны доски до 27. И есть асимптотическая формула (0.143n)ⁿ. Ясно, что решений будет много... эн в степени эн, это круче даже экспоненты. По-видимому, это все решения, но фундаментальных немногим меньше. Ведь симметрий всего восемь, а некоторые решения могут сразу быть симметричными и при преобразовании не "раздваиваться".
Теперь рассмотрим ту же задачу для коней. Хотя конь ходит хитрее, задача оказывается проще. Она решается без перебора. Итак, сколько коней можно поставить на шахматную доску так, чтобы они не били друг друга?
Вспомним, что доска двухцветная: поля черные и белые, попеременно. И конь с черного поля бьет непременно белое, и наоборот.
Поэтому, если расставить коней на белых полях, они друг друга бить не будут; это дает сразу 32 коня.
А можно ли больше? Если нельзя, то надо это доказать.
Нельзя. Давайте докажем это.
Здесь надо применить такой принцип: фрагмент решения задачи оптимизации сам оптимален. Конечно, есть оговорки, но часто этот принцип применим. Вот и сейчас.
Рассмотрим фрагмент доски 2х4. На нем можно разместить четыре коня, но не больше. Это легко проверить. Разместить можно как мы это делали, на белых полях. А вот пять коней никак не поместить, что легко проверяется. Каждый конь бьёт ровно одно поле, и одно занимает сам. Так что четыре коня, не бьющие друг друга, занимают четыре поля и бьют ещё четыре. Всё.
Теперь, если на всей доске стоит более 32 коней, а доска разделяется на восемь таких фрагментов, то в одном (хотя бы) из фрагментов будет более четырех коней. Это принцип Дирихле.
А раз более четырех в "клетку" 4х2 не поставить, то и на большую доску более 8х4=32 коней не поставить.
С другой стороны, в "клетку" можно посадить четырех коней разными способами. Помимо занятия белых или черных полей, можно еще так:
kkoo
kkoo
и ещё несколько вариантов. Однако легко проверить, что кони из такой клетки бьют коней из какой-нибуль соседней. Единственные два способа расставить коней по всей доске - это на поля одного цвета.
Теперь задумаемся. Двуцветность доски помогла, но доска могла и не быть раскрашена в два цвета. Например, в японских шахматах сёги доска одноцветная. И при этом 9х9. И там надо сначала придумать раскрасить ее, и это уже Идея.
Сколько обычных шахматных коней (не сёги!) можно расставить на доске для сёги так, чтобы кони друг друга не били?
Раскраска доски показывает два теперь разных способа: на белые и на черные поля. При этом белых 40, а черных 41, так что один вариант лучше другого. Как доказать, что 41 - это максимум?
Отделив мысленно одну крайнюю вертикаль и одну крайнюю горизонталь, мы получим доску 8х8, на которой будет стоять максимальное число коней, а именно 32. И мы доказали, что они будут стоять на полях одного цвета. При этом они бьют все поля другого цвета на всей доске, в том числе и на удаленных линиях, не бьют ни одного поля своего цвета и не бьются с полей ствоего цвета. Так что можно все поля того же цвета заставить конями. Это дает ещё либо 8 коней, либо 9. И полное число получается либо 40, либо 41.
А вот задачу для сёги без всего "бэкграунда" решить куда сложнее: доска не раскрашена и подсказки нет, подмножества 8х8 с единственным решением тоже. Остаётся прямой перебор. Мастерство состоит в том, чтобы прямого перебора избежать, а если не получается, то сократить.
Так и работаем.
А попробуйте расставить максимум слонов и доказать оптимальность!
