Backtracking Problem?

[Thorben86]

Hi, ich sitz hier mit nem Programm, über Backtracking (konkret geht es darum, 8 damen auf einem schachbrett zu positionieren, ohne dass diese sich schlagen können.)

Allerdings Ergibt sich jedesmal ein StckOverflow, und die Variable Spalte ist am ende 9 Stellig. Könnte vielleciht einer mal drübergucken und nen tip geben, an welcher stelle der in eine unendliche Rekursion geht?

[Alexander]

Ich denke, es würden sich sicher viel mehr anschaun, wenn du es als zip anhängst (zip ist einfach standard...) oder wenn du die Problemstelle herauskristallisieren würdest.
PS: Hast du schon mal nach Damen-Problem gegoogelt. Ist eigentlich ein recht berühmtes rekursives Problem.

[nailor]

das problem mit zip ist halt, dass es mittlerweile echt veraltet ist.

[generic]

das muss aber nicht heissen das jeder unrar in der console bedienen will.
denn nicht jeder hat eine vollversion bzw raubkopie

[Alexander]

Zitat von generic:

das muss aber nicht heissen das jeder unrar in der console bedienen will.
denn nicht jeder hat eine vollversion bzw raubkopie

Genau . Hier in der SChule habe ich z.B. gerade nichts tun, kein RAR und keine Installationsrechte .
PS: Sonst benutze ich eigentlich auch eher rar...

Aber das ist jetzt OT

[atreju2oo0]

Hab nicht genug Zeit nach dem Fehler zu schauen aber falls es Dir hilft:
Hier ist meine Version! Is schon lange her und wahrscheinlich nicht so sauber geproggt aber dafür kann man die Lösungen auch manuell suchen... Für die Leute die sich mal anstrengen wollen...
Quelltext liegt mit bei... Und is auch RAR

[Thorben86]

Sry, hab gar nicht gemerkt, dass ich es als rar hatte, is standarteinstellung bei mir. Ich hänge es nochmal als Zip an.

Das mit dem Problem hab ich doch zum Teil schon im ersten post geschrieben, dass der irgendwo eine falsche abbruchbedingung hat und dadurch die Variable Spalte wahrscheinlich zu groß wird(9 stellige zahl, obwohl es nur 8 spalten geben dürfte).

[razer]

Hallo zusammen,

hab mal probiert das Programm ein wenig zu ordnen und unnötiges rauszuschmeißen.
Das Programm sieht bei mir jetzt folgendermaßen aus:

Delphi-Quellcode:

var
  Form1: TForm1;
  spalte:integer;
  zeile:integer;
  bedrohung:boolean;
  brett:array[1..8,1..8]of boolean;
  ergebnis:array[1..8]of integer;
  n:integer;

implementation

{$R *.DFM}

procedure TForm1.bedroht(Zeile,Spalte:integer; var bedrohung:boolean);
var k:integer;
begin

  k:=1;
  bedrohung:=false;
    while ((Zeile-k)>0) do
      begin
        if Brett[Zeile-k,Spalte]=true then    //überprüft Spalte
          begin
            bedrohung:=true;
          end;
        if ((Spalte-k)>0) and (Brett[Zeile-k,Spalte-k]=true) then    //überprüft X Daigonale
          begin
            bedrohung:=true;
          end;
        if ((Spalte+k)<(n+1)) and (Brett[Zeile-k,Spalte+k]=true) then   //überprüft Y Diagonale
          begin
            bedrohung:=true;
          end;
        k:=k+1;
      end;

end;

procedure TForm1.neueZeile(zeile:integer);
var y:integer;
begin

  spalte:=0;
  repeat
    spalte:=spalte+1;
    bedroht(zeile,spalte,bedrohung);
    if (spalte=n) and (bedrohung=true) then
    schiebe(zeile-1);
  until bedrohung=false;

  Brett[zeile,spalte]:=true;
  Ergebnis[zeile]:=spalte;

  if zeile<n then
    neueZeile(zeile+1)
  else
    for y:=1 to n do
    listbox1.Items.add(inttostr(ergebnis[y]));


end;

procedure TForm1.schiebe(zeile:integer);
var hilf,z:integer;
begin

  hilf:=0;

   for z:=1 to n do
     begin
       if brett[zeile,z]=true then
         begin
         brett[zeile,z]:=false;
         hilf:=z;
         end;
     end;

  spalte:=hilf;

  repeat
    if spalte<n then
    spalte:=spalte+1
      else
    schiebe(zeile-1);
      bedroht(zeile,spalte,bedrohung);
      if (spalte=strtoint(edit1.text)) and (bedrohung=true) then
      begin
        if zeile>1 then
        schiebe(zeile-1)
          else
        exit;
      end;
  until bedrohung=false;


  brett[zeile,spalte]:=true;
  ergebnis[zeile]:=spalte;

  
  neueZeile(zeile+1);   //<------


end;

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
  listbox1.clear;
  n:=strtoint(edit1.text);

  if (n=2) or (n=3) then
    begin
    showmessage('Für diesen Parameter gibt es keine Lösung');
    n:=0;
    end;

  for i:=1 to n do
    begin
    brett[i,i]:=false;
    end;

  neueZeile(1);

end;

Wenn man die Zeile mit dem Pfeil (<-----) rauslässt, kommt kein stackoverflow mehr, allerdings kommen falsche werte raus.
Leider komme ich an dieser Stelle auch nicht weiter. Ihr könnt ja nochmal drüberschauen.
Bis dann

[Garfield]

Zitat von generic:

das muss aber nicht heissen das jeder unrar in der console bedienen will.
denn nicht jeder hat eine vollversion bzw raubkopie

Ich bin nur zufällig hierher gekommen, aber bei so viel Unwissenheit muss ich was schreiben. Man braucht keine Vollversion oder Rabkopie. Über das Kontextmenü kann man WinRAR auch ohne Registrierung ohne Einschränkung nutzen. Nur wenn WinRAR selbst geöffnet wird, bekommt man einen NagScreen.

[Timo B.]

[edit] sorry, da hatte ich was falsch verstanden [/edit]