Получать и, V из X, у просто - будем прибавлять к i разности координат, помещенные либо в массиве пар р ностей, либо в двух массивах отдельных разностей, эти массивы обозначены через а и & и соответствующим разом инициированы. Для нумерации следующего воз.мо ного хода можно использовать индекс k. Подробности noif заны в программе 3.3. Рекурсивная процедура вызыва

Рис. 3.8. Восемь возможных ходов коня.

в первый раз с параметрами хо, /о - координатами nwitj с которого начинается обход. Этому полю присваивается зна1 чение 1, остальные поля маркируются как свободные:

h [хо, Уо] := 1; try (2, Хо, уо, <?)

Не следует упускать еще одну деталь. Переменная /г ( , ) существует лищь в том случае, когда и я v находятся внут ри границ массива I ... п. Следовательно, выражение i (3.27), подставленное вместо он приемлем в (3.24), осмыс ленно, только если его первые две составляющие истиннь1 В программе 3.3 это условие подходящим образом перефор! мулировано, кроме того, двойное отнощение 1 и п за# нено выражением нin [1,2, п], которое при достаточ малых п обычно бывает более эффективным (см. разд. МОД, В табл. 3.1 приведены рещения, полученные при исходи* позициях <1,1>, <3,3> для п = 5 и <1,1> для п =6.

Параметр-результат q и локальную переменную ql мож* заменить глобальной переменной и тем самым несколЫ' упростить программу.

Каким образом теперь можно обобщить этот пример? кой схеме, типичной для задач подобного рода, он следУ^ Какие выводы можно сделать, изучая его? Характерная чег этого алгоритма состоит в том, что он предпринимает ка1* то щаги по направлению к общему решению, эти шаги Ф сируются (записываются), но можно возвращаться o6pai и стирать записи, если оказывается, что шаг не приводи'

jjifogram knightstovr (output); . const /rsa 5; rsg = 25; type index var i,j: index;

v q: boolean; .

и! s: set of index; . . . .

I ut,6:array[l. .8]ofih/eger;

Л: array [index, index] integer;

-jprocedure try (/: integer; x,y: index; var q: boolean);

var Ar,m,v: integer; ql: boolean;-begin /с := 0;

repeat k := k+l; gl := false; f u:= X + a{k]; v :=* у + b[k]; if (m in s)l\{v in then if h[u,v] 0 then begin h[u,v] ;= /; if i < nsq then begin try ii+l:,v,gl);

if -igl then Л[ ,г)] := 0 end else ql := true

until ffl V (k=S);

q:-==q\ . end {/; >} ;

begin s [1,2,3,4,5];

a[l] := 2; ВД := I; [2]:= 1;ВД:- 2; [3] -1; A[3] := 2; . [4J := -2; fc[4] := 1; [5] := -2; fc[5] := -1; Г7[6] := -1; fc[6I := -2; [7I: l;fc[7]:--2; m := 2; ад := -1; for i :=> 1 to 7? do

for jr := 1 to и do h{i,j] := 0; A[l,l] := 1; try{2,l,l,q); .

if 5 then

for i := 1 to n do

begin for / := 1 to л do write(h[i,j]:S); writeln

else mitelnd no solution ) end ,

Программа 3.3. Ход коня. .

Таблица 3.1. Три обхода конем

решению, а заводит в тупик . Такое действие называете возвратом. Из схемы (3.24) можно вывести общую схем) (3.28), если предположить, что число возможных дальнему ших путей на каждом шаге конечно:

procedure try\

begin инициировать выборку возможных шагов; repeat выбрать следующий шаг; if приемлемо then begin записать его;

if решение неполно then (3

begin попробовать очередной шаг;

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

until удача V больше нет путей end