Глава 8. Задача о восьми ферзях

Задача о восьми ферзях, как и задача о ходе коня, является одной из самых знаменитых математических задач на шахматной доске. Если задачей о коне занимался Леонард Эйлер, то задача о ферзях привлекла внимание другого великого математика - Карла Гаусса.

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

Найти ту или иную расстановку ферзей, удовлетворяющую условию задачи, не так трудно (четыре решения приведены на рис. 43). Значительно труднее подсчитать общее число существующих расстановок; собственно, в этом и состоит задача о восьми ферзях. Ясно, что как и в случае ладей, больше восьми не атакующих друг друга ферзей на шахматной доске расставить невозможно. И, соответственно, на доске n×n необходимым образом нельзя расставить более n ферзей (в общем виде задача будет рассмотрена несколько ниже).

Любопытно, что многие авторы ошибочно приписывают задачу о восьми ферзях и ее решение самому Гауссу. На самом деле первым ее сформулировал в 1848 г. немецкий шахматист М. Беццель. Доктор Ф. Наук (слепой от рождения) нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс увлекся задачей и нашел 72 решения, которые сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук (он привел их в упомянутой газете от 21 сентября 1850 г.). Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом, который в своих книгах немало места уделил рассматриваемой задаче.

Доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей).

В принципе, расставляя на доске восемь ферзей всевозможными способами, мы в конце концов найдем все устраивающие нас расстановки. Однако этот путь чересчур долог и скучен. Можно ограничиться только решениями соответствующей задачи о ладьях и отобрать среди них такие, в которых никакая пара ладей не стоит па одной диагонали. Но и в этом случае перебор довольно велик (понадобятся, как мы знаем, более 40000 попыток). Таким образом, при решении задачи «вручную» (а именно так поступали в прошлом веке) вынужденный перебор расстановок должен быть хорошо продуман. Известно много способов организовать более или менее разумный поиск искомых расположений ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике (в основном в прошлом столетии и начале нынешнего). В наш век вычислительных машин задача такого сорта не смогла бы вызвать столь живой интерес. Ведь достаточно составить несложную программу для ЭВМ - и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.

Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски вокруг центра на 90, 180 и 270° по часовой стрелке (поворот на 360° приводит к исходной позиции). Из данной расстановки ферзей новую можно получить также зеркальным отражением доски относительно одной из пунктирных прямых на рис. 43 (1-я позиция)35. Например, из первой расстановки на этом рисунке при повороте доски на 90° мы получаем третью, а при отражении относительно линии, разделяющей королевский и ферзевый фланги, - четвертую. При помощи других поворотов и отражений можно получить еще пять решений.

Итак, при поворотах и отражениях доски из одной расстановки ферзей получаются, вообще говоря, семь новых. Доказано, что в общем случае на доске n×n (при n > 1) для любой расстановки n ферзей, не угрожающих друг другу, возможны лишь три ситуации: а) при одном отражении доски получается новая расстановка, а повороты и другие отражения ничего нового не дают; б) новое решение получается при повороте доски на 90°, а отражения дают еще две расстановки; в) все три поворота и четыре отражения доски приводят к восьми несовпадающим расстановкам (включая исходную).

В случае а) исходное решение называется дважды симметрическим, в случае б) - симметрическим, а в случае в) - простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует. Алгебраическую интерпретацию решений каждого класса можно найти у Окунева.

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

1)a4, b1, c5, d8, e6, f3, g7, h2; 2)a4, b2, c5, d8, e6, f1, g3, h7; 3)a4, b2, c7, d3, e6, f8, g1, b5; 4)a4, b2, c7, d3, e6, f8, g5, h1; 5)a3, b5, c2, d8, e6, f4, g7, h1; 6)a3, b7, c2, d8, e5, f1, g4, h6; 7)a4, b7, c3, d8, e2, f5, g1. h6; 8)a6, b4, c2, d8, e5, f7, g1. h3; 9)a4, b8, c1, d5, e7, f2. g6, h3; 10)a4, b2, c7, d5. e1. f8. g6, h3; 11)1-я позиция на рис. 43; 12)2-я позиция на рис. 43.

Остальные 80 позиций получаются из этих двенадцати в результате поворотов и отражений доски. Первые 11 расстановок являются простыми, и лишь последняя - симметрической. Таким образом, всего на доске существует 11×8 + 1×4 = 92 расстановки восьми ферзей, не угрожающих друг другу.

Рассматривая основные расстановки, можно обнаружить те или иные интересные особенности их. Например, легко заметить внешнюю симметрию последней расстановки (2-я позиция на рис. 43). Это основное решение, единственное в своем роде, характеризуется также тем, что только у него центральная часть доски (квадрат 4×4) свободна от ферзей. Еще одно его свойство состоит в том, что ферзями не занята главная диагональ доски a1 - h8 (этим свойством обладает и первое основное решение).

Первая расстановка на рис. 43 любопытна тем, что здесь никакие три ферзя не стоят на одной прямой, проведенной через центры полей (имеются в виду не только вертикали, горизонтали и диагонали доски* но и прямые с другими углами наклона).

Всякое решение задачи можно записать, как набор (t1, t2, … t8), представляющий собой перестановку чисел 1, 2, …, 8. Здесь ti - номер горизонтали, на которой стоит ферзь i-й вертикали. Так как никакие два ферзя не находятся на одной горизонтали, то все tx различны, а поскольку ферзи не стоят и на одной диагонали, то для любых i, j (i < j ≤ 8) имеем: |tj - ti| ≠ j - i.

Числовая запись расстановок ферзей иногда бывает очень удобной. Например, для нахождения расстановок при фиксированном расположении ферзя на a1 достаточно из всех 92 позиций, записанных в числовой форме, отобрать такие, у которых первая координата равна 1. Если фиксировано положение ферзя на d3, то следует выделить позиции, у которых на четвертом месте стоит число 3, и т. д.

Запишем числа 1, 2, …, 8 сначала по возрастанию, а потом по убыванию. После этого сложим числа каждой из этих двух перестановок с числами произвольной перестановки, например (3, 7, 2, 8, 5, 1, 4, 6):

+ 1,2,3,4,5,6,7,8 + 8,7,6,5,4,3,2,1 3,7,2,8,5,1,4,6 3,7,2,8,5,1,4,6 4,9,5,12,10,7,11,14 11,14,8,13,9,4,6,7

Полученные суммы образуют два набора чисел: (4, 9, 5, 12, 10, 7, 11, 14) и (11, 14, 8, 13, 9, 4, 6, 7). Возникает следующая задача.

Какие перестановки чисел 1, 2,…, 8 дают в результате указанной операции сложения два таких набора, в каждом из которых все числа различны?

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

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

Задача о n ферзях. На шахматной доске n×n расставить n ферзей так, чтобы они не угрожали друг другу.

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

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

На доске 4×4 существует единственная основная расстановка, причем дважды симметрическая (a2, b4, c1, d3), т. е. всего здесь имеется два решения. На доске 5×5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4; всего же имеется десять искомых позиций. Интересно, что из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполнят все поля доски 5×5. Аналогичное наложение в общем случае возможно только при тех и, которые не делятся ни на 2, ни на 3. Из этого, в частности, следует, что для обычной доски подобрать восемь решепий, для которых ферзи заполняют всю доску, невозможно.

Обобщая указанное выше алгебраическое свойство решений задачи о восьми ферзях, получаем, что расстановка (t1, t2, … tn) n ферзей на доске n×n является искомой, если для любых i, j (i < j < n): |tj - ti| ≠ j - i. Здесь по-прежнему ti - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t1, …, tn есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

Сейчас мы опишем одну возможную схему искомого расположения n ферзей на доске n×n при всех n > 5. Доказательство того, что в полученных расстановках наше условие выполняется, можно найти, например, у Окунева или у Ягломов.

Рассмотрим последовательно ряд случаев. Пусть сначала n четно, причем n = 6k или n = 6k + 4. Половину всех ферзей поставим на первых n/2 вертикалях ходом коня, начиная со второй горизонтали и передвигаясь каждый раз на 2 поля вверх и на 1 вправо. Вторую половину поставим на оставшихся n/2 вертикалях тем же способом, но начиная с первой горизонтали. Для доски 6×6 (n = 6k, k = 1) это дает такую расстановку ферзей: a2, b4, c6, d1, e3, f5 (решение, представленное на рис. 45 для n = 10, получается иным образом).

При n = 6k + 2 предыдущий прием уже не проходит, и ферзей приходится расставлять более «хитрым» способом. Расположим их ходом коня со второй вертикали по

(n/2 - 2)-ю, начиная с третьей горизонтали, и далее с

(n/2 + 3)-й вертикали по (n - 1)-ю, начиная с шестой горизонтали. В результате свободными останутся шесть вертикалей и шесть горизонталей доски, на которых шесть ферзей должны занять поля с такими координатами: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). При n = 14 (n = 6k + 2, k = 2) получаем расстановку на рис. 44. Кстати, на обычной доске 8×8 (8 = 6k + 2, к = 1) расстановка восьми ферзей указанным способом совпадает все с тем же замечательным решением на рис. 43 (2-я позиция), но заметить закономерность расположения ферзей здесь вряд ли возможно.

Нам осталось рассмотреть задачу для нечетных значений n. Чтобы получить решение в этом случае, достаточно заметить, что в предложенных нами расстановках на «четных» досках главная диагональ (идущая из левого нижнего угла в правый верхний) оставалась свободной. Учитывая это обстоятельство, искомую расстановку n ферзей на доске n×n (при нечетном n) можно получить следующим образом. На вертикалях и горизонталях этой доски с номерами от 1 до (n - 1) расставим (n - 1) ферзя так, как это делается на доске (n - 1)×(n - 1) (n - 1 четно!), а затем n-то ферзя расположим в правом верхнем углу доски. Описанным способом можно получить первую расстановку ферзей на доске 5×5 из указанной расстановки на доске 4×4, а из расстановки ферзей на доске 6×6 имеем следующую для n = 7: a2, b4, c6, d1, e3, f5, g7.