Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0..n (число ферзей) и массива c: array [1..n] of 1..n (c [i] - координаты ферзя на i-ой горизонтали; при i > k значение c [i] роли не играет). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга).
program queens;
const n =...;
var k: 0..n;
c: array [1..n] of 1..n;
procedure begin_work; {начать работу}
begin
k:= 0;
end;
function danger: boolean; {верхний ферзь под боем}
var b: boolean;
i: integer;
begin
if k <= 1 then begin
danger:= false;
end else begin
b:= false; i:= 1;
{b <=> верхний ферзь под боем ферзей с номерами < i}
while i <> k do begin
b:= b or (c[i]=c[k]) {вертикаль}
or (abs(c[i]-c[k])=abs(i-k)); {диагональ}
i:= i+ 1;
end;
danger:= b;
end;
end;
function is_up: boolean {есть_сверху}
begin
is_up:= (k < n) and not danger;
end;
function is_right: boolean {есть_справа}
begin
is_right:= (k > 0) and (c[k] < n);
end;
{возможна ошибка: при k=0 не определено c[k]}
function is_down: boolean {есть_снизу}
begin
is_up:= (k > 0);
end;
procedure up; {вверх_налево}
begin {k < n}
k:= k + 1;
c [k]:= 1;
end;
procedure right; {вправо}
begin {k > 0, c[k] < n}
c [k]:= c [k] + 1;
end;
procedure down; {вниз}
begin {k > 0}
k:= k - 1;
end;
procedure work; {обработать}
var i: integer;
begin
if (k = n) and not danger then begin
for i:= 1 to n do begin
write ('<', i, ',', c[i], '> ');
end;
writeln;
end;
end;
procedure UW; {вверх_до_упора_и_обработать}
begin
while is_up do begin
up;
end
work;
end;
begin
begin_work;
UW;
while is_down do begin
if is_right then begin
right;
UW;
end else begin
down;
end;
end;
end.
Расчёт вычислительной сложности.
Емкостная сложность:
В программе используется одномерный массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество пременных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Временная сложность:
Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность T(n) = n0+n1+n2+n3+…+nn.
Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o(n0+n1+n2+n3+…+nn). И это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже статистических данных:
| Общее кол-во листьев | |||||||
| Кол-во вершин построенного дерева. | |||||||
| Время построения(сек) | <0.01 | <0.01 | <0.01 | <0.01 | <0.01 | <0.01 | <0.01 |
| Общее кол-во листьев | 
| 
| 
| 
| 
| 
|
| Кол-во вершин построенного дерева. | ||||||
| Время построения(сек) | <0.01 | 0.21 | 1.20 | 6.48 | 37.12 | 231.29 |
Тестирование.
Построенная по описанному алгоритму программа при различных n выдаёт следующие данные:
n=4
<1,2><2,4><3,1><4,3>
<1,3><2,1><3,4><4,2>
Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости от n количества решений (R).
| n = | |||||||||||||
| R= |
Cписок литературы.
1) Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
2) Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука, 1984.
3) Основной алгоритм находился на BBS “Master of Univercity” в файле shen.rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).