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/


 

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

44749. Умножение десятичных дробей на натуральные числа 243.5 KB
  Тема урока: Умножение десятичных дробей на натуральные числа. Тип урока: комбинированный изучение нового материала закрепление изученного Вид урока: традиционный Цели урока: Образовательные: Ознакомить учащихся с правилом умножения десятичной дроби на натуральное число; научить выполнять умножение десятичной дроби на натуральное число. Оборудование урока: доска с меловыми записями рабочие тетради учебник Математика 5 кл.
44750. Умножение десятичных дробей на натуральные числа 48.5 KB
  Тема урока: Умножение десятичных дробей на натуральные числа. Тип урока: закрепление. Вид урока: традиционный Цели урока: Образовательные: Ознакомить учащихся с правилом умножения десятичных дробей на 101001000 и т.
44751. Деление десятичных дробей на натуральные числа 37.5 KB
  Деление десятичных дробей на натуральные числа. Тип урока: комбинированный изучение нового материала и закрепление изученного Вид урока: традиционный Цели урока: Образовательные: Обеспечить усвоение правила деления десятичных дробей на натуральные числа; формировать умения деления на 10 100 1000. Оборудование урока: доска с меловыми записями рабочие тетради учебник Математика 5 кл.
44752. Деление десятичных дробей на натуральные числа. Закрепление 32 KB
  Деление десятичных дробей на натуральные числа. Тип урока: закрепление Вид урока: традиционный Цели урока: Образовательные: Проконтролировать усвоение правила деления десятичных дробей на натуральные числа; выявить ошибки при вычислениях. Оборудование урока: доска с меловыми записями рабочие тетради учебник Математика 5 кл.
44753. Деление десятичных дробей на натуральные числа 35.5 KB
  Формировать мыслительные умения (деления десятичных дробей на натуральное число; умножение десятичной дроби на 10, 100…) Устанавливать связи ранее изученного материала с новым
44754. Умножение десятичных дробей 40 KB
  Умножение десятичных дробей. Тип урока: комбинированный изучение нового материала закрепление изученного Вид урока: традиционный Цели урока: Образовательные: Подвести учащихся к пониманию правила умножения десятичных дробей; научить выполнять умножение десятичных дробей. Оборудование урока: доска с меловыми записями рабочие тетради учебник Математика 5 кл.
44755. Умножение и деление десятичных дробей на натуральное число 1.28 MB
  Умножение и деление десятичных дробей на натуральное число. Тип урока: урок контроля. Вид урока: традиционный Цели урока: Образовательные: Проверить знания умения и навыки по теме: Умножение и деление десятичных дробей на натуральное число.