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

Алгоритм розміщення 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 і немає накладань між ферзями в поточному розміщенні, то це розміщення фіксується. У нашому випадку розміщення фіксується в списку 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–) і стає рівним 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 Програма розміщення N ферзів Головна форма

Рисунок 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. Оголошення змінних, констант та типів даних

З метою зручності роботи з процедурами та функціям, у текст класу потрібно ввести:

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

Після виконаних дій, скорочений лістинг програми буде мати наступний вигляд:

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;
  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() початкової ініціалізації елементу управління StringGrid1.

Детальний приклад програмування події в системі 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. Програма розміщення 8 ферзів на дошці

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