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

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

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

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

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

Программирование события в Delphi 2010

Листинг обработчика события 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 описывается в теме:

Программирование события в Delphi 2010

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

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

⇑