C++,MS Visual Studio 2010,Курсові роботи,Математичне ПЗ,Практика

C++. Задача про N ферзів. Розвʼязок на C++




Задача про N ферзів. Розвʼязок на C++

Зміст

Пошук на інших ресурсах:

Вступ

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

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

  ⇑

Умова задачі

Задано ціле число N (N>0), що визначає кількість ферзів на дошці розміром N×N. Розробити програму, яка знаходить усі можливі варіанти розміщення N ферзів таким чином, щоб вони не “били” один одного. У програмі забезпечити візуалізацію кожного отриманого варіанту.

Задачу реалізувати в системі Microsoft Visual Studio 2010 як додаток типу 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

Розміщення 5 ферзів на дошці розміром 5*5

Рисунок 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.

Розв'язок задачі про N ферзів. Алгоритм рішення

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

  ⇑

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

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

Завантажити систему Microsoft Visual Studio 2010 та зберегти проект. Детальний приклад створення проекту за шаблоном 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. Форма додатку

Рисунок 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
  {
  private:
    int N; // кількість ферзів

  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 ферзі, повертає false якщо не б'ються
    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 - кількість ферзів
// 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), то для отримання розв’язку доведеться трішки зачекати :).

Розміщення ферзів Результат кількість N=7

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

  ⇑