C++. Задача о N ферзях. Решение на C++




Задача о N ферзях. Решение на C++


Содержание


Поиск на других ресурсах:

Введение

На олимпиадах по программированию часто встречается задача размещения 8 ферзей на шахматной доске: нужно написать такой алгоритм, в котором 8 ферзей помещаются на шахматной доске (размер 8×8) таким образом, что они не бьют друг друга. Простейший вариант решения данной задачи есть реализация полного перебора для 8 вложенных циклов с соответствующими проверками на пересечение по диагонали и вертикали. Но этот вариант не является пригодным для задачи, в которой количество ферзей составляет N, а размер доски составляет N×N.

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

 

Условие задачи

Задано целое число N (N>0), определяющее количество ферзей на доске размером N×N. Разработать программу, которая находит все возможные варианты размещения N ферзей таким образом, чтобы они не «били» друг друга. В программе обеспечить визуализацию каждого полученного варианта.

Задачу реализовать как приложение типа Windows Forms Application с использованием языка программирования C++.

 

Соображения

Для приложения типа Visual C++ — Windows Forms система Microsoft Visual Studio предоставляет соответствующие элементы управления с целью удобной визуализации полученных вариантов размещений.

Для визуализации доски размером N×N хорошо подходит элемент управления типа DataGridView. В этом элементе управления можно отображать данные как из базы данных, так и непосредственно в виде двумерной таблицы.

Перечень полученных вариантов в виде координат (x1, y1), (x2, y2), …, (xN, yN) можно сохранить в элементе управления ListBox, который представляет собой динамический список произвольного размера.

При выборе варианта в ListBox автоматически будет отображаться размещение в DataGridView.

 

Выполнение

1. Особенности реализации алгоритма решения задачи

1.1. Использование дополнительного массива для описания размещения ферзей на доске

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

Для обеспечения полного перебора вариантов, в работе используется дополнительный одномерный массив M размерностью N+1. Элемент массива с индексом 0 (M[0]) не используется с целью обеспечения удобства при оперировании индексами массива.

В массиве M координаты размещаемых ферзей формируются по следующему принципу:

  • координате x ферзя с номером k (k = 1..N) соответствует значение M[k];
  • координате y ферзя с номером k (k = 1..N) соответствует само значение k.

На рисунке 1 схематично изображен вариант размещения для N=5 на доске размером 5×5 и вид массива M

C++ задача N ферзей структуры данных

Рисунок 1. Интерпретация значений элементов массива M для доски размером 5×5

Как видно из рисунка, индексы массива M соответствуют координате y доски, а значение M[i] по данному индексу соответствует координате x доски:

M[1] => x координата 1-го ферзя: (x1, y1) => (M[1], 1)
M[2] => x координата 2-го ферзя: (x2, y2) => (M[2], 2)
...
M[k] => x координата k-го ферзя: (xk, yk) => (M[k], k)
...
M[N] => x координата N-го ферзя: (xN, yN) => (M[N], N)

Массив M заменяет полный перебор, который может быть сформирован с помощью N вложенных циклов.

 

1.2. Описание работы алгоритма

Вся работа алгоритма базируется на формировании некоторого размещения ферзей с помощью массива M. Номер ферзя, который размещается сохраняется в некоторой переменной-указателе, например, с именем p. В зависимости от ситуации, указатель p двигается вправо (p++) или влево (p—) как изображено на рисунке 2 для 5 ферзей. Итак, указатель p определяет номер ферзя, который размещается и координату y. Значение M[p] определяет координату x размещаемого ферзя с номером p.

При изменении значения указателя постоянно проверяется условие p=N, которое значит, что размещается последний ферзь. Если p=N и нет наложений между ферзями в текущем размещении, то это размещение фиксируется. В нашем случае размещение фиксируется в списке ListBox в виде строки специального формата. Если p<N, то определяются следующие изменения указателя p (номер размещаемого ферзя) или M[p] в зависимости от того, есть ли наложение для текущего количества ферзей и их размещения.

Условием окончания итерационного процесса есть получение всех возможных вариантов. При этом, указатель p двигается влево к элементу, который следует перед первым, то есть к нулевому элементу.

На рисунке 2 изображены разные варианты (состояния) массива M на основе указателя p для N=5. Выделяются:

  • 1 — начальное состояние. Это есть состояние массива M, при котором начинается итерационный процесс;
  • 2 — промежуточное состояние. Это есть некоторый промежуточный вариант размещения, когда еще не все ферзи размещены и размещается k-й ферзь (k=1..N);
  • 3 — вариант размещения – это вариант массива M, в котором сформированно искомое размещение (случай, когда все N ферзей не бьют друг друга);
  • 4 — окончание итерационного процесса (p=0). Итерационный процесс завершается, если после перебора всех возможных вариантов указатель p двигается влево (p—) и становится равным 0.

C++ Решение задачи размещения N ферзей Структуры данных

Рисунок 2. Массив M и его состояния при формировании размещения с помощью указателя p: 1) начальное состояние; 2) промежуточное состояние; 3) искомое размещение; 4) условие окончания итерационного процесса

 

2. Разработка программы

2.1. Запустить Microsoft Visual Studio. Создать проект по шаблону Windows Forms Application — C++

Загрузить систему Microsoft Visual Studio (любой версии) и сохранить проект. Подробный пример создания проекта по шаблону Windows Forms Application можно просмотреть здесь.

Имя проекта можно задать произвольным, например, PlacementNQueens. В результате будет создана пустая форма проекта.

 

2.2. Проектирование формы приложения
2.2.1. Размещение элементов управления на форме

Из панели ToolBox разместить на форме приложения следующие элементы управления:

  • четыре элемента управления типа Label для отображения информационных сообщений. В результате будут созданы три экземпляра (объекты) типа Label, которые имеют имена label1, label2, label3, label4. Один из этих элементов управления будет отображать количество вариантов размещений;
  • один элемент управления типа TextBox. Создается экземпляр (объект) с именем textBox1;
  • один элемент управления типа ListBox. Создается экземпляр с именем listBox1;
  • один элемент управления типа DataGridView. Создается экземпляр с именем dataGridView1. Этот элемент управления будет отображать доску в форме таблицы;
  • один элемент управления типа Button. Создается экземпляр с именем button1. Этот элемент управления будет запускать на выполнение процесс поиска размещений для заданного N.

На рисунке 3 отображена форма приложения после размещения элементов управления.

C++ Windows Forms Форма приложения

Рисунок 3. Форма приложения после размещения элементов управления

 

2.2.2. Настройка элементов управления формы

На этом этапе нужно настроить следующие свойства элементов управления:

  • в элементе управления label1 свойство Text = «N = «;
  • в label2 свойство Text = «Placements»;
  • в label3 свойство Text = «Current placement»;
  • в label4 свойство Text = «Number of placements = «;
  • в button1 свойство Text = «Start»;
  • в элементе управления Form1 свойство Text = «Placement of N Queens».

После настройки элементов управления и корректировки их размеров, форма приложения будет иметь приблизительный вид как показано на рисунке 4.

C++ Шаблон Windows Forms Application Форма приложения

Рисунок 4. Форма приложения после настройки

 

3. Написание программного кода

3.1. Текст модуля Form1.h

После создания проекта, весь программный код будет набираться в модуле Form1.h. На данный момент текст модуля формы имеет следующий вид:

#pragma once

namespace PlacementNQueens1 {
  using namespace System;
  using namespace System::ComponentModel;
  using namespace System::Collections;
  using namespace System::Windows::Forms;
  using namespace System::Data;
  using namespace System::Drawing;

  /// <summary>
  /// Summary for Form1
  /// </summary>
  public ref class Form1 : public System::Windows::Forms::Form
  {
  public:
    Form1(void)
    {
      InitializeComponent();
      //
      //TODO: Add the constructor code here
      //
    }

  protected:
    /// <summary>
    /// Clean up any resources being used.
    /// </summary>
    ~Form1()
    {
        if (components)
        {
          delete components;
    }
  }

  private: System::Windows::Forms::DataGridView^   dataGridView1;
  protected:
  private: System::Windows::Forms::Button^   button1;
  private: System::Windows::Forms::Label^ label1;
  private: System::Windows::Forms::ListBox^ listBox1;
  private: System::Windows::Forms::TextBox^   textBox1;
  private: System::Windows::Forms::Label^ label2;
  private: System::Windows::Forms::Label^ label3;
  private: System::Windows::Forms::Label^ label4;

  private:
    /// <summary>
    /// Required designer variable.
    /// </summary>
    System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code
    /// <summary>
    /// Required method for Designer support - do not modify
    /// the contents of this method with the code editor.
    /// </summary>

    void InitializeComponent(void)
    {
      this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());
      this->button1 = (gcnew System::Windows::Forms::Button());
      this->label1 = (gcnew System::Windows::Forms::Label());
      this->listBox1 = (gcnew System::Windows::Forms::ListBox());
      this->textBox1 = (gcnew System::Windows::Forms::TextBox());
      this->label2 = (gcnew System::Windows::Forms::Label());
      this->label3 = (gcnew System::Windows::Forms::Label());
      this->label4 = (gcnew System::Windows::Forms::Label());
      (cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->BeginInit();
      this->SuspendLayout();
      //
      // dataGridView1
      //
      this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;
      this->dataGridView1->Location = System::Drawing::Point(212, 60);
      this->dataGridView1->Name = L"dataGridView1";
      this->dataGridView1->Size = System::Drawing::Size(350, 290);
      this->dataGridView1->TabIndex = 0;
      //
      // button1
      //
      this->button1->Location = System::Drawing::Point(212, 10);
      this->button1->Name = L"button1";
      this->button1->Size = System::Drawing::Size(168, 23);
      this->button1->TabIndex = 1;
      this->button1->Text = L"Start";
      this->button1->UseVisualStyleBackColor = true;
      this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);
      //
      // label1
      //
      this->label1->AutoSize = true;
      this->label1->Location = System::Drawing::Point(12, 15);
      this->label1->Name = L"label1";
      this->label1->Size = System::Drawing::Size(27, 13);
      this->label1->TabIndex = 2;
      this->label1->Text = L"N = ";
      //
      // listBox1
      //
      this->listBox1->FormattingEnabled = true;
      this->listBox1->Location = System::Drawing::Point(15, 60);
      this->listBox1->Name = L"listBox1";
      this->listBox1->Size = System::Drawing::Size(194, 290);
      this->listBox1->TabIndex = 3;
      this->listBox1->Click += gcnew System::EventHandler(this, &Form1::listBox1_Click);
      this->listBox1->KeyUp += gcnew System::Windows::Forms::KeyEventHandler(this, &Form1::listBox1_KeyUp);
      //
      // textBox1
      //
      this->textBox1->Location = System::Drawing::Point(63, 12);
      this->textBox1->Name = L"textBox1";
      this->textBox1->Size = System::Drawing::Size(100, 20);
      this->textBox1->TabIndex = 4;
      //
      // label2
      //
      this->label2->AutoSize = true;
      this->label2->Location = System::Drawing::Point(12, 44);
      this->label2->Name = L"label2";
      this->label2->Size = System::Drawing::Size(62, 13);
      this->label2->TabIndex = 5;
      this->label2->Text = L"Placements";
      //
      // label3
      //
      this->label3->AutoSize = true;
      this->label3->Location = System::Drawing::Point(209, 44);
      this->label3->Name = L"label3";
      this->label3->Size = System::Drawing::Size(93, 13);
      this->label3->TabIndex = 6;
      this->label3->Text = L"Current placement";
      //
      // label4
      //
      this->label4->AutoSize = true;
      this->label4->Location = System::Drawing::Point(12, 362);
      this->label4->Name = L"label4";
      this->label4->Size = System::Drawing::Size(125, 13);
      this->label4->TabIndex = 7;
      this->label4->Text = L"Number of placements = ";
      //
      // Form1
      //
      this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);
      this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
      this->ClientSize = System::Drawing::Size(730, 395);
      this->Controls->Add(this->label4);
      this->Controls->Add(this->label3);
      this->Controls->Add(this->label2);
      this->Controls->Add(this->textBox1);
      this->Controls->Add(this->listBox1);
      this->Controls->Add(this->label1);
      this->Controls->Add(this->button1);
      this->Controls->Add(this->dataGridView1);
      this->Name = L"Form1";
      this->Text = L"Placement of N Queens";
      (cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->EndInit();
      this->ResumeLayout(false);
      this->PerformLayout();
    }
#pragma endregion
  }
}

 

3.2. Объявление внутренней переменной N (количество ферзей)

В текст класса вводится внутренняя скрытая (private) переменная N, которая определяет количество ферзей для размещения а также размеры доски

private:
    int N; // количество ферзей

После ввода N, вид класса формы Form1 следующий:

...

public ref class Form1 : public System::Windows::Forms::Form
{
private:
    int N; // количество ферзей

public:
    Form1(void)
    {
        InitializeComponent();
        //
        //TODO: Add the constructor code here
        //
    }
...
}
...

 

3.3. Метод IsStrike(). Проверка того, бьются ли два ферзя с разными координатами

В текст класса Form1 вводится метод IsStrike(). Метод служит основой проверки на накладывание. Метод проверяет, «бьются» ли два ферзя с разными координатами. Метод получает 4 целочисленных параметра:

  • x1, y1 – координаты первого ферзя;
  • x2, y2 – координаты второго ферзя.

Метод возвращает true, если два ферзя «бьют» друг друга. В методе происходит проверка как по горизонтали, так и по вертикали.

Метод должен быть размещен в классе Form1 после директивы

#pragma endregion





Листинг метода в классе Form1 следующий

...

public ref class Form1 : public System::Windows::Forms::Form
{
    ...

#pragma endregion

    // Проверка, бъются ли 2 ферзя
    bool IsStrike(int x1, int y1, int x2, int y2)
    {
        // 1. Горизонталь, вертикаль
        // Ферзи бъют друг друга, если какие то 2 значения-параметра совпадают
        if ((x1 == x2) || (y1 == y2)) return true;

        // 2. Главная диагональ
        int tx, ty; // дополнительные переменные

        // 2.1. Влево-вверх
        tx = x1 - 1; ty = y1 - 1;
        while ((tx >= 1) && (ty >= 1))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx--; ty--;
        }

        // 2.2. Вправо-вниз
        tx = x1 + 1; ty = y1 + 1;
        while ((tx <= N) && (ty <= N))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx++; ty++;
        }

        // 3. Дополнительная диагональ
        // 3.1. Вправо-вверх
        tx = x1 + 1; ty = y1 - 1;
        while ((tx <= N) && (ty >= 1))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx++; ty--;
        }

        // 3.2. Влево-вниз
        tx = x1 - 1; ty = y1 + 1;
        while ((tx >= 1) && (ty <= N))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx--; ty++;
        }
        return false;
    }
};
...

 

3.4. Метод Strike(). Проверка наложения размещаемого ферзя с предшествующими (уже размещенными) ферзями

Метод Strike() предназначен для проверки координат ферзя, который размещается с координатами ранее размещенных ферзей, которые между собой не накладываются.

Метод получает входящими параметрами массив M и указатель p (см. п.п. 1.2-1.3). В массиве M помещается информация о:

  • координатах ферзей, которые рассматриваются как размещенные и которые не накладываются;
  • указатель p, представляющий номер размещаемого ферзя. Значит, координата M[p] есть координатой x текущего ферзя, который размещается. Координата p есть координатой y текущего ферзя, который размещается.

Метод проверяет, накладывается ли ферзь с координатами, которые соответствуют позиции p, с ферзями, которые размещены в позициях 1, 2, … , p-1.

Метод должен быть размещен в классе формы Form1 после метода IsStrike(). Листинг метода следующий:

// Проверка, накладывается ли последний элемент M[p]
// с элементами M[1], M[2], ..., M[p-1].
// Данная функция использует функцию IsStrike()
bool Strike(int M[], int p)
{
    int px, py, x, y;
    int i;

    px = M[p];
    py = p;

    for (i = 1; i <= p - 1; i++)
    {
        x = M[i];
        y = i;
        if (IsStrike(x, y, px, py))
            return true;
    }
    return false;
}

 

3.5. Методы обеспечивающие отображение размещения ферзей в dataGridView1
3.5.1. Метод InitDataGridView(). Инициализация и настройка элемента управления dataGridView1

Элемент управления dataGridView1 используется для отображения размещения записанного в listBox1. В методе InitDataGridView() реализована начальная инициализация dataGridView1 программным путем. Метод получает входным параметром значение N.

Метод должен быть помещен после метода Strike(). Листинг метода InitDataGridView() следующий

// начальная инициализация dataGridView1
// N - количество ферзей
void InitDataGridView(int N)
{
    int i;

    dataGridView1->Columns->Clear();

    // сформировать dataGridView1 - добавить столбцы
    for (i = 1; i <= N; i++)
    {
        dataGridView1->Columns->Add("i" + i.ToString(), i.ToString());

        // ширина столбца в пикселах
        dataGridView1->Columns[i - 1]->Width = 30;
    }

    // добавить строки
    dataGridView1->Rows->Add(N);

    // вывести номера строк
    for (i=1; i<=N; i++)
        dataGridView1->Rows[i-1]->HeaderCell->Value = i.ToString();

    // забирает последнюю строку, чтобы нельзя было добавлять строки в режиме выполнения
    dataGridView1->AllowUserToAddRows = false;

    // выравнивание по центру во всех строках
    dataGridView1->RowsDefaultCellStyle->Alignment = DataGridViewContentAlignment::MiddleCenter;
}

 

3.5.2. Отображение строки из listBox1 в dataGridView1. Метод ShowDataGridView()

В элементе управления listBox1 отображаются строки, которые содержат варианты полученных размещений. Строки сформированы в собственном формате. Выделенная строка в listBox1 отображается в dataGridView1 в виде матрицы (доски).

Метод ShowDataGridView() предназначен для обработки выделенной строки в listBox1 и визуализации координат ферзей, представленных в этой строке. Сформированные в виде строки координаты ферзей визуализируются в dataGridView1.

Метод получает входными параметрами:

  • строку s, в которой помещаются пары координат ферзей для полученных размещений;
  • количество ферзей N.

Текст метода размещается после метода InitDataGridView().

Листинг метода ShowDataGridView() следующий

// метод, отображающий в dataGridView1 строку s,
// N - количество ферзей
// принимаем, что dataGridView1 уже инициализирован в размер N*N
void ShowDataGridView(String ^ s, int N)
{
    int i;
    int j;
    String ^ xs;
    String ^ ys;
    int x, y;

    // сначала очистить dataGridView1
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            dataGridView1->Rows[i]->Cells[j]->Value = "";

    j = 0; // смещение
    for (i = 0; i < N; i++)
    {
        // сформировать xs
        xs = "";
        while (s[j] != ',')
        {
            xs = xs + s[j].ToString();
            j++;
        } // xs - число x в виде строки

        // прокрутить смещение
        j++;

        // сформировать ys
        ys = "";
        while (s[j] != '-')
        {
            ys = ys + s[j].ToString();
            j++;
        }

        // прокрутить смещение
        j++;

        // перевести xs->x, ys->y
        x = x.Parse(xs);
        y = y.Parse(ys);

        // обозначить позицию (x, y) ферзя
        dataGridView1->Rows[y - 1]->Cells[x - 1]->Value = "X";
    }
}

 

3.6. Методы работи с listBox1
3.6.1. Добавить размещения в listBox1 в формате строки. Метод AddToListBox()

Метод AddToListBox() выполняет следующие операции:

  • конвертирует размещение, описанное в строках массива M в строку типа string;
  • добавляет сформированную строку к списку в listBox1.

Пример строки s типа string для N=5 и массива M, изображенного на рисунке 1:

"11-23-35-42-54-"

Текст метода помещается после метода ShowDataGridView(). Листинг метода AddToListBox() в тексте формы Form1 следующий:

// записать строку в listBox1
// входные параметры: M[] - массив чисел, N - количество элементов в массиве M[]
void AddToListBox(int M[], int N)
{
    // добавить в listBox1 строку
    String ^ s;
    for (int i = 1; i <= N; i++)
        s = s + M[i].ToString() + "," + i.ToString() + "-";
    listBox1->Items->Add(s);
}

 

3.6.2. Программирование обработчиков событий Click и KeyUp элемента управления listBox1

В элементе управления listBox1 формируется перечень строк, которые соответствуют полученным размещениям N ферзей на доске размером N×N. В программе нужно обеспечить визуализацию в dataGridView1 выделенной в listBox1 строки. Для того, чтобы пользователь мог удобно пересматривать полученные размещения в dataGridView1, нужно запрограммировать обработчики событий Click и KeyUp элемента управления listBox1.

В данной теме не рассматривается подробный процесс программирования обработчиков событий Click и KeyUp, поскольку он осуществляется стандартным способом. Более подробный пример того, как программируется обработчик события в Microsoft Visual Studio описывается в теме:

Обработчики событий размещаются после метода AddToListBox(). Листинг обработчиков событий Click и KeyUp элемента управления listBox1 следующий:

// клик на listBox1
private: System::Void listBox1_Click(System::Object^   sender, System::EventArgs^ e) {
    if (listBox1->Items->Count <= 0) return;
    int num;
    num = listBox1->SelectedIndex;
    ShowDataGridView(listBox1->Items[num]->ToString(), N);
}

// нажата клавиша в listBox1 - событие KeyUp
private: System::Void listBox1_KeyUp(System::Object^   sender, System::Windows::Forms::KeyEventArgs^ e) {
    if (listBox1->Items->Count <= 0) return;
    int num;
    num = listBox1->SelectedIndex;
    ShowDataGridView(listBox1->Items[num]->ToString(), N);
}

 

3.7. Программирование события Click на кнопке Start. Реализация алгоритма поиска размещений

При нажатии клавиши Start пользователь должен получить перечень вариантов размещения N ферзей. Все это осуществляется в обработчике события Click, который вызывается при нажатии на кнопке Start.

В обработчике события реализуется алгоритм, который описан в п. 1.3.

Листинг обработчика события следующий:

// Обработчик события Click на элементе управления Button - реалізует размещение
private: System::Void button1_Click(System::Object^   sender, System::EventArgs^ e) {
    const int MaxN = 20;
    int M[MaxN];
    int p; // номер размещаемого ферзя
    int k; // количество вариантов размещения

    // получить количество ферзей
    N = N.Parse(textBox1->Text);

    // Инициализировать dataGridView1
    InitDataGridView(N);

    // очистить listBox1
    listBox1->Items->Clear();

    // АЛГОРИТМ ФОРМИРОВАНИЯ РАЗМЕЩЕНИЯ
    // начальные настройки
    p = 1;
    M[p] = 0;
    M[0] = 0;
    k = 0;

    // цикл формирования размещения
    while (p > 0) // если p==0, то виход из цикла
    {
        M[p] = M[p] + 1;
        if (p == N) // последний элемент
        {
            if (M[p] > N)
            {
                while (M[p] > N) p--; // перемотать обратно
            }
            else
            {
                if (!Strike(M, p))
                {
                    // зафиксировать размещение
                    AddToListBox(M, N);
                    k++;
                    p--;
                }
            }
        }
        else // не последний элемент
        {
            if (M[p] > N)
            {
                while (M[p] > N) p--; // перемотать назад
            }
            else
            {
                if (!Strike(M, p)) // Если M[p] не накладывается з предыдущими M[1],M[2], ..., M[p-1]
                {
                    p++; // перейти на размещение следующего ферзя
                    M[p] = 0;
                }
            }
        }
    }

    // вывести количество вариантов размещения
    if (k > 0)
    {
        listBox1->SelectedIndex = 0;
        listBox1_Click(sender, e);
        label4->Text = "Количество вариантов размещения = " + k.ToString();
    }
}

 

3.8. Итоги программного кода

В программе введена внутренняя переменная N (количество ферзей и размер доски).

В программе (в классе Form1) реализованы следующие методы:

  • метод IsStrike() – проверяет, бъются ли две координаты по диагонали и по вертикали;
  • метод Strike() – проверяет «бьется» ли заданный ферзь с предварительно размещенными ферзями;
  • метод InitDataGridView() – осуществляет начальную инициализацию элемента управления dataGridView1 в зависимости от значения N;
  • метод ShowDataGridView() – отображает описанное размещение из входной строки s в dataGridView1;
  • метод AddToListBox() – преобразовывает размещение из массива M в строку специального формата s и добавляет эту строку в список listBox1;
  • два метода – обработчики событий listBox1_Click() и listBox1_KeyUp(), которые позволяют удобно пересматривать размещения при изменении выделенной строки в listBox1;
  • обработчик события button1_Click() клика на кнопке Start – реализует основной алгоритм размещения.

 

4. Запуск программы на выполнение. Тестирование работы

Результат выполнения программы показан на рисунке 5. Можно задавать разные значения N. Если значение N задать достаточно большое (N>13), то для получения решения придется нужно время.

C++ Приложения размещения N ферзей на доске размером N*N

Рисунок 5. Результат работы программы для количества ферзей N=7. Количество вариантов размещений равно 40