Расстановка ферзей на шахматном поле

Приднестровский государственный университет им. Т.Г. Шевченко

Инженерно-технический  институт

Кафедра «Программное обеспечение вычислительной техники

и автоматизированных систем» 
 

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

по дисциплине «Программирование на языке высокого уровня»

"Расстановка ферзей

на  шахматном поле" 

                                                                            Выполнил

студент гр. 09ВТ1

Полежаев  Дмитрий

                                                                           

                                                                  

                                                                             

                    

                                                                            Проверил

                                                                            доцент

Кирсанова А.В.

                                                                                                                                                       

Тирасполь 2011

     Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

    История шахмат насчитывает не менее полутора тысяч лет. Считается, что игра-прародитель, чатуранга, появилась в Индии не позже VI века нашей эры. По мере распространения игры на Арабский Восток, затем в Европу и Африку, правила менялись. В том виде, который игра имеет в настоящее время, она сформировалась к XV веку, окончательно правила были стандартизованы в XIX веке, когда стали систематически проводиться международные турниры.

    Задача  о восьми ферзях — широко известная  задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого».

    Общее число возможных расположений 8 ферзей на 64-клеточной доске равно 4426165368. Общее число возможных расположений, удовлетворяющих условию задачи, равно 92. В принципе, современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём прямого перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: 16777216 (то есть 8, в 8 степени) вместо 4426165368. Генерируя перестановки, которые являются решениями задачи о восьми ферзях, и затем, проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40320 (то есть 8!).

    Программа, которая сможет расставлять ферзей по всем правилам, позиционируется как интеллектуальная программа. Её можно использовать как наглядное пособие при решении студентами или учениками задачи по расстановке ферзей. Также программа может помочь провести досуг. Наличие инструкции объяснит пользователю, как необходимо расставлять ферзей. 
 
 

 

     1  Техническое задание

     Для выполнения курсовой работы необходимо создать визуальную модель шахматной доски, размером n на n клеток. Необходимо организовать работу рекурсивного алгоритма, который будет выполнять проверку на постановку ферзей. Также необходимо сделать визуальный контроль пользователя за результатом работы алгоритма.

     Основные задачи при разработке приложения по расстановке ферзей на шахматном поле:

• разработка графического интерфейса;
• вывод инструкции для пользователя;
• алгоритм постановки ферзей;
• алгоритм проверки поставленного ферзя;
• алгоритм рекурсии не правильно поставленного ферзя;
• прорисовка поставленных ферзей.

 
 
 
 
 

 

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

Общая схема программы имеет вид, представленный на рисунке 1:

      
 

      

      

    

    

    

    

    

      

      

    

      
 

    

      

    

      
 
 
 
 

Рисунок 1 - Обобщенная функциональная схема программы 

    Алгоритм  постановки ферзей представляет собой следующие методы:

    Метод public void PlaceQueue - в этом методе происходит заполнение массива случайными значениями. Результат работы данного метода – это массив, все элементы которого имеют случайные значение.

    Метод public void DisarrayQueen – этот метод выполняет непосредственно постановку ферзей или возврат к предыдущей постановке, если условие не удовлетворяется.

     Последовательность  работы метода DisarrayQueen:

• запускаем цикл, который будет выполнять сортировку;
• если текущий элемент последний, то сортировка закончена;
• если сортировка закончена, то возвращаемся к PlaceQueue;
• вызываем метод IsSuitablePos,  который проверяет, не бьется ли поставленный ферзь;
• если ферзь поставлен, то редактируем массив.

    Метод public bool IsSuitablePos – метод, проверяющий, «не бьется» ли поставленный ферзь по диагоналям. Строки и столбцы не проверяются, так как новый ферзь ставится только в свободную строку и столбец.

    Метод private void ChangeSize - метод, сохраняющий настройки количества ферзей, указанных пользователем. Если пользователь указал буквы, а не цифры, то при подтверждении он получит сообщение о неправильном вводе.

    Метод private void Clear – метод, очищающий панель для нового поля.

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

    Путём решения было создание изображения, рисуемого программно. Считывались размеры панели, на которой происходило рисование, размеры делились на количество ферзей, указанных пользователем. Затем при помощи метода ShowDesk происходила прорисовка шахматного поля с ферзями. Прорисовка ферзя выглядит схематически. Ферзь на шахматном поле отображается красным кругом. Для того чтобы ферзь был прорисован строго в указанном месте, шахматная доска рисовалась по столбцам, затем рисовался ферзь, и рисование переходило к следующему столбцу. 

Приведем алгоритм метода сохранения настроек количества ферзей, указанных пользователем:

private void ChangeSize(object sender, System.EventArgs e)

            {

                  try

                  {

                        Queens.Queen.CountOfQueens = Int32.Parse(this.SizeDialog.SizeText.Text);

                        this.SizeDialog.Hide();

                  }

                  catch

                  {

                        Queens.Error.ShowError("Нужно вводить цифры");

                        this.SizeDialog.Hide();

                  }

            } 

Также интересным является метод, выполняющий непосредственно  постановку ферзей или возврат к  предыдущей постановке, если условие  не удовлетворяется: 

public void DisarrayQueen(int Y)

            {

                  if ( Y == this.NumOfQueens )

                this.ExitProce = true; //если  текущий элемент  последний, то  сортировка закончена

            if (this.ExitProce == true) return; //если  сортировка закончена, то возвращаемся к PlaceQueue

                  for (int IterX = 0; IterX < this.NumOfQueens; IterX ++)

                if (this.IsSuitablePos(Y, IterX)) //вызываем метод IsSuitablePos

                        {

                              if (!this.ExitProce)

                              {//если  ферзь поставлен,  то редактируем  массив

                                    this.Desk[Y] = IterX;

                                    this.DisarrayQueen(Y + 1);

                              }    }

            }

 

2.1 Общие сведения 

      В последнее время С и С++ являются наиболее используемыми языками для разработки коммерческих и бизнес-приложений. Эти языки устраивают многих разработчиков, но в действительности не обеспечивают должной продуктивности разработки. К примеру, процесс написания приложения на С++ зачастую занимает значительно больше времени, чем разработка эквивалентного приложения, скажем, на Visual Basic. Сейчас существуют языки, увеличивающие продуктивность разработки за счет потери в гибкости, которая так привычна и необходима программистам на С/С++. Подобные решения являются весьма неудобными для разработчиков, и зачастую предлагаются значительно меньшие возможности. Также эти языки не ориентированы на взаимодействие с появляющимися сегодня системами, и очень часто они не соответствуют существующей практике программирования для Web. Многие разработчики хотели бы использовать современный язык, который позволял бы писать, читать и сопровождать программы с простотой Visual Basic и в то же время давал бы мощь и гибкость C++, обеспечивал бы доступ ко всем функциональным возможностям системы, взаимодействовал бы с существующими программами и легко работал бы с возникающими Web стандартами.

      Учитывая  все подобные пожелания, Microsoft разработала  новый язык - C#. В него входит много полезных особенностей - простота, объектная ориентированность, типовая защищенность, "сборка мусора", поддержка совместимости версий и многое другое. Данные возможности позволяют быстро и легко разрабатывать приложения, особенно COM+ приложения и Web сервисы. При создании C# его авторы учитывали достижения многих других языков программирования: C++, C, Java, SmallTalk, Delphi, Visual Basic и т.д. Надо заметить, что по причине того, что C# разрабатывался с чистого листа, у его авторов была возможность (которой они явно воспользовались) оставить в прошлом все неудобные и неприятные особенности (существующие, как правило, для обратной совместимости) любого из предшествующих ему языков. В результате получился действительно простой, удобный и современный язык, по мощности не уступающий С++, но существенно повышающий продуктивность разработок.