Задача о расстановке ферзей

Министерство  образования и науки РФ федеральное  агентство по образованию государственное  образовательное учреждение высшего  профессионального образования  Северо-Кавказский Государственный  Технический Университет. 
 
 
 
 

Курсовая работа 
 

По дисциплине: Информатика.

На тему: «Решение задачи о расстановке ферзей» 
 
 
 
 
 
 
 

Выполнил:

Студент группы ИС-071  I – курса

Савченко  Николай Сергеевич 
 
 

Проверил:

Ратнер И. М. 
 
 
 

Ставрополь 2008г. 

План.

1. Введение.
2. Алгоритм решения.
3. Реализация алгоритма на С++
4. Заключение.
5. Список литературы.

 

  

  Введение.

  Шахмамты не только популярная игра, но и источник множества интересных математических задач. Не случайно шахматные термины можно встретить в литературе по комбинаторике, теории графов, кибернетике, теории игр,программированию.

  Эта задача - одна из очень интересных шахматных  головоломок. 
Условие такое: можно ли поставить восемь ферзей на пустой доске таким образом, чтобы ни один из них не “атаковал” другого, т.е. так, чтобы ни какие два ферзя не стояли на одном и том же столбце, или на одной и той же строке, или на одной и той же диагонали шахматной доски. 
 
Решение этой задачи существует, причём не одно. На рис.1 показан один из возможных вариантов расстановки ферзей.

Рисунок 1

 

Алгоритм  решения.

  Решение этой задачи на компьютере не представляет большой сложности. В принципе, можно  перебрать все возможные варианты расстановки ферзей на доске, а затем  определить подходящие. Но так как  существует очень большое количество решений, выполнение  этого алгоритма  занимает много времени.

  Поэтому, нужно каким-то образом определить на какую клетку ставить следующего ферзя. Например, ставить несколько  ферзей в одну линию бессмысленно (это противоречит условию). Если попробовать  решить задача вручную, то становится понятно, что расставить 6 – 7 ферзей не сложно. Но после этого свободных  клеток (которые не “бьются” ни одним  из ферзей) нет. Следовательно, ферзей нужно расставлять так, чтобы  они били как можно меньше клеток. Очень хорошо если несколько разных ферзей “бьют” одни и те же клетки, но при этом не “бьют” друг друга.

  Дальше  все очень просто. Нужно перебрать  по очереди все свободные клетки доски (те, которые не “атакует”  ни один ферзь) и посчитать, сколько  свободных клеток “будет” бить ферзь из данной.

  Для решения этой задачи потребуется  массив Х, из восми элементов типа int, обозначающих позицию ферзя в i-том ряду шахматной доски (где i – индекс массисва Х) и три функции: MainProc,Check,Display.

  Функция Check – проверяет не занята ли данная клетка и не атакует ли её один из ферзей.

  Функция Display – выводит на экран текущее  содержание массива Х в виде шахматной  доски.

  Функция MainProc – сначала, используя функцию Check находит свободную и не подвергающуюся атаке позицию в одном ряду на доске и заносит её в массив Х, затем рекурсивно делает тоже самое, но уже для другого ряда, а когда пройдены все ряды, добавляет 1 к числу возможных расстановок и, используя функцию Display выводит результат на экран. 
Функция Check – проверка не бьётся ли эта клетка другим ферзём  
Функция Display – Выводит на экран комбинации

 

  Функция MainProc – инициализация массива X – шахматной доски

    
Тело программы

 

  //Расстановка ферзей 

  #include <iostream>

  #include <math.h>

  #include <conio.h>

  using namespace std; 

  int const N = 8; 

  char X[N]; long Count; 

  void Display()

  {

        char a=219,b=255;//объявление символов

        for (int i=0;i<N;i++)

        {

              for(int j=0;j<N;j++)

              {

                    if(j==X[i])cout<<"QQ";

                    else if((i+j)%2)cout<<b<<b;

                    else cout<<a<<a;

              }

              cout<<"\n";

        }

        cout<<"\n";

  } 

  bool Check(int K, int Y)

  {

        int i=0;

        while ((i < K) && (Y != X[i]) && (abs(K - i) != abs(Y - X[i]))) i++;

        return (i == K);

  } 

  void MainProc(int k)

  {

        for (int y = 0; y<N; y++)

              if (Check(k, y))

              {

                    X[k] = y;

                    if (k == (N - 1))

                    {

                          Display();

                          Count++;

                    }

                    MainProc(k + 1);

              }

  } 

  void main()

  {

    Count = 0;

    MainProc(0);

    cout<<"Vsego "<<Count<<" rastanovok\n"; 

    getch();

  }

  В результате выполнения программы будет выведен  на экран список всех возможных комбинаций и их количество (рис.2)

Рисунок 2

 

Список  используемой литературы:

1. Т. Кормен, Ч. Лейзерсон, Р.Ривест Алгоритмы: построение и анализ. —

М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004

2. Ф. А. Новиков Дискретная математика для программистов. —

СПб.: Питер 2004

3. http://www.livejournal.ru/
4. http://www.computerra.ru/
5. http://ru.wikipedia.org/