48763

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

Курсовая

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

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

Русский

2013-12-15

142.5 KB

26 чел.

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

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

                                      

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

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

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


 

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

78624. Эффективность использования основных фондов (основного капитала) на предприятии. Амортизация 24 KB
  Эффективность использования основных фондов основного капитала на предприятии. Амортизация основных фондов есть форма возмещения износа основных фондов путем постепенного переноса ими своей стоимости на произведенный продукт то есть амортизация это денежное выражение физического и морального износа основных фондов. Накапливаемые амортизационные отчисления составляют амортизационный фонд за счет которого производится полное или частичное возмещение стоимости основных фондов. Амортизационный фонд делится на...
78625. Оборотный капитал предприятия и эффективность его использования 34.5 KB
  Наличие у предприятия собственного оборотного капитала его состав и структура скорость оборота и эффективность использования оборотного капитала во многом предопределяют финансовое состояние предприятия и устойчивость его положения на рынке. Эффективное использование оборотного капитала играет большую роль в обеспечении нормальной работы предприятия повышении рентабельности хозяйственной деятельности и зависит от множества факторов. Обобщающим показателем эффективности использования оборотного капитала является его рентабельность Рок...
78626. Прибыль предприятия, ее формирование и использование 53.5 KB
  Прибыль предприятия ее формирование и использование. Прибыль в рыночном хозяйстве является вознаграждением такого специфического фактора как предпринимательство. Вовторых мы не можем трактовать прибыль как своеобразную равновесную цену по аналогии с рынком труда капитала и земли. Предприниматель в результате выполнения этих функций вправе претендовать на определенный доход прибыль.
78627. Организационно-правовые формы предприятия и их развитие в современных условиях 44.5 KB
  Организационноправовые формы предприятия и их развитие в современных условиях Фирма хозяйствующий субъект обладающий экономической самостоятельностью для осуществления производственной деятельности с целью получения прибыли. В настоящее время наибольшее распространение получили следующие формы предприятий организаций: индивидуальные предприятия; товарищества; акционерные общества; объединения предприятий ФПГ; государственные предприятия; смешанные предприятия. Преимущества: быстрая организация предприятия открытие и закрытие;...
78628. Эффективность производственно-хозяйственной деятельности предприятия. Показатели экономической эффективности 38.5 KB
  Эффективность производства – важнейшая качественная характеристика хозяйствования на всех уровнях. Под экономической эффективностью производства понимается степень использования производственного потенциала которая выявляется соотношением результатов и затрат общественного производства. Чем выше результат при тех же затратах чем быстрее он растет в расчете на единицу затрат общественно необходимого труда или чем меньше затрат на единицу полезного эффекта тем выше эффективность производства. Эффективность производства – это показатель...
78629. Производительность труда и ее показатели 27.5 KB
  Производительность труда измеряется количеством продукции вырабатываемой работником в сфере материального производства за единицу рабочего времени или количеством времени которое затрачивается на производство единицы продукции. Повышение производительности труда ведет к увеличению количества продукции производимой в единицу времени...
78630. Себестоимость: структура и пути снижения 29 KB
  Под себестоимостью продукции понимают выраженные в денежной форме текущие затраты предприятия на производство и реализацию продукции. Себестоимость продукции является одним из важнейших качественных показателей эффективности производства который позволяет осуществлять контроль над затратами живого и овеществленного труда и оценивать результаты производственной и хозяйственной деятельности предприятия. Снижение себестоимости продукции способствует увеличению внутрипроизводственных накоплений ускорению расширенного воспроизводства росту...
78631. Трудовые ресурсы и трудовой потенциал страны, региона 36.5 KB
  Подавляющую часть трудовых ресурсов составляет население в трудоспособном возрасте. Основное пополнение трудовых ресурсов происходит и будет происходить в будущем за счет населения моложе трудоспособного возраста. Трудовой потенциал есть совокупность всех трудовых возможностей как отдельного человека так и различных групп работников общества в целом. В отличие от трудовых ресурсов определяющих количество и структуру труда трудовой потенциал характеризует его качество и потенциальные возможности.
78632. Трудовые ресурсы предприятия и эффективность их использования 31.5 KB
  Более развернутое представление о возможностях и способностях рабочей силы дает понятие трудового потенциала как обобщающая характеристика человеческого фактора производства. Вместе с тем понятия трудовых ресурсов рабочей силы и трудового потенциала по существу не нацелены на изучение индивидуальных качеств человека как работника и личности. Поэтому более естественным понятием является человек труда как индивидуализированный элемент трудовых ресурсов владелец рабочей силы обладатель трудового потенциала. Трудовой потенциал...