Backtracking-Problem

[mashutu]

Nur mal grob (hab das auch schon lange nicht mehr gemacht):

Du uebergibst eine Kopie deines Systemzustands an die rekursiv arbeitende Methode.
Scheitert die Methode beim Versuch den gewuenschten Zustand herzustellen veraenderst Du den Zustand und versuchst es erneut.

Pseudocode

Delphi-Quellcode:

function TesteDasSystem(var S:Tsystem):boolean;
  function SetzeZustand(S:TSystem):TSystem;
  begin
    result:=NIL;

    if Setze den naechstmoeglichen Zustand (S) then
      if Bedingung(S) then
        result:=S
      else
        result:=NIL;
  end;
var
  S2:TSystem;
begin
  S2:=SetzeZustand(S);
  if S2 <> NIL then
     if TesteDasSystem(S2) then
        S:=S2;
end;

In der Regel gibst man noch iterationspartameter mit und prueft wie tief das System ausgetestet wird oder kontrolliert so die Iterationstiefe.