Задача про N ферзів. Розвʼязок з використанням Delphi
Зміст
- Вступ
- Умова задачі
- Міркування
- Виконання
- 1. Особливості реалізації алгоритму рішення задачі
- 2. Розробка програми
- 3. Написання програмного коду
- 3.1. Текст модуля Unit1.pas
- 3.2. Оголошення змінних, констант та типів даних
- 3.3. Функції Strike() та IsStrike(). Перевірка того, чи б’ються два ферзі з різними координатами
- 3.4. Процедури відображення розміщення в StringGrid1
- 3.5. Програмування події активізації форми OnActivate
- 3.6. Процедури роботи з ListBox1
- 3.7. Програмування події Click на кнопці Start. Реалізація алгоритму пошуку розміщень
- 3.8. Лістинг інтерфейсної частини модуля Unit1.pas
- 4. Запуск програми на виконання. Тестування роботи
Вступ
На олімпіадах з програмування часто зустрічається задача розміщення 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-го ферзя: (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.
Рисунок 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. Оголошення змінних, констант та типів даних
З метою зручності роботи з процедурами та функціям, у текст класу потрібно ввести:
- константу 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), то для отримання розв’язку потрібен деякий час.
Рисунок 5. Результат роботи програми для кількості ферзів N=8. Кількість варіантів розміщень рівна 92
⇑