Backtracking-Problem

[pcbiker42]

Hallo liebe Delphigemeinde,
ich habe hier ein Problem mit einer Backtracking Prozedur, und zwar dreht es sich um folgendes:
Ich habe 4 Würfel, die auf jeder ihrer 6 Seiten eine von vier Farben tragen und nun sollen die Würfel so gelegt werden , dass oebn,unten,hinten und vorne jeweils jede der vier Farben genau einmal sichtbar wird.
Ich bin nun soweit dass ich eine Prozedur habe die den Würfel in alle 24 Lagen drehen kann. Nun komme ich bei der Konzeption/Umsetzung der Backtrackingprozedur nicht weiter. Im Grunde ist es ja so dass ich damit beginne den 1ten Würfel in der 1ten Lage liegen zuhaben und dann damit weiter mache den 2ten Würfel in eine Lage zu bringen die der Lösung des Problems entsprechend ist und das dann auch mit Würfel 3 und 4 zu tun. Allerdings stehe ich nun auf dem Schlauch bei der Umsetzung falls diese Idee erstmal stimmen sollte.

[mashutu]

Ich habe jetzt nicht die Zeit um auf Dein Problem im Detail einzugehen.
Die Idee ist in der Regel folgende:

type
tSystem = class(TObject)
cubes : TCubes;

end;

var xCubes : tSystem;
tSystem enthaelt eine Konfiguration Deiner Wuerfel.

Nun beginnst Du mit einem beliebigen Anfangszustand der Wuerfel und probierst dabei alle Moeglichkeiten durch indem Du eine prozedur rekursiv aufrufst. Wenn der Versuch erfolgreich war, gehst Du eine Ebene tiefer, wenn nicht wird die naechste Stellung ausprobiert.

[pcbiker42]

Erstmal vielen Dank für deine schnelle Antwort.
Dieses große Konzept hab ich ja mir auch schon zusammengebastelt. Mein Problem liegt in der Backtrackingprozedur, die ich dann rekursiv aufrufe. Ich weiß einfach nicht wie ich die angehe sollen.

[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.