Глава 9. Независимость и доминирование шахматных фигур

Множество очень интересных и красивых задач на шахматной доске возникает при решении двух следующих комбинаторных проблем.

1. Какое максимальное число одноименных фигур (ферзей, ладей, слонов, коней или королей) можно расставить на шахматной доске так, чтобы никакие две из них не угрожали друг другу?

2. Какое минимальное число одноименных фигур (ферзей, ладей, слонов, коней или королей) можно расставить на шахматной доске так, чтобы они держали под обстрелом все свободные поля доски?

Первое из этих чисел мы будем называть числом независимости для соответствующих фигур, а второе - числом доминирования. Для единства терминологии фигуры, которые не угрожают друг другу, будем называть независимыми, а фигуры, обстреливающие все свободные поля доски (доминирующие на доске), - доминирующими.

Здесь мы имеем явную аналогию с рядом важных задач из теории графов. Чтобы убедиться в этом, приведем следующие определения. Множество вершин графа называется независимым, если никакие две из них не соединены между собой ребром. Среди независимых множеств существует хотя бы одно «максимально независимое», содержащее максимальное число вершин. Это число называется числом независимости для данного графа (или числом его внешней устойчивости).

Множество вершин графа называется доминирующим, если каждая вершина вне этого множества соединена ребром хотя бы с одной вершиной, принадлежащей ему. Среди доминирующих множеств существует хотя бы одно «минимально доминирующее», содержащее минимальное число вершин. Это число называется числом доминирования для данного графа (или числом его внутренней устойчивости)36.

Каждой шахматной фигуре можно поставить в соответствие граф, вершины которого расположены на всех 64 полях доски, а ребра соответствуют ходам этой фигуры. Иначе говоря, если фигура в состоянии сделать ход между двумя данными полями, то расположенные в них вершины соединены ребром (аналогично был введен граф при рассмотрении задачи о коне Аттилы). Теперь легко убедиться в том, что наша первая проблема заключается в определении числа независимости для графа данной фигуры, а вторая проблема - в определении числа доминирования.

Установленная связь между чисто математическими объектами - графами и задачами о шахматных фигурах, как мы видели, довольно естественна, чем и объясняется большая популярность шахматных терминов и задач в литературе по теории графов. Многие задачи о графах, весьма сложные в общем случае, удается решить для графов шахматных фигур. Именно так обстоит дело и с задачами о независимости и доминировании на шахматной доске. Ниже мы найдем числа независимости и доминирования для графов всех шахматных фигур и, следовательно, разрешим для них обе наши проблемы. Попутно нами будут рассмотрены вопросы о подсчете числа «оптимальных» расстановок фигур, а также разлтные обобщения для досок n×n. Для удобства через А будем обозначать число независимости, а через D - число доминирования, индекс у этих букв указывает размер доски; так, D_n (Л) - число доминирования для ладей на доске n×n. Результаты наших исследований мы будем заносить в табл. 2, знаки вопроса означают, что соответствующие числа неизвестны (по крайней мере, автору). После каждой строки с числами N и D в таблще идет строка с числом «оптимальных» расстановок на доске - т. е. расстановок, в которых участвуют, соответственно, N или D указанных фигур.

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

1. Ферзь. Число независимости для ферзей на любой доске n×n найдено в предыдущей главе, имеем N₂(Ф) = 1, N₃(Ф) = 2, N_n(Ф) = n (n ≠ 2, 3). Формула для числа соответствующих расстановок в общем случае не известна. На обычной доске, как мы знаем, кожно расставить восемь независимых ферзей (рис. 43), причем существуют 92 различные расстановки.

Число доминирования для ферзей на обычной доске, как, впрочем, и на досках 9×9, 10×10 и 11×11 (рис. 35, 39), равно пяти. Существует 4860 способов для расстановки пяти «ферзей-часовых» на доске 8×8. Как уже говори л ось, в общем случае формулу для D_n (Ф) никому найти не удалось (тем более неизвестно и число решений).

2. Ладья. Для ладьи все результаты получены в главе 6. Как мы знаем, N_n (Л) = D_n(Л) = n, а число расстановок соответственно равно n! и 2nⁿ - n! На обычной доске имеется 8! расстановок восьми независимых ладей и 2×8⁸ - 8! расстановок восьми доминирующих ладей.

3. Конь. На обычной доске успешно доминируют 12 коней (рис. 47); что касается доминирования на доске n×n, то здесь вопрос остается открытым. Гарднер приводит числа D_n(К) для всех n ≤ 10.

Про независимость коней известно гораздо больше. Очевидно, что на обычной доске можно расположить 32 независимых коня, достаточно поставить их на все белые или на все черные поля. Кстати, никаких других фигур, не угрожающих друг другу, в таком количестве расставить на доске невозможно, и поэтому коней можно по праву считать самыми мирными жителями шахматной семьи. Больше 32 независимых коней на шахматной доске расставить не удается. Докажем это двумя различными способами.

Рис. 48. Задача о мирных конях

а. Разобьем доску на восемь конгруэнтных прямоугольников (рис. 48) и рассмотрим один из них. Конь, стоящий в данном прямоугольнике, держит под обстрелом ровно одно его поле; при этом, куда бы мы ни поставили двух коней, поля прямоугольника, на которые они нападают, различны. Поскольку каждый прямоугольник состоит из восьми полей, то внутри него можно разместить не более четырех коней, не угрожающих друг другу, а значит - общее число коней не превосходит 4×8 = 32.

б. Непосредственное доказательство того, что максимальное число «мирных» коней равно 32, следует из существования замкнутого маршрута коня. Действительно, в таком маршруте после каждого поля, занятого конем, должно следовать свободное поле, а поскольку маршрут охватывает всю доску, то более половины ее полей не могут быть заняты конями.

Доказательство, аналогичное а), показывает, что

N_n(К) = n²/2, если n четно, и N_n(К) = (n²/2 + 1)/2, если n нечетно. В первом случае существуют только две необходимые расстановки, а во втором - всего одна (кони должны стоять на полях того цвета, которого на доске больше). То, что иных расстановок не существует, доказано у Ягломов.

С математической точки зрения король и слон не так интересны, как другие шахматные фигуры, и поэтому в настоящей книге им уделено меньше внимания. Сейчас мы найдем для этих фигур числа независимости и доминирования.

4. Слон. Для нахождения числа независимости рассмотрим на шахматной доске пятнадцать диагоналей, показанных на рис. 49. Если никакие два слона не угрожают друг другу, то на каждой из этих диагоналей мвжет стоять не более одного слона. Поскольку диагонали покрывают все поля доски, общее число независимых слонов не превосходит пятнадцати. Одиако ровно столько слонов тоже не удается поставить, так как крайние из наших диагоналей состоят из одного поля, причем оба эти поля расположены на одной диагонали a8 - h1. Расстановка на рис. 49 показывает, что N₈(С) = 14. Совершенно аналогично получаем N_n(С) = 2n - 2. При этом можно показать, что при n > 1 на доске n×n существует 2ⁿ необходимых расстановок (в каждой из них все слоны расположены на крайних линиях). Соответствующие доказательства можно найти в книге Ягломов.

Восемь «слонов-часовых» вполне в состоянии справиться с шахматной «тюрьмой» (рис. 50). Покажем, что меньшее число слонов доминировать на доске не может. Пусть на ней стоит меньше четырех белопольных слонов. Тогда не меньше пяти белых диагоналей (из восьми отмеченных на рисунке) свободны от слонов, причем хотя бы одна из них содержит больше трех полей. Так как ни один из выбранных слонов не может угрожать более чем одному полю такой диагонали (на ней самой слонов нет), то все ее поля не могут одновременно находиться под угрозой - противоречие. Итак, на доске должно стоять не меньше четырех белопольных слонов. Точно так же получаем, что на ней должно стоять и не меньше четырех чернопольных слонов, т. е. общее число слонов не меньше восьми, D₈(С) = 8.

Аналогично получаем D_n(С) = n. Число способов доминирования восьми слонов на шахматной доске равно 20736; для доски n×n формула имеет довольно сложный вид, ее вывод приведен у Ягломов.

Рис. 51. Шестнадцать независимых королей на шахматной доске

5. Король. Для определения числа независимости для королей разобьем шахматную доску на 16 квадратов (рис. 51). При расстановке королей, не угрожающих друг другу, т. е. не стоящих рядом, в каждом из этих квадратов может находиться не более одного короля. Это означает, что больше 16 независимых королей расставить невозможно, а ровно столько стоит на рис. 51. Совершенно аналогично показывается, что на доске n×n можно расставить (n/2)² независимых королей при четных n и ((n + 1)/2)² - при нечетных n. На обычной доске существует 281571 расстановок; формулы для доски n×n имеются у Фабеля.

Теперь найдем число D₈(Кр). В каждом из девяти прямоугольников, выделенных на рис. 52 (четыре из них квадраты), имеется поле (на нем стоит король), которое может быть атаковано только королем, находящимся в этом же прямоугольнике. Следовательно, для того чтобы все свободные поля находились под угрозой, в каждом из наших девяти прямоугольников должен стоять хотя бы один король, и D₈(Кр) = 9.

Для доски n×n последняя задача также решается разбиением всей доски на квадраты 3×3 и прямоугольники, состоящие из остальных полей. Для различных n получаются несколько отличные формулы, все зависит от остатка, который получается при делении n на 3. Число расстановок доминирующих королей неизвестно.

Рис. 52. Восемь королей, доминирующих на шахматной доске

Итак, насколько смогли, мы заполнили табл. 2. При этом числа независимости и доминирования на обычной доске найдены для всех фигур. Таким образом, решены обе проблемы (для n = 8), сформулированные в начале главы. Мы нашли также все числа расстановок независимых фигур на доске 8×8; что же касается доминирования, то здесь еще осталось два нерешенных вопроса.

Уникальной является позиция Дьюдени на рис. 53. Здесь одновременно уместились 8 ферзей, 8 ладей и 14 слонов, причем все одноименные фигуры независимы! На доске находится также 21 «мирный» конь, и еще для одного «рекорда» не хватило 11 белых полей, которые, к сожалению, уже заняты.

Если разрешить пешкам стоять на первой и последней горизонталях, то обе наши проблемы станут корректными и для них. Нетрудно проверить, что в этом случае N₈(п) = 32; пешками следует заполнить любые четыре вертикали, лишь бы они не были соседними. Имеем также D₈(п) = 29 - достаточно занять пешками первую горизонталь и вертикали a, d и g.

До сих пор мы рассматривали лишь классические комбинаторные задачи о расстановке фигур. Однако существует множество самых разнообразных и необычных задач такого типа.

Например, если говорить о независимости, то весьма сложными являются задачи о расстановках заданного числа фигур, не обязательно равного N. Вот общая формулировка таких задач.

Сколькими различными способами можно расставить на шахматной доске n×n р независимых фигур (ферзей, ладей, слонов, коней или королей)?

Решения некоторых задач такого типа (для различных фигур и различных значений пир) можно найти у Фабеля и Петровича. Наиболее просто они, как обычно, решаются для ладей, а сложнее всего - для ферзей. Формула для двух независимых ферзей на доске n×n будет получена в следующей главе; у Окунева она приведена также для р = 3, а для четырех ферзей решение еще неизвестно.

В задачах о доминировании можно требовать, чтобы фигуры держали под обстрелом не только свободные поля доски, но и занятые фигурами. Мы уже приводили расстановку пяти «ферзей-часовых», обладающих этим свойством. Восемь ладей, стоящих вдоль одной вертикали и горизонтали, также нападают на все поля доски. Что касается других фигур, то для того, чтобы они атаковали все поля доски, их требуется несколько больше, чем для обычного доминирования. Коней и слонов надо иметь на два больше, соответственно - 14 и 10, а королей - даже на три больше, т. е. только 12 королей в состоянии держать под обстрелом все поля доски. Соответствующие расстановки приведены на рис. 54. Так как поля первой горизонтали никогда не могут быть атакованы пешками, то для них наше задание невыполнимо.

Интересно исследовать также доминирование на шахматной доске различных наборов фигур, не обязательно одноименных. Как мы знаем, пять ферзей справляются с шахматной доской, но меньшим числом фигур обойтись не удается. Любопытно, однако, что двух из пяти ферзей можно заменить более слабыми фигурами - двумя ладьями или даже ладьей и слоном (рис. 55), причем в первой расстановке атакованы все поля доски, включая занятые.

Можно ли расставить на шахматной доске полный комплект фигур (король, ферзь, две ладьи, два слона, два коня) так, чтобы они нападали на все 64 поля доски?

Восемь шахматных фигур могут доминировать на всей доске, но, как это ни странно, лишь в том случае, если слоны одноцветные (рис. 56,а). Если же слоны разного цвета, то при любой расстановке фигур хотя бы одно поле доски не атаковано (на рис. 56,б безопасно поле c1).

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

Нахождение хроматического числа (так же, как и чисел независимости и доминирования) - это не простая задача, а для некоторых классов графов представляет собой чрезвычайно сложную проблему. Достаточно упомянуть знаменитую задачу четырех красок, которая сводится к определений) хроматического числа в графе.

Можно ли произвольную географическую карту раскрасить четырьмя красками так, чтобы любые две соседние страны были окрашены в разный цвет?

Если в каждой стране поместить вершину графа и соединить ребрами все пары вершин, расположенные в соседних странах (они имеют общую границу), мы получим граф географической карты. Его хроматическое число совпадает с минимальным числом красок для раскраски карты. Гипотеза, по которой хроматическое число любого графа географической карты равно четырем, не поддается разрешению уже более ста лет, несмотря на усилия многих выдающихся математиков. Таким образом, на предложенный нами вопрос ответ до сих пор не найден. Известно лишь, что пятью красками можно обойтись всегда.

Что касается графов шахматных фигур, то здесь дело обстоит следующим образом. Для всех фигур, кроме ферзя, хроматические числа находятся без труда, а для ферзя еще не все ясно. Сформулируем теперь задачу о хроматическом числе в шахматных терминах.

Какое минимальное число красок необходимо иметь для раскраски всех полей доски, если любые два поля, связанные ходом данной фигуры (ферзя, ладьи, коня, слона или короля), должны быть окрашены в разные цвета?

Очевидно, при правильной раскраске доски фигуры, стоящие на полях одного цвета, не угрожают друг другу. Поскольку всего шахматных фигур - пять, то мы имеем здесь пять задач о раскраске доски. Меньше всего красок (две) требуется для коней. Собственно, здесь и раскрашивать ничего не надо, достаточно взять обычную шахматную черно-белую доску. Тех же двух красок хватает для раскраски любой доски n×n, а при n, равном 1 или 2, можно ограничиться и одной краской.

В случае слонов и ладей для раскраски обычной доски достаточно восьми красок (а для раскраски доски n×n достаточно n красок). На доске, затянанной слонами, каждую вертикаль можно окрасить в «свой» цвет. Для ладей все поля первой горизонтали нужно окрасить в разные цвета, а для раскраски последующих горизонталей использовать «циклический» сдвиг красок. Другими словами, если краски занумеровать числами от 1 до 8, то окраска первой горизонтали - 1, 2, …, 8; второй - 2, 3, …, 8, 1; третьей - 3, 4, …, 8, 1, 2 и т. д.; восьмой - 8, 7, …, 1.

Переходя к королям, заметим, что для них все четыре поля произвольного квадрата 2×2 должны быть окрашены разными красками. Оказывается, четырех красок хватает и для любой доски n×n (при n = 1 - одна краска). Левый нижний квадрат 2×2 можно произвольно раскрасить в четыре цвета, а затем так же раскрасить соседние квадраты 2×2 и т. д., пока не будет раскрашена вся доска (если n² не делится на 4, то, естественно, числа полей, окрашенных в разные цвета, могут несколько отличаться).

На рис. 57 показана раскраска шахматной доски для ферзей (числа от 1 до 9 соответствуют девяти краскам). Действительно, здесь никакие два одинаковых числа не стоят на одной вертикали, горизонтали и диагонали. Видимо, восьми красок для раскраски доски с ферзями не хватает, хотя точно это еще не установлено (следовало бы прибегнуть к помощи ЭВМ). В общем случае доказано37, что всегда можно раскрасить доску n×n в n + 3 цвета так, чтобы ферзи, стоящие на полях одного цвета, не угрожали друг другу. Для некоторых n достаточно и меньшего числа красок: n, n + 1 или w + 2. В указанной статье предложена также гипотеза, по которой хроматическое число графа ферзей при любом n > 3 равно либо n, либо n + 1.

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

36. Более подробно с приведенными понятиями можно ознакомиться в книге К. Бержа (см. сноску 19), а также в книге О. Оре «Теория графов» (М., «Наука», 1968).

37. М. Iyer, V. Menon. On Coloring the n×n chessboard. - «American Math, MonthJy», 1966, № 7.