Задача про 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#.

 

Міркування

Для додатку типу 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# Windows Forms Розв'язок задачі про 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# Windows Forms Розв'язок задачі про 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 = “Number of placements = “;
  • у label3 властивість Text = “Placements”;
  • у label4 властивість Text = “Current placement”;
  • у button1 властивість Text = “Start”;
  • в елементі управління Form1 властивість Text = “Placement of N Queens”.

Після налаштування елементів управління та коригування їх розмірів, форма додатку буде мати приблизний вигляд як показано на рисунку 4.

C# Шаблон Windows Forms Форма додатку

Рисунок 4. Форма додатку після налаштування

 

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

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

На даний момент текст модуля форми має наступний вигляд:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace PlacementNQueens
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
    }
}

 

3.2. Оголошення внутрішньої змінної N (кількість ферзів)

У текст класу вводиться внутрішня прихована (private) змінна N, яка визначає кількість ферзів для розміщення та розміри дошки

private int N; // кількість ферзів

Після вводу N, вигляд класу форми Form1 наступний:

...
public partial class Form1 : Form
{
    private int N; // кількість ферзів

    public Form1()
    {
        InitializeComponent();
    }
}
...

 

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

У текст класу Form1 вводиться метод IsStrike(). Метод є основою перевірки на накладання. Метод перевіряє, чи “б’ються” два ферзі з різними координатами. Метод отримує 4 цілочисельні параметри:

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

Метод повертає true, якщо два ферзі “б’ють” один одного. У методі відбувається перевірка як по горизонталі, так і по вертикалі.

Лістинг методу у класі Form1 наступний

...

public partial class Form1 : Form
{
    ...

    // Перевірка, чи б'ються 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 наступний:

...
public partial class Form1 : Form
{
    ...
    // Перевірка, чи накладається останній елемент 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.

Лістинг методу InitDataGridView() у класі Form1 наступний

...

public partial class Form1 : Form
{
    ...

    // початкова ініціалізація 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.

Лістинг методу ShowDataGridView() у класі Form1 наступний

...

public partial class Form1 : Form
{
    ...

    // метод, що відображає в dataGridView1 рядок s,
    // N - кількість ферзів
    // приймаємо, що dataGridView1 вже ініціалізовано в розмір N*N
    void ShowDataGridView(string s, int N)
    {
        int i;
        int j;
        string xs, 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 = Convert.ToInt32(xs);
            y = Convert.ToInt32(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-"

Лістинг методу AddToListBox() у тексті форми Form1 наступний:

...

public partial class Form1 : Form
{
    ...

    // записати рядок в listBox1
    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 описується в темі:

Лістинг обробників подій Click та KeyUp елементу управління listBox1 наступний:

...

public partial class Form1 : Form
{
    ...

    private void listBox1_Click(object sender, EventArgs e)
    {
        if (listBox1.Items.Count <= 0) return;
        int num;
        string s;
        num = listBox1.SelectedIndex;
        s = listBox1.Items[num].ToString();
        ShowDataGridView(s, N);
    }

    private void listBox1_KeyUp(object sender, KeyEventArgs e)
    {
        if (listBox1.Items.Count <= 0) return;
        int num;
        string s;
        num = listBox1.SelectedIndex;
        s = listBox1.Items[num].ToString();
        ShowDataGridView(s, N);
    }
}

...

 

3.7. Програмування події Click на кнопці Start. Реалізація алгоритму пошуку розміщень

При натиску клавіші Start користувач повинен отримати перелік варіантів розміщення N ферзів. Усе це здійснюється в обробнику події Click, який викликається при натиску на кнопці Start.

В обробнику події реалізується алгоритм, який описаний в п. 1.3.

Лістинг обробника події наступний:

...

public partial class Form1 : Form
{
    ...

    // Команда "Start"
    private void button1_Click(object sender, EventArgs e)
    {
        const int MaxN = 20;
        int[] M = new int[MaxN]; // масив, що формує циклічні вкладення
        int p; // покажчик (номер) на ферзя, який розміщується
        int k; // кількість варіантів розміщення

        // взяти кількість ферзів
        N = Convert.ToInt32(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);
            label2.Text = "Number of placements = " + 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 ферзів на дошці Результат

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