Задача о N ферзях. Решение с использованием Delphi

Задача о N ферзях. Решение с использованием Delphi


Содержание





Введение

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

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

 

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

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

Задачу реализовать в системе программирования Delphi (любой версии) как приложение типа VCL Forms Application — Delphi.

 

Соображения

Для приложения типа VCL Forms Application система Delphi предоставляет соответствующие элементы управления для удобной визуализации полученных вариантов размещений.

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

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

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

 

Выполнение

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

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

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

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

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

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

Delphi. Вариант размещения 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-го ферзя: (x, y) => (M[N], N)

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

 

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

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

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

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

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

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

Delphi. Размещение N ферзей на шахматной доске. Алгоритм решения

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

 

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

2.1. Запустить Delphi. Создать проект по шаблону VCL Forms Application — Delphi

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

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

 

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

Из панели Tool Palette разместить на форме приложения следующие компоненты:

  • четыре компонента типа TLabel для отображения информационных сообщений. В результате будут созданы три экземпляра (объекта) типа TLabel, которые имеют имена Label1, Label2, Label3, Label4. Один из этих компонентов будет отображать число вариантов размещений;
  • один компонент типа TEdit. Создается экземпляр (объект) с именем Edit1;
  • один компонент типа TListBox. Создается экземпляр с именем ListBox1;
  • один компонент типа TStringGrid. Создается экземпляр с именем StringGrid1. Этот компонент будет отображать размещение на доске;
  • один компонент типа TButton. Создается экземпляр с именем Button1. Этот компонент будет запускать на выполнение процесс поиска размещений для заданного N.

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

Delphi. Приложение типа VCL Forms Application

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

 

2.2.2. Настройка компонент формы

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

  • в компоненте Label1 свойство Caption = «N = «;
  • в Label2 свойство Caption = «Placements»;
  • в Label3 свойство Caption = «Current placement»;
  • в Label4 свойство Caption = «Number of placements = «;
  • в Button1 свойство Caption = «Start»;
  • в компоненте Form1 свойство Caption = «Placement of N Queens»;
  • в Edit1 свойство Text =»».

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

Delphi. Проект VCL Forms Application. Главная форма

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

 

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

3.1. Текст модуля Unit1.pas

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

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Button1: TButton;
    Label2: TLabel;
    ListBox1: TListBox;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    Label4: TLabel;

  private
    { Private declarations }

  public
    { Public declarations }

  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

end.

 

3.2. Объявление переменных, констант и типов данных

С целью удобства работы с процедурами и функциям, в текст класса нужно ввести:

  • константу Max, определяющую максимально возможное количество ферзей;
  • внутреннюю скрытую (private) переменную N, которая определяет текущее количество ферзей;
  • тип TArray, который необходим для передачи массива целых чисел в функцию в качестве параметра.

После выполненных действий, сокращенный листинг программы будет иметь следующий вид:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;

const
  Max = 20; // максимальное количество ферзей и размер доски

type
  TArray = array [0..Max] of integer; // вспомогательный тип - массив

  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Button1: TButton;
    Label2: TLabel;
    ListBox1: TListBox;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    Label4: TLabel;

    private
      { Private declarations }
      N:integer; // количество ферзей, размер доски
    public
      { Public declarations }
    end;

...

 

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

В класс формы модуля Unit1.pas вводятся функции Strike() и IsStrike(). В раздел implementation вводятся тексты функций. Функции служат основой проверки «бьющихся» ферзей.

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

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

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

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

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

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

Листинг методов Strike() и IsStrike() в разделе implementation следующий:

...

implementation

{$R *.dfm}

// проверка, бьются ли два ферзя
function TForm1.IsStrike(x1, y1, x2, y2:integer):boolean;
var
  tx, ty:integer;
begin

  // 1. Горизонталь, вертикаль
  // Ферзи бьют друг друга, если любый 2 значення-параметра совпадают
  if (x1=x2) or (y1=y2) then
  begin
    IsStrike := true;
    exit;
  end;

  // 2. Главная диагональ
  // 2.1. Влево-вверх
  tx := x1-1;
  ty := y1-1;
  while (tx>=1)and(ty>=1) do
  begin
  if (tx=x2)and(ty=y2) then
  begin
    IsStrike:=true;
    exit;
  end;
  tx:=tx-1; ty:=ty-1;
end;

  // 2.2. Вправо-вниз
  tx:=x1+1; ty:=y1+1;
  while (tx<=N)and(ty<=N) do
  begin
    if (tx=x2) and (ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx+1;
    ty:=ty+1;
  end;

  // 3. Дополнительная диагональ
  // 3.1. Вправо-вверх
  tx:=x1+1; ty:=y1-1;
  while (tx<=N)and(ty>=1) do
  begin
    if (tx=x2)and(ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx+1;
    ty:=ty-1;
  end;

  // 3.2. Влево-вниз
  tx:=x1-1; ty:=y1+1;
  while (tx>=1)and(ty<=N) do
  begin
    if (tx=x2)and(ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx-1;
    ty:=ty+1;
  end;
  IsStrike:=false;
end;

function TForm1.Strike(M: TArray; p: Integer):boolean;
var
  px, py, x, y, i: integer;
begin
  px := M[p];
  py := p;

  for i:=1 to p-1 do
  begin
    x := M[i];
    y := i;

    if IsStrike(x,y,px,py) then
    begin
      Strike:=true;
      exit;
    end;
  end;
  Strike:=false;
end;

...

Предварительно в классе формы Form1 должны быть описаны сигнатуры функций

...

TForm1 = class(TForm)
  Label1: TLabel;
  Edit1: TEdit;
  Button1: TButton;
  Label2: TLabel;
  ListBox1: TListBox;
  Label3: TLabel;
  StringGrid1: TStringGrid;
  Label4: TLabel;

private
  { Private declarations }
  N:integer; // количество ферзей, размер доски

public
  { Public declarations }
  function IsStrike(x1, y1, x2, y2:integer):boolean;
  function Strike(M:TArray; p:integer):boolean;
end;

...

 

3.4. Процедуры отображения размещения в StringGrid1

Компонент StringGrid1 используется для отображения размещения записанного в ListBox1. Компонент StringGrid1 представляет собой двумерную таблицу строк, которая удобно настраивается и обрабатывается. В программе для работы с компонентом StringGrid1 используются две процедуры InitStringGrid() и ShowStringGrid().



 

3.4.1. Включение сигнатур процедур работы с компонентом StringGrid1 в текст класса TForm1

Перед реализацией процедур работы с компонентом StringGrid1, в текст класса TForm1 в разделе public (или private) нужно ввести следующие сигнатуры процедур

...
TForm1 = class(TForm)
...
private
  { Private declarations }
  N:integer; // количество ферзей, размер доски

public
  { Public declarations }
  ...
  // процедуры обработки TStringGrid
  procedure InitStringGrid(N:integer);
  procedure ShowStringGrid(s:string; N:integer);
end;
...

 

3.4.2. Инициализация и настройка StringGrid1. Процедура InitStringGrid()

В процедуре InitStringGrid() реализована начальная инициализация StringGrid1 программным путем. Процедура получает входным параметром значение N.

Листинг процедуры InitStringGrid() в классе Form1 следующий

...
// инициализация StringGrid
procedure TForm1.InitStringGrid(N: Integer);
var
  i,j:integer;
begin
  // края доски
  StringGrid1.FixedCols:=1;
  StringGrid1.FixedRows:=1;

  // размеры доски
  StringGrid1.RowCount:=N+1;
  StringGrid1.ColCount:=N+1;

  // заголовок
  for i:=1 to N do
  begin
    StringGrid1.Cols[i].Text:=IntToStr(i);
    StringGrid1.Rows[i].Text:=IntToStr(i);

    // ширина колонки
    StringGrid1.ColWidths[i]:=30;
  end;

  // ширина нулевой колонки
  StringGrid1.ColWidths[0]:=35;

  // очистка ячеек
  for i:=1 to N do
    for j:=1 to N do
      StringGrid1.Cells[i,j]:='';
end;
...

 

3.4.3. Отображение строки из ListBox1 в StringGrid1. Метод ShowStringGrid()

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

Процедура ShowStringGrid() предназначена для обработки выделенной строки в ListBox1 и визуализации координат ферзей, представленных в этой строке. Сформированные в виде строки координаты ферзей визуализируются в StringGrid1.

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

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

Листинг процедуры ShowStringGrid() в разделе implementation следующий

...
// Процедура, отображающая в StringGrid1 строку s,
// N - количество ферзей
// принимаем, что StringGrid1 уже инициализировано в размер N*N
procedure TForm1.ShowStringGrid(s: string; N: Integer);
var
  i, j:integer;
  xs, ys:string;
  x, y:integer;
begin
  // очистить StringGrid1
  for i:=1 to N do
    for j:=1 to N do
      Form1.StringGrid1.Cells[i,j]:='';

  j:=0; // смещение
  for i:=1 to N do
  begin
    // сформировать xs
    xs:='';
    while s[j+1] <> ',' do
    begin
      xs:=xs+s[j+1];
      j:=j+1;
    end; // xs - число x в виде строки

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

    // сформировать ys
    ys:='';
    while s[j+1]<>'-' do
    begin
      ys:=ys+s[j+1];
      j:=j+1;
    end;

    // прокрутить
    j:=j+1;

    x:=StrToInt(xs);
    y:=StrToInt(ys);

    // обозначить позицию x,y ферзя
    StringGrid1.Cells[x,y]:='X';
  end;
end;
...

 

3.5. Программирование события активизации формы OnActivate

На этом этапе в обработчик события OnActivate главной формы программы Form1 нужно ввести вызов метода InitStringGrid().

Подробный пример программирования события в системе Delphi описывается в теме:

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

// Активизация формы
procedure TForm1.FormActivate(Sender: TObject);
begin
  InitStringGrid(1);
end;

 

3.6. Процедуры работы с ListBox1
3.6.1. Добавление размещения в ListBox1 в формате строки. Процедура AddToListBox()

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

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

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

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

Предварительно, в текст класса TForm1 нужно ввести сигнатуру процедуры AddToListBox():

TForm1 = class(TForm)
...
private
  { Private declarations }
  N:integer; // количество ферзей, размер доски
public
  { Public declarations }
  ...
  // добавить строку s в ListBox1 в заданном формате
  procedure AddToListBox(M:TArray; N:integer);
end;

Листинг процедуры AddToListBox() в разделе implementation следующий:

...
// записать строку в listBox1
// входные параметры: M - массив чисел, N - количество элементов в массиве M
procedure TForm1.AddToListBox(M:TArray; N:integer);
var
  s:string;
  i:integer;
begin
  for i:=1 to N do
    s:=s+IntToStr(M[i])+','+IntToStr(i)+'-';
  ListBox1.Items.Add(s);
end;
...

 

3.6.2. Программирование обработчика события Click компонента ListBox1

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

Более подробный пример того, как программируется обработчик события в Delphi описывается в теме:

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

...
// клик на строке в ListBox1
procedure TForm1.ListBox1Click(Sender: TObject);
var
  num:integer;
begin
  if ListBox1.Items.Count<=0 then
    exit;
  num:=ListBox1.ItemIndex;
  ShowStringGrid(ListBox1.Items[num],N);
end;
...

 

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

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

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

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

...
// Обработчик события Click элемента управления Button - реализует размещение
procedure TForm1.Button1Click(Sender: TObject);
var
  M:TArray; // массив, формирующий размещения ферзей
  p:integer; // номер размещаемого ферзя
  k:integer; // количество вариантов размещения
begin
  // взять количество ферзей
  N:=StrToInt(Edit1.Text);

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

  // очистить listBox1
  ListBox1.Items.Clear;

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

  // цикл поиска вариантов размещений
  while p>0 do
  begin
    M[p]:=M[p]+1;
    if p=N then // последний элемент
    begin
      if M[p]>N then
        while M[p]>N do p:=p-1 // перемотать обратно
      else
      begin
        if not Strike(M,p) then
        begin
          // зафиксировать размещение
          AddToListBox(M,N);
          k:=k+1;
          p:=p-1;
        end;
      end;
    end
    else // не последний элемент
    begin
      if M[p]>N then
        while M[p]>N do p:=p-1 // перемотать обратно
      else
      begin
        if not Strike(M,p) then
        begin
          p:=p+1;
          M[p]:=0;
        end;
      end;
    end;
  end;

  // вывести количество варіантов размещения
  if k>0 then
  begin
    ListBox1.ItemIndex:=0;
    ListBox1Click(Sender);
    Label4.Caption:='Number of placements = ' + IntToStr(k);
  end;
end;
...

 

3.8. Листинг интерфейсной части модуля Unit1.pas

С целью проверки, ниже приведен листинг интерфейсной части (раздел interface) с полным текстом класса TForm1.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;

const
  MaxN = 20; // максимальное количество ферзей и размер доски

type
  TArray = array [0..MaxN] of integer;

  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Button1: TButton;
    Label2: TLabel;
    ListBox1: TListBox;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    Label4: TLabel;
    procedure FormActivate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure ListBox1Click(Sender: TObject);
  private
    { Private declarations }
    N:integer; // количество ферзей, размер доски
  public
    { Public declarations }
    function IsStrike(x1, y1, x2, y2:integer):boolean;
    function Strike(M:TArray; p:integer):boolean;

    // обработка TStringGrid
    procedure InitStringGrid(N:integer);
    procedure ShowStringGrid(s:string; N:integer);

    // добавить строку s в ListBox1 в заданном формате
    procedure AddToListBox(M:TArray; N:integer);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

// Реализация процедур и функций
// ...

end.

 

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

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

Delphi Програма размещение N ферзей Результат

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