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

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

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

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

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

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

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

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

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

                                                                            Выполнил

студент гр. 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# разрабатывался с чистого листа, у его авторов была возможность (которой они явно воспользовались) оставить в прошлом все неудобные и неприятные особенности (существующие, как правило, для обратной совместимости) любого из предшествующих ему языков. В результате получился действительно простой, удобный и современный язык, по мощности не уступающий С++, но существенно повышающий продуктивность разработок. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.   Минимальные системные и аппаратные требования

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

• процессор семейства Intel Pentium III 1000 МГц;
• графическая карта VGA  32 Мб;               
• 128 Мб оперативной памяти;                                           
• 3 Мб свободного места на жестком диске;         
• операционная система Windows XP;
• Net.FrameWork 3.

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

    При запуске программы открывается окно, на котором есть панель меню и область для прорисовки шахматного поля и ферзей. Запуск алгоритма производится по нажатию кнопки ButtonApply или через элемент меню menuDequeue. Изменение размера поля производится через форму FormSize.cs, которая вызывается элементом меню menuSize. Просмотр данных о разработчике программы доступен на форме About.cs, вызываемой элементом меню menuAbout. Вызов формы с правилами расстановки ферзей Rules.cs происходит по нажатию на элемент меню menuRules.

    Начало  работы алгоритма по постановке ферзей вызывается нажатием на кнопку ButtonApply. Вызывается метод Queens.Queen.PlaceQueue(), расположенный в файле Queens.cs. Этот метод заполняет массив случайными значениями. Размерность массива равна количеству ферзей. Значения, которые помещаются в массив, выбираются в диапазоне от 0 до N-1, где N – количество ферзей. 

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

    Когда массив из поставленных ферзей поставлен, то возвращаемся к методу PlaceQueensClick. Далее метод Clear очищает панель, на которой происходит прорисовка поля и ферзей. Когда метод Clear закончил свою работу, метод ShowDesk выполняет прорисовку поля и ферзей.

    Метод ShowDesk считывает размеры панели, на которой производится прорисовка, и вычисляет размеры клеток шахматного поля. При помощи библиотеки using System.Drawing и параметра Brush определяем два инструмента - BrQueens и BrNone, где BrQueens прорисовывает ферзей, а BrNone шахматное поле.  
 
 
 
 
 
 
 
 
 
 

4. Руководство пользователя

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

    Рисунок 2 – Главное окно программы 

    Просмотреть данные о разработчике можно, нажав на элемент меню «О программе». Диалоговое окно примет вид: 

    Рисунок 3 – Окно, предоставляющее данные о разработчике 

    Для ознакомления с правилами расстановки  ферзей и возможными схемами размещения надо нажать на элемент меню «Правила». Окно примет вид: 

    Рисунок 4 – Правила расстановки и 12 основных схем 

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

    Рисунок 5 – Изменение размера шахматного поля 
 
 

    Далее на форме появляется графическое  изображение расстановки 

    ферзей: 

    Рисунок 6 – Расстановка ферзей 
Заключение

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

    Задача  о восьми ферзях была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем, который нашел 60 решений. После этого Гаусс заинтересовался задачей и нашел 72 решения. Полный же набор решений, состоящий из 92 позиций, получил Ф. Наук. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.

    Строгое доказательство того, что 92 решения  исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.

    Из  каждого решения задачи о ферзях можно получить ряд других при  помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам.

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

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

Список используемой литературы

1. Лабор В.В. Си шарп: Создание приложений для Windows. - Издательство «Харвест», Минск, 2003. – 384 с.

2. Петцольд, Чарльз. Программирование для Microsoft Windows на C#. Т. 2, перевод с англ., Издательско-торговый дом «Русская редакция»,  М., 2002. -624 с.: ил.

3. Холлингворс, Джерод и Баттерфилд, Дэн. C# Руководство разработчику. БХВ-Петербург, 2007. - 326 с.

4. Шилдт, Герберт. Полный справочник по C#. "Вильяме", М., 2004. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Приложение А

Form.cs: //главная форма

using System;

using System.Drawing;

using System.Collections;

using System.ComponentModel;

using System.Windows.Forms;

using System.Data; 

namespace Queens

{

      /// <summary>

      /// Summary description for Form1.

      /// </summary>

      public class FormQueens : System.Windows.Forms.Form

      {

            private System.Windows.Forms.MainMenu mainMenu;

            private System.Windows.Forms.MenuItem menuItem1;

            public System.Windows.Forms.Button ButtonApply;

            public System.Windows.Forms.Panel Panel;

            public FormSize SizeDialog;

            private System.Windows.Forms.MenuItem menuSize;

        private System.Windows.Forms.MenuItem menuDequeue;

        private MenuItem menuItem2;

        private MenuItem menuRules;

        private MenuItem menuAbout;

        private PictureBox pictureBox1;

        private IContainer components; 

            public FormQueens()

            { 

                  InitializeComponent();

                  this.SizeDialog = new FormSize();

                  this.SizeDialog.buttonOK.Click += new EventHandler(this.ChangeSize);

            }

            protected override void Dispose( bool disposing )

            {

                  if( disposing )

                  {

                        if (components != null)

                        {

                              components.Dispose();

                        }

                  }

                  base.Dispose( disposing );

            } 

            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 ShowDesk()

        {//метод прорисовки шахматного поля с ферзями

                  int DeltaX = this.Panel.Width / (Queens.Queen.CountOfQueens);

                  int DeltaY = this.Panel.Height / (Queens.Queen.CountOfQueens);

                  Graphics Grfx = this.Panel.CreateGraphics();

                  Brush BrQueens = new SolidBrush(Color.Red);

                  Brush BrNone = new SolidBrush(Color.LightGray);

                  for (int IterX = 0; IterX < Queens.Queen.CountOfQueens; IterX ++)

                  {

                        for (int IterY = 0; IterY < Queens.Queen.CountOfQueens; IterY ++)

                        {

                              Grfx.FillRectangle(BrNone, IterX * DeltaX + 1, IterY * DeltaY + 1, DeltaX - 2, DeltaY - 2);

                        }

                        Grfx.FillEllipse(BrQueens, IterX * DeltaX, Queens.Queen.Desk[IterX] * DeltaY, DeltaX, DeltaY);

                  }

            }

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

            {//метод, выводящий окно с изменением размера шахматного поля

                  try

                  {

                        this.SizeDialog.Show();

                  }

                  catch

                  {

                        this.SizeDialog = new FormSize();

                        this.SizeDialog.buttonOK.Click += new EventHandler(this.ChangeSize);

                        this.SizeDialog.Show();

                  }

            }

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

            {

                  this.SizeDialog.Hide();

            }

            private void Clear() //очистка панели для нового поля

            {

                  Graphics Grfx = this.Panel.CreateGraphics();

                  Brush Br = new SolidBrush(this.Panel.BackColor);

                  Grfx.FillRectangle(Br, 0, 0, this.Panel.Width, this.Panel.Height);

            }   

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

            {//вызов метода, выполняющего сортировку

            pictureBox1.Visible = false;

                  Queens.Queen.PlaceQueue();

            this.Clear(); //метод очистки

                  this.ShowDesk(); //метод прорисовки  шахматного поля с ферзями

            } 

        private void menuItem4_Click(object sender, EventArgs e)