30. Применение алгоритмов с возвратом к задачам о ходе коня и о ферзях

 

Дана доска размером n*n, т. е. содержащая n^2 полей. Вначале на поле с координатами x0, y0 помещается конь — фигура, переме­щающаяся по обычным шахматным правилам. Задача заключа­ется в поиске последовательности ходов (если она существует), при которой конь точно один раз побывает на всех полях доски (обойдет доску), т. е. нужно вычислить n2 - 1 ходов.

Очевидный прием упростить задачу обхода n^2 полей — решать более простую: либо выполнить очередной ход, либо доказать, что никакой ход не возможен.

Если мы хотим описать этот алгоритм более детально, то нуж­но выбрать некоторое представление для данных. Доску, самое простое, можно представлять как матрицу, назовем ее h. Введем, кроме того, тип для индексирующих значений:

Из-за того, что мы хотим знать историю продвижения по доске, поля ее будем представлять целыми числами, а не булевскими значениями, позволяющими лишь определять занятость поля. Очевидно, можно остановиться на таких соглашениях:

 

h [х, у] = 0: поле <х, у> еще не посещалось;                                                                                           (3.26)

h [х, у] = i:   поле <х, у> посещалось на i'-м ходу.

 

 Теперь нужно выбрать соответствующие параметры. Они долж­ны определять начальные условия следующего хода и результат (если ход сделан). В первом случае достаточно задавать коорди­наты поля (х, у), откуда следует ход, и число i, указывающее но­мер хода (для фиксации). Для результата же требуется булевский параметр; если он — "истина", то ход был возможен.

 Какие операторы можно уточнить на основе принятых реше­ний? Очевидно, условие доска не заполнена можно переписать как i < п2. Кроме того, если ввести две локальные переменные u и v для возможного хода, определяемого в соответствии с правилами "прыжка" коня, то предикат подходит можно представить как ло­гическую конъюнкцию условий, что новое поле находится в пре­делах доски (1 <= u <= n  и 1 <=  v <= n) и еще не посещалось (huv = 0).

 Фиксация допустимого хода выполняется с помощью присваи­вания huv := i, а отмена — с помощью huv := 0. Если ввести локаль­ную переменную q1 и использовать ее в качестве параметра-ре­зультата при рекурсивных обращениях к этому алгоритму, то q1 можно подставить вместо удача. Так мы приходим к следующему варианту:

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

Если задана начальная пара координат х, у, то для следующего хода u, v существует восемь возможных кандидатов. На рис. 3.8 они пронумерованы от 1 до 8. Получать u, v из х, у очень просто, достаточно к последним добавлять разности между координата­ми, хранящиеся либо в массиве разностей, либо в двух массивах, хранящих отдельные разности. Обозначим эти массивы через dx и dy и будем считать, что они соответствующим образом иниции­рованы. Для нумерации очередного хода-кандидата можно исполь­зовать индекс k. Подробности показаны в листинге 3.3. Первый раз к рекурсивной процедуре обращаются с параметрами х0 и у0 -координатами поля, с которого начинается обход.

 

Нельзя упускать еще одну деталь. Переменная huv, существует только в том случае, если и u и v лежат в диапазоне индексов 1... n. Следовательно, выражение в (3.27), подставленное вместо подходит из (3.24), осмысленно, только если его четыре первые состав­ляющие истинны. Именно поэтому важно, чтобы составляющая huv = 0 была последней. В табл. 3.1 приводятся решения для трех исходных позиций: (3,3) и (2,4) при n = 5 и (1,1) при n = 6.

Какой же вывод можно сделать из этого примера? Какой схеме мы в нем следовали, типична ли она для алгоритмов поиска ре­шения? Чему этот пример научил нас? Характерное свойство та­ких алгоритмов заключается в том, что в них делаются шаги в на­правлении общего решения, но все они фиксируются (записыва­ются) таким образом, что позже можно вернуться вспять, отбра­сывая тем самым шаги, которые ведут в тупик, а не к общему решению. Такой процесс называется возвратом или откатом (backtracking). Если предположить, что число потенциальных шагов конечно, то из алгоритма (3.24) можно вывести универсаль­ную схему:

PROCEDURE Try;

BEGIN инициация выбора кандидата;

REPEAT выбор очередного кандидата;

 IF подходит THEN

его запись;

 IF решение неполное THEN Try;                                               (3.28)

IF неудача THEN стирание записи END

END

END

UNTIL удача OR кандидатов больше нет END Try;

 

  В реальных программах могут, конечно, встречаться и другие варианты, получающиеся из схемы (3.28). Часто, например, встре­чается построение с явным параметром для уровня, когда указы­вается глубина рекурсии. Это приводит к простым условиям окон­чания работы. Более того, если на каждом шаге число исследуе­мых путей фиксировано (пусть оно равно m), то можно применять

еще одну выведенную схему (к ней надо обращаться с помощью оператора Тrу(1)):

PROCEDURE Try(i: INTEGER);

  VAR k: INTEGER;

BEGIN k := 0;

REPEAT k := k+1;- выбор k-ro кандидата;

IF подходит THEN

его запись;                                                                            (3.29)

IF i < n THEN Try(i+1);

IF неудача THEN стирание записи END

END

END

 UNTIL удача OR (k = m)

END Try;

 


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

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

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

 

PROCEDURE Try(i: INTEGER);

BEGIN

инициация выбора положения io ферзя;

   REPEAT выбор очередного положения;

IF безопасно THEN поставить ферзя;

IF i < 8 THEN Try(i+1);                                                                       (3.30)

IF неудача THEN убрать ферзя END

 END

 END

        UNTIL удача OR мест больше нет

END Try;

 

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

Остается решить вопрос: как представлять на доске эти восемь ферзей? Очевидно, доску вновь можно было бы представить в виде квадратной матрицы, но после небольших размышлений мы об­наруживаем, что это значительно усложнило бы проверку безо­пасности поля. Конечно, подобное решение нежелательно, поскольку такая операция выполняется очень часто. Поэтому хоте­лось бы остановиться на таком представлении данных, которое, насколько это возможно, упростило бы проверку. В этой ситуа­ции лучше всего делать непосредственно доступной именно. ту информацию, которая действительно важна и чаще всего исполь­зуется. В нашем случае это не поля, занятые ферзями, а сведения о том, находится ли уже ферзь на данной горизонтали или диаго­нали. (Мы уже знаем, что на каждой k-й вертикали (1 <= k <= i) сто­ит только один ферзь.) Эти соображения приводят к таким опи­саниям переменных: 

 

VAR      x: ARRAY [1..8] OF INTEGER;

a: ARRAY [1..8] OF BOOLEAN;                                                                                  (3.31)

b: ARRAY [b1..b2] OF BOOLEAN;

c: ARRAY [c1..c2] OF BOOLEAN;

где

xi   обозначает местоположение ферзя на i-й вертикали;

aj   указывает, что на j-й горизонтали ферзя нет;

bk  указывает, что на k-й /-диагонали ферзя нет;

сk   указывает, что на k-й \-диагонали ферзя нет.

 

Выбор границ индексов b1, b2, с1, с2 определяется исходя из спо­соба вычисления индексов для b и с. На /-диагонали у всех полей постоянна сумма координат i и j, а на \-диагонали постоянна их разность. Соответствующие вычисления приведены в листин­ге 3.4. Если мы уже определили так данные, то оператор поста­вить ферзя превращается в такие операторы:

х[i]  := j;   a[j]  := FALSE;   b[i+j]   := FALSE; c[i-j]  := FALSE;                                                       (3.32)

а оператор убрать ферзя — в такие:

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

Условие безопасно выполняется, если поле с координатами i, j лежит на горизонтали и вертикали, которые еще не заняты. Сле­довательно, ему соответствует логическое выражение

а[j]   &  b[i+j] & c[i-j];                                                                                                                            (3.34)

На этом создание алгоритма заканчивается; полностью он пред­ставлен на листинге 3.4. Программа дает решение х = (1,5, 8, 6,3, 7, 2, 4), которое изображено на рис. 3.9.

1

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

6

 

 

 

 

 

 

 

7

 

 

 

 

 

 

 

8

 

 

 

 

 

 

 

 

1

2

3

4

5

6

7

8

 

Рис. 3.9.  Одно из решений задачи о восьми ферзях

 

Прежде чем закончить разбор задач, "посвященных" шахматной доске, мы воспользуемся задачей о восьми ферзях и представим одно важное обобщение алгоритма проб и ошибок. В общих ловах речь идет о нахождении не одного, а всех решений поставленное обобщение получается довольно легко.   Напомним, что формирование возможных кандидатов происходит регулярным образом, гарантирующим, что ни один кандидат не встретится более чем один раз. Такое свойство алгоритма обеспечивается тем, что поиск идет по дереву кандидатов так, что каждая из его вершин проходится точно один раз. Это позволяет, если найдено и должным образом зафиксировано одно решение, просто пере­ходить к следующему кандидату, предлагаемому упомянутым процессом систематического перебора. Общую схему такого про­цесса можно "вывести" из схемы (3.29):

Обратите внимание: из-за того что условие окончания в процес­се выбора свелось к одному отношению k = т, оператор повторе­ния со словом REPEAT заменится на оператор цикла с FOR. Удивительно, что поиск всех возможных решений выполняется более простой программой, чем в случае поиска одного-единственного решения. (Если бы программа отыскивала лишь 12 принципиально различных реше­ний, причем делала бы это максимально быстро, то и ома сама, и данные, кото­рыми она должна была бы манипулировать, оказались бы значительно более сложными.)

 Обобщенный алгоритм, приведенный в программе на листин­ге 3.5, отыскивает 92 решения задачи о восьми ферзях. Однако принципиально различных решений всего 12 — наша программа не учитывает симметрию. В табл. 3.2  приведены первые 12 реше­ний. Число п в правом столбце указывает, сколько раз проводи­лась проверка на "безопасность" поля. Среднее число для всех 92 решений равно 161.