Задача о 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

Рисунок 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-го ферзя: (x, y) => (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.

Рисунок 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 отображена форма приложения после размещения элементов управления.

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

Рисунок 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 описывается в теме:

Пример программирования события в C#. Разработка программы для определения площади поверхности шара

Листинг обработчиков событий 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), то для получения решения придется немного подождать :).

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

⇑