МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Содержание 
1.	Постановка задачи. 
2.	Построение модели. 
3.	Описание алгоритма 
4.	Доказательство правильности алгоритма 
5.	Блок-схема алгоритма 
6.	Описание переменных и программа 
7.	Расчёт вычислительной сложности 
8.	Тестирование 
9.	Список литературы 
Постановка задачи 
Перечислить все способы расстановки n ферзей на шахматной доске n на n, при которых они не бьют друг друга 
Построение модели 
Очевидно, на каждой из n горизонталей должно стоять по ферзю. Будем называть k-позицией (для k = 0, 1,...,n) произвольную расстановку k ферзей на k нижних горизонталях (ферзи могут бить друг друга). Нарисуем "дерево позиций": его корнем будет единственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в (k+1)-позиции. Эти n позиций отличаются положением ферзя на (k+1)-ой горизонтали. Будем считать, что расположение их на рисунке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее 
Дерево позиций для n = 2 

Данное дерево представлено только для наглядности и простоты представления для n=2 
Среди позиций этого дерева нам надо отобрать те n-позиции, в которых ферзи не бьют друг друга. Программа будет "обходить дерево" и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении 
Точнее, назовем k-позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции 
Описание алгоритма 
Разобьем задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимых позиций 
Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева. Он умеет выполнять команды: 
вверх_налево (идти по самой левой из выходящих вверх стрелок) 
вправо (перейти в соседнюю справа вершину) 
вниз (спуститься вниз на один уровень) 
вверх_налево 
вправо 
вниз 
и проверки, соответствующие возможности выполнить каждую из команд, называемые "есть_сверху", "есть_справа", "есть_снизу" (последняя истинна всюду, кроме корня). Обратите внимание, что команда "вправо" позволяет перейти лишь к "родному брату", но не к "двоюродному" 
Будем считать, что у Робота есть команда "обработать" и что его задача - обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие "есть_сверху" ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей 
Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются на три категории: над Роботом, левее Робота и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до нее и сворачивать вправо, не доходя до нее.) Через (ОЛ) обозначим условие "обработаны все листья левее Робота", а через (ОЛН) - условие "обработаны все листья левее и над Роботом" 
Нам понадобится такая процедура: 
procedure вверх_до_упора_и_обработать 
{дано: (ОЛ), надо: (ОЛН)} 
begin 
{инвариант: ОЛ} 
while есть_сверху do begin 
вверх_налево 
end 
{ОЛ, Робот в листе} 
обработать; 
{ОЛН} 
end; 
Основной алгоритм: 
дано: Робот в корне, листья не обработаны 
надо: Робот в корне, листья обработаны 
{ОЛ} 
вверх_до_упора_и_обработать 
{инвариант: ОЛН} 
while есть_снизу do begin 
if есть_справа then begin {ОЛН, есть справа} 
вправо; 
{ОЛ} 
вверх_до_упора_и_обработать; 
end else begin 
{ОЛН, не есть_справа, есть_снизу} 
вниз; 
end; 
end; 
{ОЛН, Робот в корне => все листья обработаны} 
Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу - утверждения о результате ее выполнения): 
1.	{ОЛ, не есть_сверху} обработать {ОЛН} 
2.	{ОЛ} вверх_налево {ОЛ} 
3.	{есть_справа, ОЛН} вправо {ОЛ} 
4.	{не есть_справа, ОЛН} вниз{ОЛН} 
Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья) 
Решение. Пусть x - некоторая вершина. Тогда любая вершина y относится к одной из четырех категорий. Рассмотрим путь из корня в y. Он может: 
а) быть частью пути из корня в x (y ниже x); 
б) свернуть налево с пути в x (y левее x); 
в) пройти через x (y над x); 
г) свернуть направо с пути в x (y правее x); 
В частности, сама вершина x относится к категории в). Условия теперь будут такими: 
(ОНЛ) обработаны все вершины ниже и левее; 
(ОНЛН) обработаны все вершины ниже, левее и над 
Вот как будет выглядеть программа: 
procedure вверх_до_упора_и_обработать 
{дано: (ОНЛ), надо: (ОНЛН)} 
begin 
{инвариант: ОНЛ} 
while есть_сверху do begin 
обработать 
вверх_налево 
end 
{ОНЛ, Робот в листе} 
обработать; 
{ОНЛН} 
end; 
Основной алгоритм: 
дано: Робот в корне, ничего не обработано 
надо: Робот в корне, все вершины обработаны 
{ОНЛ} 
вверх_до_упора_и_обработать 
{инвариант: ОНЛН} 
while есть_снизу do begin 
if есть_справа then begin {ОНЛН, есть справа} 
вправо; 
{ОНЛ} 
вверх_до_упора_и_обработать; 
end else begin 
{ОЛН, не есть_справа, есть_снизу} 
вниз; 
end; 
end; 
{ОНЛН, Робот в корне => все вершины обработаны} 
Приведенная только что программа обрабатывает вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу: 
Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)". Под "обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над - полностью" 
Программа будет такой: 
procedure вверх_до_упора_и_обработать 
{дано: (ОНЛ), надо: (ОНЛН)} 
begin 
{инвариант: ОНЛ} 
while есть_сверху do begin 
обработать 
вверх_налево 
end 
{ОНЛ, Робот в листе} 
обработать; 
{ОНЛН} 
end; 
Основной алгоритм: 
дано: Робот в корне, ничего не обработано 
надо: Робот в корне, все вершины обработаны 
{ОНЛ} 
вверх_до_упора_и_обработать 
{инвариант: ОНЛН} 
while есть_снизу do begin 
if есть_справа then begin {ОНЛН, есть справа} 
вправо; 
{ОНЛ} 
вверх_до_упора_и_обработать; 
end else begin 
{ОЛН, не есть_справа, есть_снизу} 
вниз; 
обработать; 
end; 
end; 
{ОНЛН, Робот в корне => все вершины обработаны полностью} 
Доказательство правильности алгоритма 
Докажем , что приведенная программа завершает работу (на любом конечном дереве) 
Доказательство . Процедура вверх_налево завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются повторно, начиная с некоторого момента ни один лист не обрабатывается. А это возможно, только если Робот все время спускается вниз. Противоречие 
Блок-схема алгоритма 
Описание переменных и программа 
Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной 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) = n 0 +n 1 +n 2 +n 3 +…+n n 
Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o(n 0 +n 1 +n 2 +n 3 +…+n n ). И это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже статистических данных: 
	1 	2 	3 	4 	5 	6 	7 	
Общее кол-во листьев 	2 	7 	40 	341 	3906 	55987 	960800 	
Кол-во вершин построенного дерева. 	2 	3 	4 	17 	54 	153 	552 	
Время построения(сек) 	<0.01 	<0.01 	<0.01 	<0.01 	<0.01 	<0.01 	<0.01 	
	8 	9 	10 	11 	12 	13 	
Общее кол-во листьев 							
Кол-во вершин построенного дерева. 	2057 	8394 	35539 	166926 	856189 	4674890 	
Время построения(сек) 	<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 = 	1 	2 	3 	4 	5 	6 	7 	8 	9 	10 	11 	12 	13 	
R= 	1 	0 	0 	2 	10 	4 	40 	92 	352 	724 	2680 	14200 	73712 	
Cписок литературы 
1.	Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. 
2.	Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука, 1984. 
3.	Основной алгоритм находился на BBS “Master of Univercity” в файле shen.rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).