48763

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

Курсовая

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

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

Русский

2013-12-15

142.5 KB

35 чел.

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

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

                                      

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

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

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


 

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

12134. ИССЛЕДОВАНИЕ КОЛЕБАТЕЛЬНОЙ СТРУКТУРЫ ЭЛЕКТРОННОГО СПЕКТРА ПОГЛОЩЕНИЯ МОЛЕКУЛЯРНОГО ЙОДА 136.5 KB
  Лабораторная работа № 19 ИССЛЕДОВАНИЕ КОЛЕБАТЕЛЬНОЙ СТРУКТУРЫ ЭЛЕКТРОННОГО СПЕКТРА ПОГЛОЩЕНИЯ МОЛЕКУЛЯРНОГО ЙОДА Цель работы: с помощью спектра поглощения паров йода определить частоту колебаний силовую постоянную и энергию диссоциации молекулы йода. Об
12135. КОЛОРИМЕТРИЧЕСКИЕ ИЗМЕРЕНИЯ ОПТИЧЕСКОЙ ПЛОТНОСТИ ПОГЛОЩЕНИЯ МОЛЕКУЛЯРНОГО КРАСИТЕЛЯ 199.5 KB
  Лабораторная работа № 20 КОЛОРИМЕТРИЧЕСКИЕ ИЗМЕРЕНИЯ ОПТИЧЕСКОЙ ПЛОТНОСТИ ПОГЛОЩЕНИЯ МОЛЕКУЛЯРНОГО КРАСИТЕЛЯ Цель работы: Измерение пропускания и оптической плотности растворов красителей по точкам в ближней ультрафиолетовой 315400 нм и видимой областях спек
12136. ОПРЕДЕЛЕНИЕ ДЛИНЫ ПРОБЕГА АЛЬФА-ЧАСТИЦ В ВОЗДУХЕ 141 KB
  Лабораторная работа №21 ОПРЕДЕЛЕНИЕ ДЛИНЫ ПРОБЕГА АЛЬФАЧАСТИЦ В ВОЗДУХЕ Цель работы: ознакомление с aраспадом освоение методики измерения энергии по длине пробега в воздухе. Объект исследования Используется препарат плутоний238 из набора учебных радио...
12137. ИССЛЕДОВАНИЕ ПОГЛОЩЕНИЯ БЕТА-ЧАСТИЦ В АЛЮМИНИИ 307.5 KB
  Лабораторная работа №22 ИССЛЕДОВАНИЕ ПОГЛОЩЕНИЯ БЕТАЧАСТИЦ В АЛЮМИНИИ Цель работы: ознакомиться с распадом освоить методику измерения энергии элементарных частиц методом поглощения. Объект исследования В качестве источника частиц используется к
12138. ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА ПОГЛОЩЕНИЯ ГАММА-ИЗЛУЧЕНИЯ В СВИНЦЕ 750 KB
  Лабораторная работа №23 ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА ПОГЛОЩЕНИЯ ГАММАИЗЛУЧЕНИЯ В СВИНЦЕ Цель работы: Измерение коэффициентов поглощения излучения твердыми телами. Определение энергии квантов и механизма взаимодействия излучения с веществом по коэффициентам...
12139. ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКОГО ХАРАКТЕРА РАСПРЕДЕЛЕНИЯ КОСМИЧЕСКИХ ЧАСТИЦ (РАСПРЕДЕЛЕНИЕ ПУАССОНА) 106 KB
  Лабораторная работа №24 ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКОГО ХАРАКТЕРА РАСПРЕДЕЛЕНИЯ КОСМИЧЕСКИХ ЧАСТИЦ РАСПРЕДЕЛЕНИЕ ПУАССОНА Цель работы: ознакомиться с устройством принципом работы счетчика Гейгера и методикой измерения радиоактивного излучения: изучение хара...
12140. Изучение схемы АВР асинхронных электродвигателей 336 KB
  Изучение схемы АВР асинхронных электродвигателей. Цель работы: По принципиальной схеме составить монтажную схему. Собрать ее на действующем стенде включить в работу и изучить все возможные варианты. План проведения работы.
12141. Исследование схемы управления электродвигателем постоян-ного тока на тиристерных преобразователях 668 KB
  ЛАБОРАТОРНАЯ РАБОТА 2. Тема: Исследование схемы управления электродвигателем постоянного тока на тиристерных преобразователях. Цель работы: Изучение работы тиристорного преобразователя для электродвигателя постоянного тока с регулируемой частотой враще
12142. Исследование схем автоматического пуска электродвигателя в функции времени 324 KB
  Исследование схем автоматического пуска электродвигателя в функции времени. Цель работы: По принципиальной схеме составить монтажную схему собрать схему на действующем стенде включить в работу и изучить возможные варианты