Rutina Backtracking nerecursiva:

k := 1; o8b8bh
INIT(k,st);
while k>0 do
Begin
Repeat
SUCCESOR(as,k,st);
If as then
VALID(ev,k,st);
Until (not as) or (as and ev);
If as then
If solutie(k) then
TIPAR else
Begin k := k+1;
INIT(k,st);
End else k := k-1
End; unde:
- pocedura SUCCESOR verifica daca mai sunt elemente in Ak;
VALID verifica daca sunt satisfacute conditiile de continuare;
TIPAR afiseaza o solutie rezultat.

Procedura Backtracking recursiva:

PROCEDURE back (k :integer);
BEGIN
If SOLUTIE(k) then
TIPAR else
Begin
INIT(k,st);
While as do
Begin
VALID(ev,k,st);
If ev then
Back(k+1);
End;
End;
END;

Obs:
1. Procedura Back are un parametru intreg k si functioneaza astfel:
• Daca s-a ajuns la o solutie se tipareste si se revine la nivelul anterior;
• Daca nu s-a ajuns la o solutie:
- se initializeaza nivelul;
- atata timp cat este succesor pe acest nivel,
- daca este valid, procedura Back se autoapeleaza pt. k+1 ;
- daca nu este succesor se trece pe nivelul k-1 prin iesirea din procedura Back.
? Procedura se apeleaza Back(1);

2. Functia SUCCESOR verifica daca mai sunt elementa in Ak;
3. Procedura VALID verifica daca sunt satisfacute conditiile de continuare;
4. Procedura TIPAR afiseaza o solutie rezultat;

5. Functia SOLUTIE returneaza true daca pe nivelul k s-a ajuns la solutie false daca pe nivelul k nu s-a ajuns la o solutie;
In general functia solutie se defineste astfel:

FUNCTION SOLUTIE(k:integer):boolean;
Begin
Solutie := (k = n+1);
End;

Programul de generare a permutarilor multimii A=A1,…,nS folosind backtracking-ul recursiv.

Type
Stiva = arraya1..100i of integer;
Var
St:stiva; i, k, n : integer; as, ev : boolean;

Procedure INIT(k:integer; var st:stiva);
Begin
Staki:=0;
End;

Procedure SUCCESOR(var as:boolean; k:integer; var st:stiva);
Begin
If staki<n then
Begin
Staki := staki+1; as := true;
End else as := false;
End;
Procedure VALID(var ev:boolean; k:integer; var st:stiva);
Begin ev := true;
For i := 1 to k-1 do
If staki = staii then ev := false;
End;

Procedure TIPAR;
Begin
For i := 1 to k do
write(staii,‘ ‘);
Writeln;
End;

Procedure BACK(k:integer);
Begin
If k = n+1 then tipar else
Begin
Init(k,st);
While as do
Begin
Valid(ev, k, st);
If ev then
Back(k+1);
End
End;
End;
Aprogram principalS
Begin
Write(‘n= ’); readln(n); back(1); end.