Контрольная работа: Решение задачи о 8 ферзях

Остальные 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() используются для подготовки к работе основного кода программы и для корректного ее завершения соответственно.