В этой главе рассмотрим ещё один приём перечисления всех элементов некоторого множества. Его называют ╚поиск с возвратами╩, ╚метод ветвей и границ╩ или ╚обход дерева╩.
Перед изучением темы необходимо познакомиться с понятиями: граф, дерево - связный граф с минимальным числом рёбер.

Обход дерева. Перебор с возвратами.

Во многих книгах приводятся головоломки, интересные тем, что для их решения не требуется особых математических или каких-либо  других специальных научных знаний. К таким задачам относятся поиск пути в сложном лабиринте, чтение текста ходом шахматного коня, расстановка фигур на шахматной доске таким образом, чтобы удовлетворить известным условиям.
Пример:   Дан лабиринт. Попадают в него в пункте А. Следует найти путь из пункта А до единственного выхода, расположенного в другом конце лабиринта. 
 
Находясь в точке А, мы не знаем, какой выход открыт и как к нему пройти. Поэтому на каждом перекрестке╩ лабиринта нужно выбрать одну из двух дорог. Договоримся сначала испытывать левую дорогу.

Из пункта А мы попадаем в пункт В, из В - в С, из С - в D. Отсюда дороги нет. Мы снова возвращаемся на ближайший ╚перекресток╩ С и из него пробуем пройти по новой дороге в пункт Е. Здесь мы обнаруживаем выход. Задача решена. Её решение - путь АВСЕ.

Заметим, узнав, что мы пошли неверным путем, мы не начинаем решать задачу заново, а делаем лишь один шаг назад и снова пытаемся идти с этого места. Если , сделав шаг назад, обнаруживаем, что нет новых неисследованных путей, делаем назад ещё один шаг и т.д. до тех пор, пока мы не доходим до места, из которого можно пойти новым, не испробованным путем. Если возвращаясь, мы дошли до исходной точки и из нее нет новых путей, то задача не имеет решения.

Решая любую задачу по программированию требуется сначала создать математическую модель. В задаче, которую мы будем рассматривать, такой моделью является дерево. Дерево это частный случай графа.
Граф в этой задаче служит для иллюстрации решения, вернее для поиска решения. Строя дерево мы классифицируем возможные варианты по какому-то признаку. Затем, анализируя полученную картинку. Отыскиваем способ перебора всех возможных вариантов.

В подобных задачах полезно рассмотреть частный случай (с фиксированным малым количеством переменных), на основе частного случая составить алгоритм и обобщить его на n переменных.

Задача о восьми ферзях - хорошо известный пример использования метода перебора с возвратом. В 1850 г. Эту задачу исследовал К.Ф.Гаусс, однако полностью он её так и не решил, т.к. для подобных задач характерно отсутствие аналитического решения. Они требуют огромного количества изнурительной работы. 
Задача: Перечислить все способы расстановки n ферзей на шахматной доске n n, при которых они не бьют друг друга.
Решение: Очевидно, что на каждой из n горизонталей должно стоять  по ферзю. Будем называть k-позицией (для k=0,1,...,n) произвольную расстановку k ферзей на k нижних горизонталях (ферзи могут бить друг друга).

Нарисуем ⌠дерево позиций■: его корнем будет единственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в (k+1)-позиции. Эти n позиций отличаются положением ферзя на (k+1)-ой горизонтали. Будем считать, что расположение их на рисунке соответствует  положению этого ферзя: левее та позиция, в которой ферзь расположен левее.

Среди позиций этого дерева нам надо отобрать те n-позиций, в которых ферзи не бьют друг друга. Программа будет ⌠обходить дерево■ и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.

Точнее, назовем k-позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции.

 
Дерево допустимых позиций для n=3
Разобьем задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимы позиций.
Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется робот, который в каждый момент находится в одной из вершин дерева (вершины изображены на рисунке кружочками). Он умеет выполнять команды:
  • вверх_налево (идти по самой левой из выходящих вверх стрелок)
  •  вправо (перейти в соседнюю справа вершину)
  • вниз (спуститься вниз на один уровень)
(На рисунках стрелками показано, какие перемещения соответствуют этим командам.)
вверх_влево
вправо
вниз
 Кроме того, в репертуар Робота входят проверки, соответствующие возможности выполнить каждую из команд:
  • есть_сверху;;
  • есть_справа;
  • есть_снизу;
(последняя проверка истинна всюду, кроме корня). Обратите внимание, что команда вправо позволяет перейти лишь к ⌠родному брату■, но не к ⌠двоюродному■.
Так команда вправо не действует!
Будем считать, что у Робота есть команда обработать и что его задача ≈ обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие есть_сверху ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей.
Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева, тогда все листья дерева разбиваются на три  категории: над Роботом, левее Робота, и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до нее и сворачивать вправо, не доходя до нее.) Через (ОЛ) обозначим условие ⌠обработаны все листья левее Робота■, а через (ОЛН) ≈ условие ⌠обработаны все листья левее и над Роботом■.

       Левее      Над      Правее
 
Нам потребуется такая процедура: 

procedure вверх_до_упора_и_обработать
 {дано: (ОЛ), надо: (ОЛН) }
begin
  {инвариант: ОЛ}
  while есть_сверху do  вверх_налево;
    {ОЛ, Робот в листе} 
  обработать; 
  {ОЛН} 
end; 
Основной алгоритм: 
дано: Робот в корне, листья не обработаны 
надо: Робот в корне, листья обработаны 
{ОЛ} 
вверх_до_упора_и_обработать; 
{инвариант: ОЛН} 
while есть_снизу do 
  if есть_справа then begin {ОЛН, есть справа} 
                   вправо;    {ОЛ} 
                   вверх_до_упора_и_обработать; 
                   end 
       else  вниз;    {ОЛН, не есть_справа, есть_снизу} 
   {ОЛН, Робот в корне   все листья обработаны} 
Осталось воспользоваться следующими свойствами команд Робота (в каждой строке в первой фигурной скобке записаны условия, в которых выполняется команда, во второй ≈ утверждения о результате ее выполнения): 
(1) {ОЛ, не есть_сверху} обработать {ОЛН} 
(2) {ОЛ} вверх_налево{ОЛ} 
(3) {есть_справа, ОЛН} вправо {ОЛ} 
(4) {не есть_справа, ОЛН} вниз {ОЛН} 
Реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0..n (число ферзей) и массива c: array [1..n] of 1..n ( c[i] - координаты ферзя на i-ой горизонтали). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга). 
 
 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 danger:=false 
        else 
          begin b:=false; i:=1; 
              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; 
 function is_down: boolean; {есть_снизу} 
   begin 
      is_down:=(k>0); 
   end; 
 procedure up; {вверх_налево} 
   begin {k<n, not danger} 
     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 write('<',i,',',c[i],'> '); 
             writeln; 
           end; 
   end; 
 procedure uw; {вверх_до_упора_и_обработать} 
   begin 
     while is_up do up; 
     work; 
   end; 
 BEGIN 
   begin_work; 
   uw; 
   while is_down do 
     if is_right then 
            begin right; uw; end 
        else down; 
 End. 
Литература: 
1.  Н.Я.Виленкин. Комбинаторика. 
2.  Уилсон. Введение в теорию графов. 
3.  В.А.Дагене, Г.К.Григас, К.Ф.Аугутис . 100 задач по программированию. 
4.  Ж.Арсак. Программирование игр и головоломок. 
5.  Н.Вирт. Алгоритмы и структуры данных. 
6.  С.Барт. Россыпи головоломок. 
7.  Математический энциклопедический словарь. 
8.  М.Гарднер. Математические досуги. 
Упражнения: 
1.  Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n ). Изменить реализацию операций с деревом позиций так, чтобы все три проверки есть_сверху / справа / снизу и соответствующие команды требовали бы количества действий, ограниченного не зависящей от n константой. 
2.  Использовать метод обхода дерева для решения задачи: дан массив из n целых положительных чисел a[1]...a[n] и число s; требуется узнать, может ли число s быть представлено как сумма некоторых из чисел массива. (Каждое число можно использовать не более чем по одному разу). 
3.  Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд ( нет куска вида ХХ).