48763

Задача о 8 ферзях

Курсовая

Информатика, кибернетика и программирование

Задача состоит в нахождении всевозможных комбинаций расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого

Русский

2013-12-15

142.5 KB

41 чел.

УРАЛЬСКИЙ   ГОСУДАРСТВЕННЫЙ   ГОРНЫЙ   УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАТИКИ

                                      

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

ПО ПРОГРАММИРОВАНИЮ

Задача о 8 ферзях

Студент: Сорокин С

гр. АСУ – 09 – 1

Преподаватель: доц. Дружинин А.В.

                                                   Екатеринбург 2011

Фамилия: Сорокин

Имя: Сергей

Отчество: Анатольевич

группа АСУ – 09 – 1

алгоритмический язык: С#

среда разработки: Microsoft Visual Studio 2010

Формулировка задания

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

Дата выдачи задания:

Дата сдачи отчёта:

Отчёт принял: доцент Дружинин А.В.

              

Оглавление

1) Постановка задачи       4

2) Описание базового класса      4

3) Визуализация        5

4) Пример работы программы      6

5) Листинг         7

6) Литература         13


1) Постано
вка задачи

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

  1.  Описание базового класса

Базовым классом является класс Queens.

   class Queens

   {

       /// <summary>

       /// Размер доски.

       /// </summary>

       public const int BoardSize = 8;

 

       /// <summary>

       /// Позиция ферзя на доске.

       /// </summary>

       private class Pos {

           public int row, col;

 

           public bool placed;

 

           public Pos(int r, int c, bool pl)

           {

               row = r; col = c; placed = pl;

           }

};

 

       /// <summary>

       /// Состояние клетки доски (Queen - клетка занята ферзём, Empty - пустая клетка).

       /// </summary>

       private enum PosState { Queen, Empty };

 

       private PosState[,] board = new PosState[BoardSize, BoardSize];

 

private Stack<Pos> qStack = new Stack<Pos>();

 

/// <summary>

/// Проверить: находится ли позиция под боем?

/// </summary>

private bool IsPosUnderAttack(Pos p)

       {

           int i;

           for (i = 0; i < p.col; i++)

           {

               if (board[p.row, i] == PosState.Queen) return true;

               if (p.row-i-1 >= 0)

                   if (board[p.row-i-1, p.col-i-1] == PosState.Queen)

                       return true;

               if (p.row+i+1 < BoardSize)

                   if (board[p.row+i+1, p.col-i-1] == PosState.Queen)

                       return true;

               //Console.WriteLine("{0}:{1} {2}",  p.col-i-1, p.row-i-1, p.row+i+1);

           }

           return false;

       }

 

       /// <summary>

       /// Получить свободную (не под боем) позицию в столбце col

/// Возвращается номер строки или -1 - при неудаче

/// Просмотр строк начинаем со строки startRow + 1

       /// </summary>

    private int GetFreePos(int col, int startRow)

       {

           for (int r = startRow + 1; r < BoardSize; r++)

               if (!IsPosUnderAttack(new Pos(r, col, false)))

                   return r;

           return -1;

       }

 

       /// <summary>

       /// Получить свободную (не под боем) позицию в столбце col

       /// Возвращается номер строки или -1 - при неудаче

       /// Просмотр строк начинаем со строки 0.

       /// </summary>

       int GetFreePos(int col)

       {

           return GetFreePos(col, -1);

       }

 

       /// <summary>

       /// Инициализация объекта перед решением задачи.

       /// </summary>

       public Queens()

       {

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

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

                   board[i,j] = PosState.Empty;

       }

 

       /// <summary>

       /// Решить задачу.

       /// </summary>

       public bool SolveTask()

       {

           Pos p = new Pos(0, 0, true);

    qStack.Push(p);

    board[0, 0] = PosState.Queen;

    while(qStack.Count > 0) {

        p = qStack.Peek();

               if (p.placed) {  // Предыдущий ферзь установлен - ставим следующий

                   if (p.col < BoardSize-1) {  // Справа от этого ферзя можно попытаться поставить ещё.

                       int r = GetFreePos(p.col+1);

  if (r > -1) { // Ставим нового ферзя справа от старого (есть позиция, которая не под боем).

      qStack.Push(new Pos(r, p.col+1, true));

      board[r, p.col+1] = PosState.Queen;

  }

  else { // Нового ферзя поставить нельзя - производим откат назад

      qStack.Peek().placed = false;   // Из-за этого Pos не может быть структурой

  }

     }

     else {  // В последний столбец был поставлен ферзь - задача решена.

         return true;

     }

               }

 else {  // Корректируем позицию ферзя на котором произошел возврат (если возможно)

     while(true) {

         if (qStack.Count == 0) return false;

         board[qStack.Peek().row, qStack.Peek().col] = PosState.Empty;

                int r = GetFreePos(qStack.Peek().col, qStack.Peek().row);

  if (r > -1) {  // Корректируем позицию ферзя на котором произошел возврат

      qStack.Peek().row = r;

      qStack.Peek().placed = true;

      board[qStack.Peek().row, qStack.Peek().col] = PosState.Queen;

      break;

  }

  else {  // Удаляем последнего ферзя (откорректировать позицию не удалось)

      qStack.Pop();

  }

     }

 }

    }

    return false;

       }

 

       /// <summary>

       ///.

       /// </summary>

 

   }

}

3)Визуализация

При запуске программы пользователь видит шахматную доску, на которыю при нажатии кнопки «расставить» происходит расстановка ферзей

(одна из 92 возможных комбинаций)

Выход – кнопка “Выход”

Литература

1.   Рекурсия, вероятностные алгоритмы.

Макконелл Дж.

2.   Основы современных алгоритмов.

М., Техносфера, 2004 , Корнилов Е.

3.  Программирование шахмат и других логических игр.

СПб., БХВ-Петербург, 2005



4. http://msdn.microsoft.com/ru-ru/vcsharp/


 

А также другие работы, которые могут Вас заинтересовать

8924. Очистка природного газа и переработки кислых газов с получением товарной продукции (серы) на Карачаганакском месторождении 1.08 MB
  Введение Сформировавшемуся в последнее время нефтегазовому комплексу Республики Казахстан отводится ведущая роль в топливно-энергетическом балансе и экономике страны. При нынешних темпах развития производительных сил и освоения углеводородных ресурс...
8925. Отработка заданных режимов системы позиционирования при переменном моменте инерции нагрузки и следующих вариациях параметров объекта 131.5 KB
  Цель работы: Целью работы является отработка заданных режимов системы позиционирования при переменном моменте инерции нагрузки и следующих вариациях параметров объекта. - коэффициент жесткости с упругого звена - посто...
8926. Лекции по теории автоматов Часть 1 Теория абстрактных автоматов 241 KB
  Лекции по теории автоматов Часть 1 Теория абстрактных автоматов Учебное пособие для студентов очной и заочной форм обучения специальностям в области вычислительной техники, информатики и управления. ОГЛАВЛЕНИЕ Часть 1. Теория абстрактных автоматов...
8927. Енергозбереження - шлях до віддалення глобальної катастрофи 115.5 KB
  Тема 10. Енергозбереження - шлях до віддалення глобальної катастрофи Людська цивілізація знаходиться на порозі чергової кризи, звязаної з наслідками її діяльності, а саме - глобальним забрудненням довкілля, зокрема парниковими газами...
8928. Інвестиційна політика в галузі енергозбереження 122 KB
  Тема 9. Інвестиційна політика в галузі енергозбереження З таблиці 2 теми 1 бачимо, що обсяг капіталовкладень, які необхідні для забезпечення ефективної політики в галузі енергозбереження на Україні, становить у розрахунку на 2005 рік...
8929. Утилізація вторинних енергоресурсів 284.5 KB
  Утилізація вторинних енергоресурсів Будь-які енергоносії, чи енергія у формі тепла або стиснених газів, що отримуються внаслідок основних технологічних процесів, наприклад, коксування вугілля, металургійних процесів, роботи ГТУ чи ТЕС, називаються в...
8930. Лекции по теории автоматов. Логические основы цифровых автоматов 620.5 KB
  Лекции по теории автоматов. Логические основы цифровых автоматов. Учебное пособие для студентов очной и заочной форм обучения специальностям в области вычислительной техники, информатики и управления..
8931. Нетрадиційні та поновлювані джерела енергії 644 KB
  Нетрадиційні та поновлювані джерела енергії Сучасна енергетика базується на викопному органічному паливі: камяному вугіллі, нафті та газі. Розвіданих і прогнозних запасів викопного палива при сучасних темпах енергоспоживання достатньо на 90-15...
8932. Біогазова технологія утилізації органічних відходів і виробництва енергії 581 KB
  Біогазова технологія утилізації органічних відходів і виробництва енергії Біогаз - енергоносій, який є сумішшю метану (60 - 70%), діоксиду вуглецю (30 - 40%), невеликої кількості сірководню, водню, аміаку та оксиду азоту(5%). Склад бі...