48763

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

Курсовая

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

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

Русский

2013-12-15

142.5 KB

29 чел.

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

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

                                      

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

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

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


 

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

46188. Автострахование в России. Основные проблемы 178.5 KB
  Основные проблемы История страхования в России Досоветский период Эпоха великих реформ Александра II 60е-70е гг. Часть страхового поля включавшая в себя надежные в пожарном отношении объекты застрахования была в значительной мере уже освоена 1м 2м обществами и Саламандрой . Перспективы страхования новых фабрик и их складских помещений были неясны. Было решено подыскать специалиста досконально знакомого с тонкостями огневого страхования и способного предложить программу выхода из нелегкого положения.
46189. ОРГАНИЗАЦИЯ ПРОИЗВОДСТВА НА ПРЕДПРИЯТИЯХ МАШИНОСТРОЕНИЯ 129.5 KB
  Показатели Вариант 9 Обработка резанием Расход металла кг 26 Стоимость 1 кг металла 60 Основная заработная плата рабочих руб. 112 Дополнительная заработная плата 10 Единый социальный налог 26 Расходы по работе оборудования руб. год 1200 Прочие постоянные расходы руб год 1000 Штамповка Расход металла кг 5 Стоимость 1 кг металла 66 Основная заработная плата рабочих руб. шт 4 Дополнительная заработная плата 10 Единый социальный налог 26 Расходы по работе оборудования руб.
46190. Особенности механизма образования цен в строительстве 250 KB
  Капитальный ремонт зданий и сооружений – работы по восстановлению или замене отдельных частей зданий сооружений или целых конструкций деталей и инженерно технического оборудования в связи с их техническим износом и разрушением на более долговечные и экономичные улучшающие их эксплуатационные показатели. Действующая методическая и сметнонормативная база позволяет определить стоимость строительства на всех стадиях разработки предпроектной и проектносметной документации. время работы строительных машин и механизмов маш. Главной функцией...
46191. Решение систем линейных дифференциальных уравнений матричным методом 78 KB
  Часто в физике при решении определенных задач приходится сталкиваться с системами из 3 или 4 линейных дифференциальных уравнений. При решений таких систем удобно использовать матричный метод решения систем линейных дифференциальных уравнений. Часто матрица коэффициентов этих систем уравнений имеет симметричный вид.
46192. Сетевая атака. Классификация сетевых атак 82 KB
  Сегодня к Сети подключены миллионы устройств и многие миллионы устройств будут подключены к Интернету в ближайшем будущем поэтому вероятность доступа хакеров к уязвимым устройствам постоянно возрастает. Создатели этой сети не подозревали насколько широкое распространение она получит. Если приложение работает в режиме клиентсервер а аутентификационные данные передаются по сети в читаемом текстовом формате то эту информацию с большой вероятностью можно использовать для доступа к другим корпоративным или внешним ресурсам. Третий способ...
46193. Водоотводящие системы промышленных предприятий 872.67 KB
  Данная работа представляет собой учебный курсовой проект по дисциплине «Очистка сточных вод предприятий железнодорожного транспорта», выданного кафедрой «Гидравлика, водоснабжения, водные ресурсы и экология» СГУПС
46194. Расчет заработной платы 1.04 MB
  Общая схема расчета зарплаты Предпосылки расчета ЗП Этапы расчета зарплаты Описание этапов функции пользователя Внесение и изменение данных в инфотипы релевантные для расчета зарплаты
46195. МОДЕЛИРОВАНИЕ БИОТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ 10.84 MB
  Настоящее учебное пособие содержит общие сведения о классификации моделей и подходов к математическому описанию процессов клеточного роста и образования клетками продуктов метаболизма; о применении их при планировании экспериментов, статистической обработке полученных результатов и оптимизации биотехнологических процессов. Удобно для использования при выполнении практических заданий, решении задач, планировании и обработке результатов научно-исследовательских и лабораторных работ по спецдисциплинам, при подготовке коллоквиумов, отчетов по лабораторным и научно-исследовательским практикумам, при выполнении курсовых и дипломных работ
46196. Исследование систем управления 261 KB
  Барнауле Региональная кафедра Менеджмента и маркетинга Конспект лекций по дисциплине Исследование систем управления Составитель – к. Анализ и синтез организационных структур управления Анализ структуры управления фирмы Алгоритм определения предпочтительной организационной структуры управления диверсифицированной фирмы