48763

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

Курсовая

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

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

Русский

2013-12-15

142.5 KB

31 чел.

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

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

                                      

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

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

Задача о 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/


 

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

41056. Порядок складання, оформлення та ведення облікових документів 122.5 KB
  Організація обліку матеріальних засобів речової служби у військовій частиніâ€. Для студентів спеціальності “Організація об’єднаного забезпечення в наземних військах та авіаціїâ€ Навчальна та виховна мета: Ознайомити студентів з організацією обліку речового майна у військовій частині. Успішне рішення задач будівництва держави вимагає повсюдного впровадження наукової організації обліку. У рішеннях уряду підкреслюється необхідність поліпшувати систему обліку і звітності...
41057. Порядок зарахування військової частини на речове забезпечення.Витребування речового майна 104 KB
  Речове забезпечення військової частини у мирний час Витребування і отримання речового майна військовою частиною†Для студентів спеціальності “Організація об’єднаного забезпечення в наземних військах та авіаціїâ€ Навчальна та виховна мета: Розширити та поглибити теоретичні знання студентів з питань зарахування військової частини на речове забезпечення витребування речового майна та отримання його зі складу оперативного...
41058. Вимоги щодо зберігання речового майна 131 KB
  Організація зберігання речового майна у військовій частині. Організація зберігання речового майна у військовій частині. Для студентів спеціальності “Організація об’єднаного забезпечення в наземних військах та авіаціїâ€ Навчальна та виховна мета:Ознайомити студентів з загальними вимогами щодо зберігання речового майна у військовій частині.
41059. Право та порядок зарахування військовослужбовців на речове забезпечення 93.5 KB
  Забезпечення речовим майном особового складу військової частини Забезпечення речовим майном військовослужбовців строкової служби та військовослужбовців які проходять службу за контрактом†Для студентів спеціальності €œОрганізація об’єднаного забезпечення в наземних військах та...
41060. Порядок забезпечення речовим майном офіцерів, прапорщиків та військовослужбовців жінок 208.5 KB
  €œОрганізація речового забезпечення Забезпечення речовим майном особового складу військової частини €œЗабезпечення речовим майном офіцерів прапорщиків та військовослужбовцівжінок†Для студентів спеціальності “Організація об’єднаного забезпечення в наземних військах та авіації
41061. Організація правильної експлуатації, збереження і своєчасного ремонту речового майна 93.5 KB
  Експлуатація та ремонт речового майна €œОрганізація експлуатації та збереження речового майнаâ€.Ознайомити студентів з загальними положеннями щодо організації правильної експлуатації збереження та своєчасного ремонту речового майна.Розширити та поглибити теоретичні знання студентів з питань організації та порядку переведення речового майна із однієї категорії в іншу та порядку списання речового майна.
41062. Значення лазнево-прального обслуговування. Перелік робіт та послуг які відносяться до лазнево-прального обслуговування 135 KB
  Лазневопральне обслуговування має на меті організацію гігієнічної помивки особового складу своєчасне прання білизни дезінфекцію і хімічне чищення обмундирування і спеціального одягу. Лазневопральне обслуговування військових частин кораблів установ і закладів включає: організацію регулярної щотижневий помивки в лазні солдатів матросів сержантів і старшин термінової служби курсантів військовоморських і військових училищ суворовців і нахімовців а також військовозобов'язаних під час проходження ними зборів з обов'язковою зміною...
41063. Звітність військової частини по речовій службі 72 KB
  Для підтримання високого рівня бойової і мобілізаційної готовності, створення нормальних умов життя і побуту особового складу військ, Збройні Сили України отримують від народного господарства озброєння, техніку та інші види матеріальних засобів
41064. ПОЛИТИЧЕСКОЕ ПОЗИЦИОНИРОВАНИЕ ПУБЛИЧНЫХ ИМИДЖЕЙ 359 KB
  Имидж политика, как правило, создается на основе ожиданий целевой группы электората. Важно сформировать необходимое восприятие политического деятеля в массовом сознании. При этом не менее важным является и процесс поддержания политического имиджа, так как созданный образ может искажаться со временем в силу определенных причин.