Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Подразумевается, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям. Обобщение задачи — расставить максимальное количество взаимно не бьющих друг друга ферзей на прямоугольном поле, в частности, квадратном поле, со стороной n.
Содержание
Формулировка [ править | править код ]
В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8×8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».
Конечная цель, поставленная перед решающим задачу, может формулироваться в нескольких вариантах:
- Построить одно, любое решение задачи.
- Аналитически доказать, что решение существует.
- Определить количество решений.
- Построить все возможные решения.
- Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N×N клеток (при этом при 1 Особенности решения [ править | править код ]
Общее число возможных расположений 8 ферзей на 64-клеточной доске равно 4 426 165 368 = (64!/(8!(64-8)!)). Общее число возможных расположений, удовлетворяющих условию задачи, равно 92. Интересно отметить, что эти 92 расположения разбиваются на 12 групп: 11 групп по 8 и одну из 4 расположений. Положения внутри групп получаются из одного положения путём преобразований симметрии: отражения от вертикальной и горизонтальной осей, отражения от диагоналей доски и поворотов на 90, 180 и 270 градусов. Пары расположений, симметричные относительно горизонтальной оси, имеют сумму номеров, равную 93, то есть для каждой группы эта сумма равна 93×4.
Современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём прямого перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: 16 777 216 (то есть 8 8 ) вместо 4 426 165 368 . Генерируя перестановки, которые являются решениями задачи о восьми ладьях и затем проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40 320 (то есть 8!). Однако, если условие нападения по диагонали учитывать при генерации позиций, скорость счёта возрастает на порядок.
Один из типовых алгоритмов решения задачи — использование поиска с возвратом: первый ферзь ставится на первую горизонталь, затем каждый следующий пытаются поставить на следующую так, чтобы его не били ранее установленные ферзи. Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад — переставляется ранее установленный ферзь.
«Решение задачи о 8 ферзях»
Цель работы: разработать программу, которая бы наглядно продемонстрировала варианты размещения ферзей на шахматной доске, удовлетворяя правилам задачи.
Метод исследования: изучение литературы, составление и отладка программ на компьютере, проверка решений.
Программа размещения ферзей на практике может применяться в в образовательных целях. Также ее можно использовать для изучения математической модели поставленной задачи. Ведь задача особенно интересна, при увеличении размера шахматной доски.
Задача звучит следующим образом:
«Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?»
Задача о восьми ферзях
Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.
Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.
Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.
Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике. В наш век ЭВМ задача такого сорта не вызвала бы столь живой интерес. Ведь достаточно составить несложную программу, и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.
Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам. Например, из расстановки, показанной на рис. а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. в, а при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, – на рис. г. При помощи других поворотов и отражений доски можно получить еще пять решений.
Итак, указанные операции с шахматной доской позволяют из одного расположения мирных ферзей получить, вообще говоря, семь новых. Доказано, что в общем случае на доске nхn (при n > 1) для любой расстановки n мирных ферзей возможны три ситуации:
1) при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается;
2) новое решение возникает при повороте доски на 90°, а ее отражения дают еще две расстановки;
3) три поворота доски и четыре отражения приводят к семи различным расстановкам (а если считать и исходную, то всего имеем восемь позиций).
В случае 1) исходное решение называется дважды симметрическим, в случае 2) – симметрическим, а в случае 3) – простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует.
Набор расстановок восьми мирных ферзей называется основным, если, во-первых, эти расстановки не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи данных преобразований доски. Доказано, что всякий основной набор решений задачи содержит ровно 12 расстановок. Вот один из таких наборов:
3) a4, b1, c5, d8, e6, f3, g7, h2;
4) a4, b2, c5, d8, e6, f1, g3, h7;
5) a4, b2, c7, d3, e6, f8, g1, h5;
6) a4, b2, c7, d3, e6, f8, g5, h1;
7) a3, b5, c2, d8, e6, f4, g7, h1;
8) a4, b1, c5, d8, e2, f7, g3, h6;
9) a4, b7, c3, d8, e2, f5, g1, h6;
10) a6, b4, c2, d8, e5, f7, g1, h3;
11) a4, b8, c1, d5, e7, f2, g6, h3;
12) a4, b2, c7, d5, e1, f8, g6, h3.
Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски. Основная расстановка на рис. б является симметрической, другие одиннадцать основных расстановок – простыми. Итак, всего на доске имеем 11·8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу.
Отметим несколько интересных свойств расстановок мирных ферзей. Симметрическая расстановка на рис. б как ей и положено, обладает внешней симметрией. Она характеризуется также тем, что центральная часть доски (квадрат 4х4) не занята ферзями. Свободны здесь и обе главные диагонали доски (этим свойством обладает и восьмая основная расстановка). В первой расстановке (рис. а) никакие три ферзя не находятся на одной прямой, проведенной через центры полей (имеются в виду не только вертикали, горизонтали и диагонали доски, но и прямые с другими углами наклона).
Всякое решение задачи о восьми ферзях можно записать как набор (t1, t2, ј, t8), представляющий собой перестановку чисел 1, 2, ј, 8. Здесь ti – номер горизонтали, на которой стоит ферзь i-й вертикали. Так как ферзи не стоят на одной горизонтали, то все числа ti различны, а поскольку ферзи не стоят и на одной диагонали, то для любых i, j (i 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.
Заметим, что в общем случае n расстановок (решений задачи) могут заполнить при наложении всю доску nхn только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.
Обобщая алгебраическое свойство решений задачи о восьми ферзях, получаем, что расстановка n ферзей (t1, t2, ј, tn) на доске nґn является искомой, если для любых i, j (i
| Главная ≫ Инфотека ≫ Математика ≫ Книги ≫ Глава 8. Задача о восьми ферзях / Математика на шахматной доске // Гик Е. Я. |
|
|
| Комментарии: 0 |
Задача о восьми ферзях, как и задача о ходе коня, является одной из самых знаменитых математических задач на шахматной доске. Если задачей о коне занимался Леонард Эйлер, то задача о ферзях привлекла внимание другого великого математика — Карла Гаусса. Сколькими способами можно расставить на шахматной доске восемь ферзей так, чтобы они не угрожали друг другу, т. е. никакие два не стояли на одной вертикали, горизонтали и диагонали? Найти ту или иную расстановку ферзей, удовлетворяющую условию задачи, не так трудно (четыре решения приведены на рис. 43). Значительно труднее подсчитать общее число существующих расстановок; собственно, в этом и состоит задача о восьми ферзях. Ясно, что как и в случае ладей, больше восьми не атакующих друг друга ферзей на шахматной доске расставить невозможно. И, соответственно, на доске n×n необходимым образом нельзя расставить более n ферзей (в общем виде задача будет рассмотрена несколько ниже). |
 |
| 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 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 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.
«>