Постановка задачи 
   Перечислить все способы расстановки 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; 
   {ОЛН, Робот в корне => все листья обработаны}.
   Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу — 
утверждения о результате ее выполнения): 
   {ОЛ, не есть_сверху} обработать {ОЛН} 
   {ОЛ} вверх_налево {ОЛ} 
   {есть_справа, ОЛН} вправо {ОЛ} 
   {не есть_справа, ОЛН} вниз {ОЛН} 
   Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья). 
   Решение. Пусть 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
 
Библиографический список
1.   Кузнецов О. П. Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомизда