Алгоритми з поверненням

Особливо цікаві задачі так називаного штучного інтелекту. Тут мають справу з алгоритмами, що шукають рішення не за заданими правилами, а шляхом проб і помилок. Звичайно процес проб і помилок розділяється на окремі задачі. Часто ці задачі виражаються в термінах рекурсії і потребують дослідження кінцевої кількості підзадач.

Задача про вісьмох ферзів.Вісім ферзів треба так розставити на шаховій дошці, щоб жоден з них не загрожував іншому.

Оскільки ферзь вбиває всі фігури, що знаходяться на тій самій вертикалі, діагоналі та горизонталі, як наслідок: в одній вертикалі (діагоналі, горизонталі) може знаходитися один-єдиний ферзь. Таким чином, при пошуку місця дляi-ферзя можна граничитися i-ю вертикаллю. Індекс горизонталі jбуде змінюватися до восьми. В програмному прикладі 6.8 подано рішення цієї задачі.

{===== Програмний приклад 6.8 =====}

procedure chess;

var i: integer; q: boolean;

a: array [1..8]of boolean; b:array [2..16]of boolean;

c: array [–7..7]of boolean; x:array [1..8] of integer;

procedure try(i:integer; var q:boolean);

var j: integer;

begin j:=0;

repeat j:=j+1; q:=false;

if a[j] and b[I+j] and c[I- j] then {чи вільне місце?}

begin

x[i]:=j; a[i]:=false; {поставити ферзя}

b[i+j]:=false; c[I-j]:=false;

if i< 8 then

begin

try(I+1,q);

if not q then

begin {убрати ферзя}

a[j]:=true; b[I+j]:=true; c[I-j]:= true;

end else q:=true

end; end;

if q then write(i:4);

until q or (j= 8)

end;

begin

for i:=1 to 8 do a[i]:=true ;

for i:=2 to 16 do b[i]:=true ;

for i:=–7 to 7 do c[i]:=true ;

try (1,q);

for i:=1 to 8 do writeln (x[i]) ;

end.

Масив х зберігає місцезнаходження ферзя на i-вертикалі; a_jвказує, що наj-горизонталі немає ферзя; b_k вказує, що на k-ій побічній діагоналі немає ферзя;c_k вказує, що на k-й головній діагоналі немає ферзя.