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

ддускаюший простое условие окончания. если, кроме того, на каждом щаге число исследуемых лальвсйших путей фиксировано, скажем равно т, то используется схема (3.29), вызываемая оператором try{l) :.

procedure try{i: integer); var k: integer; begin k:=0;

repeat к:=1г+ I; выбрать k-й возможный путь; if приемлемо then begin записать его;

if i<n then (3.29)

begin try{i+ 1);

if неудачно then стереть запись

end end

until удачно У (k = m)

В остальной части этой главы рассматриваются еще три примера. В них представлены различные воплощения абстрактной схемы (3.29). Эти примеры также призваны иллюстрировать подходящее использование рекурсии.

задача о восьми ферзях

Задача о восьми ферзях - хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. В 1850 г. ею занимался К. Ф- Гаусс, но полного ее решения он не дал. Это и не удивительно. Для подобных задач Характерно отсутствие аналитического решения. Вместо этого они требуют большого объема изнурительных вычислений, Терпения и аккуратности. Поэтому такие задачи стали почти Исключительно прерогативой вычислительных машин, кото-обладают этими свойствами в гораздо большей степени, люди, даже гениальные.

Задача о восьми ферзях поставлена следующим образом 1см. также [3.4]): нужно так расставить восемь ферзей на ахматной доске, чтобы ни один ферзь не угрожал дру-

Чтобы идти дальше, нужно выбрать некоторое представление для данных. Поскольку мы знаем, что по шахматным правилам ферзь бьет все фигуры, расположенные на той же горизонтали, вертикали или диагонали доски, то мы заключаем, что каждая вертикаль может содержать одного и только одного ферзя, так что i-ro ферзя можно сразу помещать и, i-ю вертикаль. Итак, параметр i становится индексом вертикали, а выбор позиции ограничивается восемью bo.j-\;0)k-нымй значениями индекса горизонтали }.

Осталось решить, как представить расположение £Oi..bMH-ферзей на доске. Очевидно, что доску можно было бы вновь изобразить в виде квадратной матрицы, но после некоторого размышления мы обнаруживаем, что такое представление значительно усложнило бы проверку безопасности позиция,! Это крайне нежелательно, поскольку такая операция выпол-( няется наиболее часто. Поэтому нужно выбрать представление, которое насколько возможно упростит эту проверку. Лучше всего сделать наиболее доступной ту информацию, которая действительно важна и чаще всего используется. В нашем случае это не расположение ферзей, а информация том, помещен ли ферзь на данной горизонтали или диагонали. (Мы уже знаем, что на каждой k-n вертикали уже п мещен один ферзь для 1 /г i.) Это приводит к следуй щим описанвгм переменных:

var X : array [1.. 8] of integer;

a : array [IS] of Boolean; /3 gl)

b : array [bl.. b2] of Boolean;

с : array [cl.. c2] ol Boolean;

-

Используя схему (3.29) в качестве образца, мы легко ц i лучаем следующую предварительную версию алгоритма: Ч

procedure try{i: integer); begin

инициировать выбор позиции для i-eo ферзя; , repeat выбрать позицию; if безопасно then begin поставить ферзя; if < 8 then begin try{i +1);

if неудачно then убрать ферзя end end

until удачно V нет больше-позиции-;

указывает позицию ферзя на t-й вертикали; означает, что на /-й горизонтали нет ферзя; означает отсутствие ферзя на /г-й /-диaroнaли; означает отсутствие ферзя на /г-й \.-диагонали.

gbi6op индексных границ Ы, Ь2, с1, с2 определяется, ис-да-способа, которым вычисляются индексы b и с; мы

ямечаем, что на у*-диагонали все поля имеют одну и ту же сумму координат i и /, а на \-диагонали постоянна разность координат I - /. Соответствующее решение показано в программе 3.4.

1 2 3 4 5 6 7 8 Рис. 3.9. Одно из решений задачи о восьми ферзях.

При таких данных оператор поставить ферзя принимает следующую форму:

* И := /; а I/]: = false, b [i -f /] := false; с [i - j] := false

(3.32)

При уточнении оператора убрать ферзя мы получаем

a\j]:=true; b[i + j]:=true; c[i - j]:=true (3.33)

a Условие безопасно выполняется, если поле </, /> нахо-Тся на горизонтали и диагонали, которые еще свободны (представлены как true), что можно описать логическим выражением

all]Ab[i + }]Acli-l]. (3.34)

Этим завершается разработка алгоритма, который полностью описан в программе 3.4. Она дает решение * = 5, 3, 7, 2, 4), которое изображено на рис. 3.9.