5 Ферзей бьют все поля

Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 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!). Однако, если условие нападения по диагонали учитывать при генерации позиций, скорость счёта возрастает на порядок.

Один из типовых алгоритмов решения задачи — использование поиска с возвратом: первый ферзь ставится на первую горизонталь, затем каждый следующий пытаются поставить на следующую так, чтобы его не били ранее установленные ферзи. Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад — переставляется ранее установленный ферзь.

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	контрольная работа
Язык	русский
Дата добавления	03.06.2014
Размер файла	21,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кемеровский государственный университет»

Кафедра ЮНЕСКО по новым информационным технологиям

ОТЧЕТ ПО СЕМЕСТРОВОЙ РАБОТЕ ПО ДИСЦИПЛИНЕ

“Технологии параллельного программирования”

«Задача о 5 ферзях»

студентки 2 курса

Ладан Людмилы Эдуардовны

Направление 010500.62 — Математическое обеспечение и администрирование информационных систем

• Введение
• 1. Постановка задачи
• 2. Последовательный алгоритм
• 3. Параллельный алгоритм
• З аключение
• Л итература Введение
• Реализовано две версии алгоритма: параллельная и последовательная.
• Основной принцип каждого из алгоритмов следующий: методом перебора на шахматной доске расставляются пять ферзей, таким образом, чтобы все поля были биты, причем второй ферзь всегда стоит после первого, третий всегда после второго и т.д.. За позицию ферзя отвечает соответствующий ему цикл. Программа останавливается, когда ферзи становятся в конечное положение, а именно последние пять полей на доске. В начале и в конце программы ставятся временные метки, считается их разность; полученное значение обозначает время, потраченное на выполнение алгоритма. Запуская параллельную программу на разном количестве процессоров, мы найдем время для каждого из случаев. На основе этих результатов можно будет говорить об ускорении и эффективности.
• 1. Постановка задачи
• Запрограммируйте параллельную программу, реализующую задачу о расстановке пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
• 2. Последовательный алгоритм
• 1. Решение задачи находится полным перебором всех возможных расстановок ферзей на поле.
• 2. Выполняется 5 циклов по i1, i2, i3, i4, i5 (каждый для своего ферзя).
• 3. На каждом шаге цикла ферзи расставляются на поле. Это делается следующим образом:
• · Массив a из 64 элементов сначала обнуляется (для того чтобы подготовить его к новой расстановке ферзей)
• · В массив расставляются ферзи: первый ставится в начало массива, остальные выстраиваются относительно первого. Начальная позиция: заняты первые пять позиций, конечная: заняты последние пять позиций. Элемент массива, куда поставлен ферзь, обозначается за 2. Получаем пять элементов, равных 2, и шестьдесят один элемент, равных 0.
• · Заносим значения массива a[] в матрицу f[][]. В результате получается расстановка ферзей на шахматной доске.
• 4. После расстановки ферзей, помечаем клетки, которые находятся под ударом ферзя. В матрице f «подударные» элементы обозначаем за единицу. Делаем перебор матрицы, если элемент равен 2 (т.е. это ферзь), то заполняем для него подударные элементы (клетки). Это делается в 6 циклах: один для горизонтали, один для вертикали и 4 для диагоналей (вниз и вправо, вверх и влево, вверх и вправо, вниз и влево относительно позиции ферзя).
• 5. После расстановки ферзей и заполнения подударных клеток делаем проверку расстановки. Если есть в матрице нули, то расстановка не верная, т.е. под ударом находятся не все поля, переходим к следующему шагу цикла. Если нет нулей, то к счетчику количества найденных решений qs прибавляем единицу и переходим к следующему шагу цикла.
• Реализация последовательного алгоритма
• #include
• #include
• #include
• #include
• int main () <
• const int LBOX=9; ///длина стороны доски + 1
• const int QCELL=65; ///кол-во клеток на шахматной доске + 1
• const int LD=8; ///длина стороны доски
• const int CH=64; ///кол-во клеток на шахматной доске
• int f[LBOX][LBOX]; ///2х-мерный массив, шахматная доска
• int a[QCELL]; ///одномерный массив
• int i1=1, i2=1, i3=1, i4=1, i5=1; ///счетчики для каждого ферзя
• int i, j, k, l, m; ///счетчики
• int qzero=0, qs=0; ///кол-во нулей в матрице f и кол-во найденных решений
• double t1, t2; /// начальное и конечное время
• t1 = clock();
• for ( i1=1; i1 =1) && (j-m>=1) )
• f[i-m][j-m] = 1; ///заполняем диагональ вверх-влево единицами
• for ( m=1; m =1) && (j+m =1) )
• f[i+m][j-m] = 1; ///заполняем диагональ вниз-влево единицами
• >
• >
• >
• qzero = 0;
• ///теперь ищем нули (т.е. клетки, непопавшие под удар ни одного из ферзей)
• for ( i=1; i

Содержание

Введение

На олимпиадах по программированию часто встречается задача размещения 8 ферзей на шахматной доске: нужно написать такой алгоритм, в котором 8 ферзей помещаются на шахматной доске (размер 8×8) таким образом, что они не бьют друг друга. Простейший вариант решения данной задачи есть реализация полного перебора для 8 вложенных циклов с соответствующими проверками на пересечение по диагонали и вертикали. Но этот вариант не является пригодным для задачи, в которой количество ферзей составляет N , а размер доски составляет N×N .

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

Условие задачи

Задано целое число N ( N>0 ), определяющее количество ферзей на доске размером N×N . Разработать программу, которая находит все возможные варианты размещения N ферзей таким образом, чтобы они не «били» друг друга. В программе обеспечить визуализацию каждого полученного варианта.

Задачу реализовать как приложение типа Windows Forms Application с использованием языка программирования C++.

Соображения

Для приложения типа Visual C++ — Windows Forms система Microsoft Visual Studio предоставляет соответствующие элементы управления с целью удобной визуализации полученных вариантов размещений.

Для визуализации доски размером N×N хорошо подходит элемент управления типа DataGridView . В этом элементе управления можно отображать данные как из базы данных, так и непосредственно в виде двумерной таблицы.

Перечень полученных вариантов в виде координат ( x1 , y1 ), ( x2 , y2 ), …, ( xN , yN ) можно сохранить в элементе управления ListBox , который представляет собой динамический список произвольного размера.

При выборе варианта в ListBox автоматически будет отображаться размещение в DataGridView .

Выполнение

1. Особенности реализации алгоритма решения задачи

1.1. Использование дополнительного массива для описания размещения ферзей на доске

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

Для обеспечения полного перебора вариантов, в работе используется дополнительный одномерный массив M размерностью N+1 . Элемент массива с индексом 0 ( M[0] ) не используется с целью обеспечения удобства при оперировании индексами массива.

В массиве M координаты размещаемых ферзей формируются по следующему принципу:

• координате x ферзя с номером k ( k = 1..N ) соответствует значение M[k] ;
• координате y ферзя с номером k ( k = 1..N ) соответствует само значение k .

На рисунке 1 схематично изображен вариант размещения для N=5 на доске размером 5×5 и вид массива M

Рисунок 1. Интерпретация значений элементов массива M для доски размером 5×5

Как видно из рисунка, индексы массива M соответствуют координате y доски, а значение M[i] по данному индексу соответствует координате x доски:

Массив M заменяет полный перебор, который может быть сформирован с помощью N вложенных циклов.

1.2. Описание работы алгоритма

Вся работа алгоритма базируется на формировании некоторого размещения ферзей с помощью массива M . Номер ферзя, который размещается сохраняется в некоторой переменной-указателе, например, с именем p. В зависимости от ситуации, указатель p двигается вправо ( p++ ) или влево ( p— ) как изображено на рисунке 2 для 5 ферзей. Итак, указатель p определяет номер ферзя, который размещается и координату y . Значение M[p] определяет координату x размещаемого ферзя с номером p .

При изменении значения указателя постоянно проверяется условие p=N , которое значит, что размещается последний ферзь. Если p=N и нет наложений между ферзями в текущем размещении, то это размещение фиксируется. В нашем случае размещение фиксируется в списке ListBox в виде строки специального формата. Если p , то определяются следующие изменения указателя p (номер размещаемого ферзя) или M[p] в зависимости от того, есть ли наложение для текущего количества ферзей и их размещения.

Условием окончания итерационного процесса есть получение всех возможных вариантов. При этом, указатель p двигается влево к элементу, который следует перед первым, то есть к нулевому элементу.

На рисунке 2 изображены разные варианты (состояния) массива M на основе указателя p для N=5 . Выделяются:

• 1 — начальное состояние. Это есть состояние массива M , при котором начинается итерационный процесс;
• 2 — промежуточное состояние. Это есть некоторый промежуточный вариант размещения, когда еще не все ферзи размещены и размещается k -й ферзь ( k=1..N );
• 3 — вариант размещения – это вариант массива M , в котором сформированно искомое размещение (случай, когда все N ферзей не бьют друг друга);
• 4 — окончание итерационного процесса ( p=0 ). Итерационный процесс завершается, если после перебора всех возможных вариантов указатель p двигается влево ( p— ) и становится равным 0.

Рисунок 2. Массив M и его состояния при формировании размещения с помощью указателя p: 1) начальное состояние; 2) промежуточное состояние; 3) искомое размещение; 4) условие окончания итерационного процесса

2. Разработка программы

2.1. Запустить Microsoft Visual Studio. Создать проект по шаблону Windows Forms Application — C++

Загрузить систему Microsoft Visual Studio (любой версии) и сохранить проект. Подробный пример создания проекта по шаблону Windows Forms Application можно просмотреть здесь .

Имя проекта можно задать произвольным, например, PlacementNQueens . В результате будет создана пустая форма проекта.

2.2. Проектирование формы приложения

2.2.1. Размещение элементов управления на форме

Из панели ToolBox разместить на форме приложения следующие элементы управления:

• четыре элемента управления типа Label для отображения информационных сообщений. В результате будут созданы три экземпляра (объекты) типа Label , которые имеют имена label1 , label2 , label3 , label4 . Один из этих элементов управления будет отображать количество вариантов размещений;
• один элемент управления типа TextBox . Создается экземпляр (объект) с именем textBox1 ;
• один элемент управления типа ListBox . Создается экземпляр с именем listBox1 ;
• один элемент управления типа DataGridView . Создается экземпляр с именем dataGridView1 . Этот элемент управления будет отображать доску в форме таблицы;
• один элемент управления типа Button . Создается экземпляр с именем button1 . Этот элемент управления будет запускать на выполнение процесс поиска размещений для заданного N .

На рисунке 3 отображена форма приложения после размещения элементов управления.

Рисунок 3. Форма приложения после размещения элементов управления

2.2.2. Настройка элементов управления формы

На этом этапе нужно настроить следующие свойства элементов управления:

• в элементе управления label1 свойство Text = «N = « ;
• в label2 свойство Text = «Placements» ;
• в label3 свойство Text = «Current placement» ;
• в label4 свойство Text = «Number of placements = « ;
• в button1 свойство Text = «Start» ;
• в элементе управления Form1 свойство Text = «Placement of N Queens» .

После настройки элементов управления и корректировки их размеров, форма приложения будет иметь приблизительный вид как показано на рисунке 4.

Рисунок 4. Форма приложения после настройки

3. Написание программного кода

3.1. Текст модуля Form1.h

После создания проекта, весь программный код будет набираться в модуле Form1.h . На данный момент текст модуля формы имеет следующий вид:

3.2. Объявление внутренней переменной N (количество ферзей)

В текст класса вводится внутренняя скрытая ( private ) переменная N , которая определяет количество ферзей для размещения а также размеры доски

После ввода N, вид класса формы Form1 следующий:

3.3. Метод IsStrike() . Проверка того, бьются ли два ферзя с разными координатами

В текст класса Form1 вводится метод IsStrike() . Метод служит основой проверки на накладывание. Метод проверяет, «бьются» ли два ферзя с разными координатами. Метод получает 4 целочисленных параметра:

• x1 , y1 – координаты первого ферзя;
• x2 , y2 – координаты второго ферзя.

Метод возвращает true , если два ферзя «бьют» друг друга. В методе происходит проверка как по горизонтали, так и по вертикали.

Метод должен быть размещен в классе Form1 после директивы

Листинг метода в классе Form1 следующий

3.4. Метод Strike() . Проверка наложения размещаемого ферзя с предшествующими (уже размещенными) ферзями

Метод Strike() предназначен для проверки координат ферзя, который размещается с координатами ранее размещенных ферзей, которые между собой не накладываются.

Метод получает входящими параметрами массив M и указатель p (см. п.п. 1.2-1.3). В массиве M помещается информация о:

• координатах ферзей, которые рассматриваются как размещенные и которые не накладываются;
• указатель p , представляющий номер размещаемого ферзя. Значит, координата M[p] есть координатой x текущего ферзя, который размещается. Координата p есть координатой y текущего ферзя, который размещается.

Метод проверяет, накладывается ли ферзь с координатами, которые соответствуют позиции p , с ферзями, которые размещены в позициях 1, 2, … , p-1 .

Метод должен быть размещен в классе формы Form1 после метода IsStrike() . Листинг метода следующий:

3.5. Методы обеспечивающие отображение размещения ферзей в dataGridView1

3.5.1. Метод InitDataGridView() . Инициализация и настройка элемента управления dataGridView1

Элемент управления dataGridView1 используется для отображения размещения записанного в listBox1 . В методе InitDataGridView() реализована начальная инициализация dataGridView1 программным путем. Метод получает входным параметром значение N .

Метод должен быть помещен после метода Strike() . Листинг метода InitDataGridView() следующий

3.5.2. Отображение строки из listBox1 в dataGridView1 . Метод ShowDataGridView()

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

Метод ShowDataGridView() предназначен для обработки выделенной строки в listBox1 и визуализации координат ферзей, представленных в этой строке. Сформированные в виде строки координаты ферзей визуализируются в dataGridView1 .

Метод получает входными параметрами:

• строку s , в которой помещаются пары координат ферзей для полученных размещений;
• количество ферзей N .

Текст метода размещается после метода InitDataGridView() .

Листинг метода ShowDataGridView() следующий

3.6. Методы работи с listBox1

3.6.1. Добавить размещения в listBox1 в формате строки. Метод AddToListBox()

Метод AddToListBox() выполняет следующие операции:

• конвертирует размещение, описанное в строках массива M в строку типа string ;
• добавляет сформированную строку к списку в listBox1 .

Пример строки s типа string для N=5 и массива M , изображенного на рисунке 1 :

Текст метода помещается после метода ShowDataGridView() . Листинг метода AddToListBox() в тексте формы Form1 следующий:

3.6.2. Программирование обработчиков событий Click и KeyUp элемента управления listBox1

В элементе управления listBox1 формируется перечень строк, которые соответствуют полученным размещениям N ферзей на доске размером N×N . В программе нужно обеспечить визуализацию в dataGridView1 выделенной в listBox1 строки. Для того, чтобы пользователь мог удобно пересматривать полученные размещения в dataGridView1 , нужно запрограммировать обработчики событий Click и KeyUp элемента управления listBox1 .

В данной теме не рассматривается подробный процесс программирования обработчиков событий Click и KeyUp , поскольку он осуществляется стандартным способом. Более подробный пример того, как программируется обработчик события в Microsoft Visual Studio описывается в теме:

Обработчики событий размещаются после метода AddToListBox() . Листинг обработчиков событий Click и KeyUp элемента управления listBox1 следующий:

3.7. Программирование события Click на кнопке Start . Реализация алгоритма поиска размещений

При нажатии клавиши Start пользователь должен получить перечень вариантов размещения N ферзей. Все это осуществляется в обработчике события Click , который вызывается при нажатии на кнопке Start .

В обработчике события реализуется алгоритм, который описан в п. 1.3.

Листинг обработчика события следующий:

3.8. Итоги программного кода

В программе введена внутренняя переменная N (количество ферзей и размер доски).

В программе (в классе Form1 ) реализованы следующие методы:

• метод IsStrike() – проверяет, бъются ли две координаты по диагонали и по вертикали;
• метод Strike() – проверяет «бьется» ли заданный ферзь с предварительно размещенными ферзями;
• метод InitDataGridView() – осуществляет начальную инициализацию элемента управления dataGridView1 в зависимости от значения N ;
• метод ShowDataGridView() – отображает описанное размещение из входной строки s в dataGridView1 ;
• метод AddToListBox() – преобразовывает размещение из массива M в строку специального формата s и добавляет эту строку в список listBox1 ;
• два метода – обработчики событий listBox1_Click() и listBox1_KeyUp() , которые позволяют удобно пересматривать размещения при изменении выделенной строки в listBox1 ;
• обработчик события button1_Click() клика на кнопке Start – реализует основной алгоритм размещения.

4. Запуск программы на выполнение. Тестирование работы

Результат выполнения программы показан на рисунке 5. Можно задавать разные значения N . Если значение N задать достаточно большое ( N>13 ), то для получения решения придется нужно время.

Рисунок 5. Результат работы программы для количества ферзей N=7 . Количество вариантов размещений равно 40