КУРСОВАЯ РАБОТА
Тема:
«Решениезадачи о 8 ферзях»
Харьков2007
Цель работы:разработать программу, которая бы наглядно продемонстрировала вариантыразмещения ферзей на шахматной доске, удовлетворяя правилам задачи.
Методисследования: изучение литературы, составление и отладка программ накомпьютере, проверка решений.
Программа размещенияферзей на практике может применяться в в образовательных целях. Также ее можноиспользовать для изучения математической модели поставленной задачи. Ведьзадача особенно интересна, при увеличении размера шахматной доски.
Задача звучитследующим образом:
«Какимиспособами можно расставить на доске восемь ферзей так, чтобы они не угрожалидруг другу, т.е. никакие два не стояли на одной вертикали, горизонтали идиагонали и сколько таких способов?»
/>
Задача овосьми ферзях
Очевидно,больше восьми мирных ферзей (как и ладей) на обычной доске расставитьневозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих другдругу, легко (на рисунке представлены четыре искомые расстановки). Значительнотруднее подсчитать общее число расстановок и вывести их, в чем, собственно, исостоит задача.
Любопытно,что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу.На самом деле, она была впервые поставлена в 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 расстановок. Вот один из таких наборов:
1) см. рис.а;
2) см. рис.б;
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
Запишем числа1, 2, ј, 8 сначала по возрастанию, а затем по убыванию. После этого сложимчисла каждой из этих двух перестановок с числами произвольной перестановкивосьми чисел, например такой – (3, 7, 2, 8, 5, 1, 4, 6): 1, 2, 3, 4, 5, 6, 7, 8
+ 3,7, 2, 8, 5, 1, 4, 6
4,9, 8, 7, 6,5, 4, 3, 2, 1
+ 3,7, 2, 8, 5, 1, 4, 6
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 до 8 дают в результате указанной операции сложения дватаких набора, в каждом из которых все элементы различны?
Задача овосьми ферзях привлекла внимание Гаусса именно в связи с этой чистоарифметической задачей. Оказывается, между решениями этих двух задач существуетвзаимно однозначное соответствие. Другими словами, каждая расстановка восьмиферзей, не угрожающих друг другу, дает решение арифметической задачи, инаоборот. Для выбранной перестановки оба набора состоят из различных чисел, иэто не случайно – она соответствует первой основной расстановке (см. рис. а).
Нетрудновидеть, что при поворотах и отражениях доски одни решения получаются из другихпри помощи простых арифметических операций над координатами полей, занятыхферзями. Анализ этих операций позволяет обнаружить дополнительные свойстварешений, которые мы не станем обсуждать.
Задача об nферзях. На шахматной доске nхn расставить n ферзей так, чтобы они не угрожалидруг другу.
На доске 1х1один ферзь ставится на одно-единственное поле, и решение существует. На доске2х2 один ферзь, где бы ни стоял, нападает на три других поля, и второго ферзяпоставить некуда. На доске 3х3 умещаются только два мирных ферзя. Итак, длядосок 2х2 и 3х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.
Заметим, чтов общем случае n расстановок (решений задачи) могут заполнить при наложении всюдоску nхn только при тех n, которые не кратны двум и трем. Из этого, вчастности, следует, что для обычной доски подобрать восемь расстановок,накрывающих все 64 поля доски, невозможно.
Обобщаяалгебраическое свойство решений задачи о восьми ферзях, получаем, чторасстановка n ферзей (t1, t2, ј, tn) на доске nґn является искомой, если длялюбых i, j (i
Описаниеалгоритма и структуры программы:
В даннойпрограмме реализован рекурсивный метод решения задачи о 8 ферзях.
У нас имеетсяфункция (intput_queen (int x)), которая ставит очередного ферзя на поле и вызывает саму себядля, того чтобы поставить следующего, если очередного ферзя поставить нельзя,то она возвращает управление в функцию, из которой была вызвана, а та в своюочередь пробует поставить своего ферзя в другое место, и опять рекурсивновызвать себя. Когда функция ставит последнего ферзя, то результат расстановкивыводится пользователю.
В самомначале мы вызываем функцию с параметром х равным нулю (нумерация начинается с0), что означает, что она должна поставить первого ферзя. Когда эта функциявозвращает управление главной функции, то это означает, что все вариантынайдены.
Длясохранения положения ферзей используется массив из 8 элементов целочисленноготипа (intqueens[8]).Порядок элемента в этом массиве означает номер ферзя и его x’овую координату,то есть столбец, а его значение – y’овую координату, или строку. Мы используемто свойство, что на одном столбце не могут находиться несколько ферзей.
Дляопределения возможности поставить текущего ферзя мы проверяем в цикле вкоординатной форме не находится ли он на одной из диагоналей («главной» и«побочной») или строке с каждым из ферзей поставленных ранее.
В качествевывода результата используется 2 способа:
1. Формированиеи отображение html страницы с результатами. Этот способ требует прав создания иизменения файлов в каталоге, где она находится. Но он более красивый чемвторой, тем более что он отображается в стандартном браузере Internet Explorer,в котором результаты можно распечатать сохранить куда необходимо и др.
2. Выводрезультатов в консоль программы. Этот способ используется если создать htmlфайл не удалось. Он менее нагляден, и удобен, но работает всегда.
Дляреализации первого способа используется процедура print_htm(), а дляреализации второй – print_console()
Используется также переменная count для хранениятекущего количества найденных результатов.
Процедурыinit() и close() используются для подготовки к работе основного кода программыи для корректного ее завершения соответственно.
Для началаработы с программой надо запустить фаил 8Q.exe после чего запуститьсяпрограмма. Если программе удалось создать htm файл, то она записывает вариантырешения в него и запускает Интернет браузер Internet Explorer с открытойстраницей, сгенерированной программой и содержащей результат работы, либо еслифайл создать не удалось, то выведет в консоль ошибку и результаты работы будутвыводиться непосредственно в консоль. После вывода очередного результатапользователю будет предложено нажать любую кнопку для продолжения работыпрограммы и вывода следующего результата. Когда все результаты будут выведенына экран, программа сообщит об этом и после нажатия на любую кнопку завершится.
программа размещение ферзь шахматный
Приложение 1
Текстпрограммы
#include
#include
#include
#include
using namespace std;
FILE *result;
int opened;
int queens[8], count;
void print_console()
{
cout
cout
cout
cout
for (int i=0; i
{
cout
cout
for (int j=0; j
{
if (j!=queens[i]) cout
}
cout
}
cout
cout
getch();
count++;
}
void print_htm()
{
if (count % 2) fprintf (result, «\n»); else fprintf (result, «\n»);
fprintf (result, «\n»);
for (int i=0; i
{
fprintf (result, «\n»);
for (int j=0; j
{
if (! ((i+j)%2)) fprintf (result, «»); else fprintf (result, «»);
if (j!=queens[i]) fprintf (result, « »); else fprintf(result, «W»);
fprintf (result, «\n»);
}
fprintf (result, «\n»);
}
fprintf (result, «Вариант №%d\n»,count);
fprintf (result, «\n»);
if (count % 2) fprintf (result, «»); else fprintf(result, «»);
count++;
}
int put_queen (int x)
{
if (x==8)
{
if (opened) print_htm(); else print_console();
return 0;
}
for (int y=0; y
{
int can_put=1;
for (int q=0; q
{
if (((queens[q] – y)==(q-x)) || (queens[q]==y) ||((queens[q]+q)==(x+y))) can_put=0;
}
if (can_put)
{
queens[x]=y;
put_queen (x+1);
}
}
return 0;
}
void init()
{
if (! (result = fopen («queens.htm», «w»)))
{
printf («Error creating result file. Result will be displayedin console.\n»);
opened=0;
} else opened=1;
if (opened) fprintf (result, «\
\n\
\n\
Курсовая работа по програмированию\n\
\n\
\n\
\n\
Задача:\n\
Какими способами можно расставить на доске восемь ферзей так,чтобы они не угрожали друг другу, т.е. никакие два не стояли на однойвертикали, горизонтали и диагонали?\
Решения (всего 92):\n\
\n»);
}
void close()
{
if (! opened)
{
cout
getch();
} else
{
fprintf_s (result, « *Эта страница быласгенерирована курсовой программой студента гр. КИ-06–7 Парченко П.В.»);
WinExec («explorer \ «queens.htm\"», SW_SHOW);
fclose(result);
}
}
int main()
{
init();
count=1;
put_queen(0);
close();
return 0;
}