Решение задачи о 8 ферзях

КУРСОВАЯ РАБОТА

Тема:

«Решение задачи о 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 < j Ј 8) имеем: |tj-ti| № 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 < j Ј n) имеет место: |tj-ti| № j-i. Таким образом, задача об n ферзях сводится к чисто математической задаче о нахождении перестановки чисел 1, 2, ј, n, удовлетворяющей указанному условию. Известно много решений этой задачи, некоторые из них опубликованы в серьезных математических журналах. Один из методов расстановки n ферзей, не угрожающих друг другу на произвольной доске nґn (n і 5), можно найти в книге «Математика на шахматной доске».

Описание алгоритма и структуры программы:

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

У нас имеется функция (int put_queen (int x)), которая ставит очередного ферзя на поле и вызывает саму себя для, того чтобы поставить следующего, если очередного ферзя поставить нельзя, то она возвращает управление в функцию, из которой была вызвана, а та в свою очередь пробует поставить своего ферзя в другое место, и опять рекурсивно вызвать себя. Когда функция ставит последнего ферзя, то результат расстановки выводится пользователю.

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

Для сохранения положения ферзей используется массив из 8 элементов целочисленного типа (int queens[8]). Порядок элемента в этом массиве означает номер ферзя и его x’овую координату, то есть столбец, а его значение – y’овую координату, или строку. Мы используем то свойство, что на одном столбце не могут находиться несколько ферзей.

Для определения возможности поставить текущего ферзя мы проверяем в цикле в координатной форме не находится ли он на одной из диагоналей («главной» и «побочной») или строке с каждым из ферзей поставленных ранее.

В качестве вывода результата используется 2 способа:

1. Формирование и отображение html страницы с результатами. Этот способ требует прав создания и изменения файлов в каталоге, где она находится. Но он более красивый чем второй, тем более что он отображается в стандартном браузере Internet Explorer, в котором результаты можно распечатать сохранить куда необходимо и др.

2. Вывод результатов в консоль программы. Этот способ используется если создать html файл не удалось. Он менее нагляден, и удобен, но работает всегда.

Для реализации первого способа используется процедура print_htm(), а для реализации второй – print_console()

Используется также переменная count для хранения текущего количества найденных результатов.

Процедуры init() и close() используются для подготовки к работе основного кода программы и для корректного ее завершения соответственно.

Для начала работы с программой надо запустить фаил 8Q.exe после чего запуститься программа. Если программе удалось создать htm файл, то она записывает варианты решения в него и запускает Интернет браузер Internet Explorer с открытой страницей, сгенерированной программой и содержащей результат работы, либо если файл создать не удалось, то выведет в консоль ошибку и результаты работы будут выводиться непосредственно в консоль. После вывода очередного результата пользователю будет предложено нажать любую кнопку для продолжения работы программы и вывода следующего результата. Когда все результаты будут выведены на экран, программа сообщит об этом и после нажатия на любую кнопку завершится.

программа размещение ферзь шахматный

Приложение 1

Текстпрограммы

#include <iostream>

#include <conio.h>

#include <iomanip>

#include <windows.h>

using namespace std;

FILE *result;

int opened;

int queens[8], count;

void print_console()

{

cout <<»–=============–n»;

cout <<» Version #» <<count << «n»;

cout <<» –===========–n»;

cout <<» a b c d e f g h n»;

for (int i=0; i<8; i++)

{

cout <<» +-+-+-+-+-+-+-+-+ n»;

cout <<» " <<8-i;

for (int j=0; j<8; j++)

{

if (j!=queens[i]) cout << "|»; else cout << "|W»;

}

cout << "|» <<8-i <<»n»;

}

cout <<» +-+-+-+-+-+-+-+-+ n»;

cout <<» a b c d e f g h nn Press any key to continue…n»;

getch();

count++;

}

void print_htm()

{

if (count % 2) fprintf (result, «<tr><td align= «center">n»); else fprintf (result, «<td align= «center">n»);

fprintf (result, «<table border= «0» width= «100%» cellspacing= «0» cellpadding= «0">n»);

for (int i=0; i<8; i++)

{

fprintf (result, «<tr>n»);

for (int j=0; j<8; j++)

{

if (! ((i+j)%2)) fprintf (result, «<td bgcolor= «#FFFFFF»>»); else fprintf (result, «<td bgcolor= «#999999»>»);

if (j!=queens[i]) fprintf (result, «&nbsp;»); else fprintf (result, «<font size= «6» style= «bold">W</font>»);

fprintf (result, «</td>n»);

}

fprintf (result, «</tr>n»);

}

fprintf (result, «<tr><td align= «center» colspan= «8"><font size= «4» style= «bold»>Вариант №%d</font></td></tr>n», count);

fprintf (result, «</table><br><br>n»);

if (count % 2) fprintf (result, «</td>»); else fprintf (result, «</td></tr>»);

count++;

}

int put_queen (int x)

{

if (x==8)

{

if (opened) print_htm(); else print_console();

return 0;

}

for (int y=0; y<8; y++)

{

int can_put=1;

for (int q=0; q<x; 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 displayed in console.n»);

opened=0;

} else opened=1;

if (opened) fprintf (result, «

<html>n

<head>n

<title>Курсовая работа по програмированию</title>n

<meta http-equiv='content-type' content='text/html; charset=windows-1251' />n

</head>n

<body bgcolor= «#FFFFFF»>n

<p><h2>Задача:</h2><br/>n

Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали?</p>

<br><h2>Решения (всего 92):</h2><br>n

<table border= «0» width= «100%%» cellspacing= «0» cellpadding= «0">n»);

}

void close()

{

if (! opened)

{

cout << «That's all. Enjoy…»;

getch();

} else

{

fprintf_s (result, «</table> *Эта страница была сгенерирована курсовой программой студента гр. КИ-06–7 Парченко П.В.»);

WinExec («explorer «queens.htm"», SW_SHOW);

fclose(result);

}

}

int main()

{

init();

count=1;

put_queen(0);

close();

return 0;

}