Jedna z verzií algoritmu pre túto metódu môže byť zaznamenaná nasledovne:

Táto metóda je mnohokrát používaná v rekurzívnom zápise, čo je veľmi prehľadné a jednoduché. Rekurzívna verzia tejto metódy:

procedure Skus_dalsie_predlzenie;

Inicializácia výberu ďalšieho predĺženia;

Zaznamenaj predĺženie;

IF riešenie nie je úplné THEN

Skus_dalsie_predlzenie;

Problém ôsmich dám je jedným zo známych problémov, pri ktorých riešení je možné aplikovať metódu prehľadávania s návratom. Preskúmal ho C. F. Gauss v roku 1850, ale jeho riešenie nedoviedol do úspešného konca. Nepodarilo sa mu nájsť analytické vyjadrenie riešenia a preskúmať všetky možnosti bolo vtedy veľmi náročné na čas a pracné.

Osem dám je treba rozmiestniť na šachovnici takým spôsobom, aby sa navzájom neohrozovali (v zmysle šachových pravidiel). Príklad takého rozloženia je uvedený na Obr. 1.

Obr 1. Uloženie dám tak, že sa navzájom neohrozujú

Sformulujeme rekurzívnu procedúru v hrubých rysoch nasledovne:

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

Inicializácia výberu pozícií pre i-tú dámu;

Ulož dámu;

IF i<8 THEN

Skus_dalsiu_damu(i+1, q);

END; {Skus_dalsiu_damu}

Teraz vyjadríme jednotlivé nepresné formulácie v tejto procedúre a vytvoríme program, ktorý nájde jedno riešenie.

Prv než urobíme upresnenie uvedených formulácií, určíme dátové typy, s ktorými budeme pracovať, t.j. dátové typy, ktoré budú reprezentovať uloženie dámy a obsadenie riadkov a uhlopriečok.

Obsadenie j-tého riadku budeme zaznamenávať v poli a, kde j-tý prvok nadobudne hodnotu true, ak je riadok voľný a inak nadobudne hodnotu false. Teda deklarujeme

c: array [-7..7] of boolean;

Ak bude uhlopriečka voľná prvok poľa, ktorý ju reprezentuje nadobudne hodnotu true, inak nadobudne hodnotu false.

program Osem_dam;

{Najde jedno riesenie problemu 8 dam}var i: integer; {poradove cislo damy}

q: boolean; {q=true, ak je riesenie najdene}

a: array [1..8] of boolean; {vektor urcujuci obsadenie riadkov}

b: array [2..16] of boolean; {vektor urcujuci obsadenie diagonal}

c: array [-7..7] of boolean; {vektor urcujuci obsadenie diagonal}

x: array [1..8] of integer; {vektor urcujuci ulozenie dam}

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

{Rekurzivna metoda prehladavania s navratom pre postupne ukladanie dam}

var j: integer; {pozicia i-tej damy v riadku}

begin

j:= 0;

repeat

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

if a[j] and b[i+j] and c[i-j] then

begin {je mozne ulozenie v riadku j}

x[i]:= j; {ulozenie i-tej damy v j-tom riadku}

a[j]:= false;

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

if i<8 then

begin {pocet doposial ulozenych dam je

mensi ako 8}

Skus_dalsiu_damu(i+1, q);

if not q then

begin {posledna dama nemoze byt ulozena}

a[j]:= true; {v j_tom riadku}

b[i+j]:= true; c[i-j]:= true;

end

end else q:= true

end

until q or (j=8);

end; {Skus_dalsiu_damu}

begin {hlavny program}

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;

Skus_dalsiu_damu(1,q);

if q then

begin

write(' Riesenie problemu 8 dam: ');

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

end else writeln('Riesenie neexistuje.');

end.

Program nájde jediné riešenie: 1, 5, 8, 6, 3, 7, 2, 4.

Tento problém je tiež typickým problémom, pri ktorého riešení je možné použiť metódu prehľadávania s návratom. Problém je možné sformulovať nasledovne:

Z  pozícií v strede šachovnice má jazdec 8 možností skokov, na okraji a v rohoch menej, preto je potrebné kontrolovať, či indexy prvku poľa ďalšieho skoku sú na šachovnici. Uvedené možnosti skokov sú preskúmavané systematicky, rovnako pri každom skoku. Zmeny pozícií pri vykonaní ďalšieho skoku sú stanovené v poliach

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

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

To znamená, ak bol jazdec v pozícii [x, y] a vykoná k-tý skok, k=1, 2, .... 8, tak jeho nová pozícia bude [x+a[k], y+b[k].

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

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

{ a, b -- pomocne polia vyjadrujuce zmenu suradnic jazdca z danej

pozicie}

type index=1..n;

var i, j: integer; {Riadiace premenne cyklov}

s: set of index; {Mnozina pozicii v jednom smere}

q: boolean; {Vyjadruje, ci riesenie najdene}

h: array [index, index] of integer; {Sachovnica}

procedure vyskusaj(i: integer; x, y: index; var q: boolean);

{Vykona i-ty skok z pozicie (x, y) a rekuzivne pokracuje dalej;

q nadobudne hodnotu true, ak je riesenie najdene}

var k, u, v: integer;

q1: boolean;

begin

k:=0; {Inicializacia pre moznosti skokov}

repeat

k:= k+1; {Prechod na skumanie dalsej moznosti}

q1:= false; { pre i-ty skok}

u:= x+ a[k]; v:= y+ b[k];

{Vypocet novej pozicie pri k-tej moznosti}

if (u in s) and (v in s) then

if h[u, v]=0 then

begin {Skok je vykonatelny}

h[u, v]:= i;

if i<nsq then {Sachovnica este nie je pokryta}

begin {Prechod na vykonanie dalsieho skoku}

vyskusaj(i+1, u, v, q1);

if not q1 then h[u, v]:= 0;

{Zrusenie posledneho skoku}

end else q1:=true {Riesenie je najdene}

end

until q1 or (k=8);

q:= q1;

end; {vyskusaj}

begin {hlavny program}

s:= [];

for i:= 1 to n do s:= s + [i];

for i:= 1 to n do

for j:=1 to n do h[i, j]:= 0;

h[1, 1]:= 1; {Jazdec zacina na policku (1,1)}

vyskusaj(2, 1, 1, q);

if q then

for i:= 1 to n do

begin for j:= 1 to n do write(h[i, j]:3);

writeln

end else writeln(' Riesenie neexistuje ')

end.

Riešenie, ktoré je nájdené pre n=5: