if Cmp(Y,X) then f:=false;

end;

iffthenbegin

Inc(S);{счетчик числа решений, глобальная переменная}

Print;{выводрешения}

end;

end;

end;

2. Задача о шахматном коне

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

Разбор задачи начинается с оценки числа 64! - таково общее число способов разметки доски 8*8. Каждую разметку следует оценивать на предмет того, является ли она способом обхода конем доски(решение в “лоб”). Затем оцениваем порядок сокращения перебора исходя из условия - логика выбора очередного хода коня. Будем считать, что поля для хода выбираются по часовой стрелке. Объяснение иллюстрируется следующими рисунками.

Структуры данных.

Const N= ; M= ;

Dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1-2);

Dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);

Var A:array[-1..N+2,-1..M+2] of integer;

Основной фрагмент реализации - процедура Solve.

procedure Solve(x,y,l:integer);

var z,i,j:integer;

begin

A[x,y]:=l;

if l=N*M then Inc(t)

else for z:=1 to 8 do begin i:=x+Dx[z];j:=y+Dy[z];

if A[i,j]=0 then Rec(i,j,l+1)

end;

A[x,y]:=0;

end;

for i:=-1 to N+2 do for j:=-1 to M do A[i,j]:=-1;

for i:=1 to N do for j:=1 to M do A[i,j]:=0;