x, y, z

Глава 8. Задача о восьми ферзях / Математика на шахматной доске

Гик Е. Я.

Комментарии: 0
<<< |1|…|7|8|9|10|11|12|13|14|15|…|19| >>>

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

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

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

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 43. Восемь ферзей, не угрожающих двуг другу на шахматной доске

Любопытно, что многие авторы ошибочно приписывают задачу о восьми ферзях и ее решение самому Гауссу. На самом деле первым ее сформулировал в 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.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 44. Задача об n ферзях

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 45. Десять ферзей-магарадж, не угрожающих друг другу на доске 10×10

Таблица 1
n123456789101112
Число решений1--21044092352724268014200

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

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

Оказывается, что восемь магарадж, не атакующих друг друга, расставить на доске 8×8 невозможно. Проанализировав все 12 приведенных выше основных расстановок, мы легко убедимся, что всякий раз по меньшей мере три пары ферзей связаны между собой ходом коня. На доске 9×9 девять наших мощных фигур также не могут находиться в безопасности. И лишь на доске 10×10 можно расставить десять «мирных» магарадж. При этом имеется всего одно основное решение, показанное на рис. 45, где ферзи играют роль магарадж.

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

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

Оказывается, что если на обычной доске имеется 92 искомые расстановки, то на цилиндрической уже нет ни одной! Докажем это, считая, что такая доска получается в результате склеивания вертикальных краев (см. рис. 68,а).

 
187
 
286
 
385
 
484
 
583
 
682
 
781
 
888
 
178
 
277
 
376
 
475
 
574
 
673
 
772
 
871
 
161
 
268
 
367
 
466
 
565
 
664
 
763
 
862
 
152
 
251
 
358
 
457
 
556
 
655
 
754
 
853
 
143
 
242
 
341
 
448
 
547
 
646
 
745
 
844
 
134
 
233
 
332
 
431
 
538
 
637
 
736
 
835
 
125
 
224
 
323
 
422
 
521
 
628
 
727
 
826
 
116
 
215
 
314
413
 
512
 
611
 
718
 
817
Рис. 46. Задача о восьми ферзях на цилиндрической доске

Возьмем обычную шахматную доску, помня о том, что ее края склеены. Это означает, в частности, что ферзь с d1 может пойти на a4 и далее, не останавливаясь, через b5 на e8 (этот путь показан стрелкой на рис. 46), и, значит, поля d1 - a4 и b5 - e8 составляют одну диагональ. Запишем на каждом поле доски три цифры, совпадающие, соответственно, с номерами вертикали, горизонтали и диагонали, проходящих через это поле. Рассматриваются диагонали, параллельные стрелкам на рис. 46, здесь же показана выбранная нами нумерация диагоналей.

Если восемь ферзей не угрожают друг другу, то на восьми полях, занимаемых ими, все первые цифры различны и, значит, образуют полный набор чисел 1, 2, …, 8. То же утверждение справедливо для вторых и для третьих цифр. Итак, сумма всех 24 цифр, стоящих на полях с ферзями, равна (1 + … + 8)×3 = 108. Так как сумма цифр каждого поля делится на 8, то и найденная сумма должна делиться на 8, однако 108 на 8 не делится - противоречие!



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

<<< |1|…|7|8|9|10|11|12|13|14|15|…|19| >>>
Комментарии: 0