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/


 

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

82265. Вера и знание, достоверность и сомнение. Диалектика веры и сомнения в процессе познания 32.72 KB
  В социальногуманитарных науках знание всегда сочетается с верой и сомнением так как вера ориентирована на преувеличение роли абсолютного момента в знании а сомнение – роли относительного – в нем. Вера присутствует в социальногуманитарных науках прежде всего в силу незавершенности познания социальных явлений как допущение возможности соответствия социальной реальности и его отражения в знании. Она также может присутствовать в социальногуманитарных науках: как вера ученогогуманитария в Бога ученый привносит в науку свою веру как его...
82266. Конструктивная роль веры как условия «бытия среди людей» (Л.Витгенштейн) Вера и верования 31.72 KB
  Витгенштейн Вера и верования. Вера возникает как необходимое следствие бытия среди людей утверждает Витгенштейн имеет социальнокоммуникативную природу. Вера – субъективная уверенность. Вера и знание имеют различные основания противоположно направленные.
82267. Вера и понимание в контексте коммуникаций. Вера и истина. Типы обоснования веры и знания. Соотношение веры и истины 36.66 KB
  Типы обоснования веры и знания. Одной из основных предпосылок философскометодологического анализа социальногуманитарного знания является рассмотрение научного познания в контексте культуры его связь с историческими особенностями и ценностными установками общества. Тема веры достоверности сомнения оказывается одной из фундаментальных в самых разных областях и на разных этапах научного познания. Соотношение различных духовноценностных установок веры и научного знания поразному влияло на развитие науки.
82268. Натуралистическая исследовательская программа 38.77 KB
  Сегодня вопрос об исследовательской программе или близком к ней понятии парадигмы в социальных науках сталкивается с двумя трудностями: 1 избрания масштаба исследования; 2 многообразия исследовательских программ господствующего сегодня в социальногуманитарных науках. Какие исследовательские программы парадигмы можно выделять 1 Классическая философия были ориентирована на природу и изучающие ее науки на следующую отсюда натуралистическую парадигму. Последователи натуралистической исследовательской программы полагают: либо предмет наук...
82269. Антинатуралистическая исследовательская программа и ее общенаучное значение 36.58 KB
  Природа остается в качестве предпосылки деятельности человека но культур центризмом не схватывается оставляя место натурализму Другой причиной жизненности натуралистической исследовательской программы является вызванное объективными социальными изменениями крушение классических рационалистических установок. Она по существу указала на границы натуралистической программы. Натуралистическая и антинатуралистическая программы направлены на изучение одного и того же объекта но в соответствии со своей методологией исследовательской программой...
82270. Применение натуралистической и антинатуралистической исследовательских программ ва социально –гуманитарных науках 33.52 KB
  В них присутствуют: натуралистическая парадигма общества основные варианты: механицизм физикализм биологизм географический детерминизм демографический детерминизм – общество понимается как жестко-детерминированная система обусловленная влиянием определенных природных факторов климата полезных ископаемых территории и т. оно рассматривается с редукционистских позиций; антинатуралистическая парадигма общества основные варианты: социологизм экономизм психологизм антипсихологизм – общество понимается как...
82271. Проблема разделения социальных и гуманитарных наук пол предмету, по методу, по предмету и методу одновременно, по исследовательским программам 34.01 KB
  В настоящее время считается что естественные науки и социально-гуманитарные науки имеют как общие так и различные характеристики. Естественные и социально-гуманитарные науки обладают всеми признаками науки как особого феномена познание нового наличие эмпирического и теоретического уровней оформленность в понятиях и т. Вместе с тем социально-гуманитарные науки отличаются от естественно-математических и технических наук по следующим основаниям: по объекту исследования – естественные науки изучают природную реальность т. то что существует...
82272. Методы социальных и гуманитарных наук 42.51 KB
  Абстрагирование важнейший метод научного постижения реальности. Результатом применения этого метода является абстракция. Наряду с абстрагированием важнейшим методом научного познания на эмпирическом уровне познания является индукция. Индукция это метод движения мысли от менее общего знания к более общему.
82273. Вненаучное социальное знание. Взаимодействие социальных, гуманитарных наук и вненаучного знания в экспертизах социальных проектов и программ 39.26 KB
  Взаимодействие социальных гуманитарных наук и вненаучного знания в экспертизах социальных проектов и программ. Эйнштейн ищут основания знания в философии и художественной литературе. Антифундаменталистская тенденция просматривается в истолковании всех важнейших областей научного познания: математического естественнонаучного гуманитарного. В то время как сциентизм базируется на абсолютизации рациональнотеоретических компонентов знания антисциентизм опирается на ключевую роль этических правовых культурных ценностей по отношению к идеалу...