8 Damen Problem

[Blackwolf96]

Moin,

Ich soll das 8 Damen Problem lösen.

Ich komme aber beim Backtracking Part nicht weiter.
Das ist was ich bis jetzt habe:

Delphi-Quellcode:

procedure backtrack;
var x,y : integer;
    found: Boolean;
begin
  posi[LastQX,LastQY] := 0;
  found := False;
  AnzahlKoenigen := 0;
  for y := 0 to Kaestchen-1 do
    for x := 0 to Kaestchen-1 do
      if posi[x,y] = 1 then AnzahlKoenigen := AnzahlKoenigen+1; // Schaue wie viele Damen auf den Feld sind.

  for y := 0 to Kaestchen-LastQY do begin
    for x := 0 to Kaestchen do
      If (isValid(x,LastQY+y)) and (LastQX <> x) then begin // Schau ob es eine Valide Postition ist und nicht
        posi[x,LastQY+y] := 1;                             // die selbe wie vorher.
        found := True;
        AnzahlKoenigen := AnzahlKoenigen+1;
        break;
      end;
     if found then break;
  end;
  if found = false then begin                            //Wenn keine neue position gefunden werden kann suche 
    for y := Kaestchen downto 0 do                      // die nächste Dame und speichere die Position.
      for x := 0 to Kaestchen do
        if posi[x,y] = 1 then begin                     
          LastQX := x;
          LastQY := y;
          break;
        end;
  end;
end;

Ich hoffe ihr könnt wir helfen.
MfG,
Blacky

[himitsu]

Abgesehn davon, daß die hälfte der Variablendefinitionen und der verwendeten Funktionen fehlt.

Wo genau hängt es denn, bzw. was passiert oder nicht?


Dann solltest du mal in den Projektoptionen die Indexprüfung aktivieren, denn dann würde dir auffallen, daß bei den letzten beiden Schleifen etwas nicht stimmen kann.

Zitat:

Delphi-Quellcode:

for y := Kaestchen downto 0 do                      // die nächste Dame und speichere die Position.
  for x := 0 to Kaestchen do

Vorallem da du das Falschgemachte schonmal richtig gemacht hattest.

Zitat:

Delphi-Quellcode:

for y := 0 to Kaestchen-1 do
  for x := 0 to Kaestchen-1 do

Tipp: Von wo bis wo gehen deine Arrays? (egal ob jetzt vor- oder rückwärts)

Zitat:

Delphi-Quellcode:

if found = false then begin                            //Wenn keine neue position gefunden werden kann suche

Und dem, der das mit diesem

Delphi-Quellcode:

if ... = False then

oder

Delphi-Quellcode:

if ... = True then

beibringt, dem sollte man mal auf die Finger hauen.
Wobei es komisch ist, denn auch das war schonmal richtig.

Zitat:

Delphi-Quellcode:

if found then

Oder halt

Delphi-Quellcode:

if not found then

. :angel:

[Blackwolf96]

Zitat:

Zitat von himitsu (Beitrag 1265387)

Wo genau hängt es denn, bzw. was passiert oder nicht?

Es finde keine Lösung mit 8 Damen.

Kaestchen gibt an wieviele Kätchen es gibt. Momentan sind es fest 8.
LastQX, LastQX gibt die Position an wo die letzt Dame hin gesetzt wurde.

Zitat:

Zitat von himitsu (Beitrag 1265387)

Zitat:

Delphi-Quellcode:

for y := Kaestchen downto 0 do                      // die nächste Dame und speichere die Position.
  for x := 0 to Kaestchen do

Vorallem da du das Falschgemachte schonmal richtig gemacht hattest.

Zitat:

Delphi-Quellcode:

for y := 0 to Kaestchen-1 do
  for x := 0 to Kaestchen-1 do

Tipp: Von wo bis wo gehen deine Arrays?

Meine Arrays gehen von 0 bis 8, wo bei die 8 nicht benutzt wird.
Bei der ersten For schleife gehe ich von unten nach oben weil 0,0 oben links ist.
Damit ich die letzt Dame die gesetzt wurde finde.

[Sir Rufo]

Mit einem OOP-Ansatz würdest du den Code erheblich vereinfachen können.

Delphi-Quellcode:

TFeld = class
private
  FNachbarn : TList<TFeld>;
  FDame : Boolean;
public
  property Dame : Boolean read FDame write FDame;
  function KannHierDameSetzen : Boolean;
  procedure SetzeNachbarFeld( AFeld : TFeld );
end;

procedure TFeld.SetzeNachbarFeld( AFeld : TFeld );
begin
  FNachbarn.Add( AFeld );
end;

function TFeld.KannHierDameSetzen : Boolean;
var
  LFeld : TFeld;
begin
  if Dame then
    Exit( False );
  for LFeld in FNachbarn do
    if LFeld.Dame then
      Exit( False );
  Result := true;
end;

Pack alle Felder in eine Liste und teile dann jedem Feld die relevanten Nachbarn mit (bei 8x8 hat jedes Feld 21-27 relevante Nachbarn).

21 Nachbarn

F	N	N	N	N	N	N	N
N	N
N		N
N			N
N				N
N					N
N						N
N							N

27 Nachbarn

N			N			N
	N		N		N
		N	N	N
N	N	N	F	N	N	N	N
		N	N	N
	N		N		N
N			N			N
			N				N

Jetzt kannst du jedes Feld einzeln fragen, ob da eine Dame hin kann.

Mit einer Schleife suchst du jetzt für die erste Dame ein Feld (z.B. Feld 3). Dann startest du mit der nächsten Dame bei dem nächsten Feld (also Feld 4) usw. Findest du keine Lösung, so ist das eine Abbruchbedingung und du kehrst zur vorherigen Dame zurück und die versucht das nächste Feld.

Delphi-Quellcode:

function Solve( Felder : TList<TFeld>; MaxDame, Dame, StartFeld : Integer ) : boolean;
var
  LIdx : integer;
begin
  LIdx := StartFeld;
  // alle Felder durchlaufen
  while LIdx < Felder.Count do
  begin
    if Felder[LIdx].KannDameHierSetzen then
    begin
      // Dame auf Feld setzen
      Felder[LIdx].Dame := true;
      // Die letzte Dame gesetzt, dann haben wir eine Lösung
      if Dame = MaxDame then
        Exit( True );
      // Rekursiver Aufruf mit der nächsten Dame und dem nächsten Feld
      if Solve( Felder, MaxDame, Dame+1, LIdx + 1 ) then
        Exit( True );
      // Dame wieder vom Feld nehmen
      Felder[LIdx].Dame := false;
    end;
    // zum nächsten Feld
    Inc( LIdx );
  end;
  // keine Lösung gefunden
  Result := false;
end;

(Frei hingetippt, müsste aber so funktionieren)

[Blackwolf96]

Zitat:

Zitat von Sir Rufo (Beitrag 1265398)

Delphi-Quellcode:

  FNachbarn : TList<TFeld>;

Da scheint es einen Fehler zu geben. Es wird ausgegeben das er einen ';' erwartete aber ein '<' gefunden hat. :/

[Sir Rufo]

Zitat:

Zitat von Blackwolf96 (Beitrag 1265416)

Zitat:

Zitat von Sir Rufo (Beitrag 1265398)

Delphi-Quellcode:

  FNachbarn : TList<TFeld>;

Da scheint es einen Fehler zu geben. Es wird ausgegeben das er einen ';' erwartete aber ein '<' gefunden hat. :/

Da du keine Delphi Version angegeben hast, habe ich einfach mal die aktuelleren mit Generics vorausgesetzt ;)

[Blackwolf96]

Zitat:

Zitat von Sir Rufo (Beitrag 1265419)

Zitat:

Zitat von Blackwolf96 (Beitrag 1265416)

Zitat:

Zitat von Sir Rufo (Beitrag 1265398)

Delphi-Quellcode:

  FNachbarn : TList<TFeld>;

Da scheint es einen Fehler zu geben. Es wird ausgegeben das er einen ';' erwartete aber ein '<' gefunden hat. :/

Da du keine Delphi Version angegeben hast, habe ich einfach mal die aktuelleren mit Generics vorausgesetzt ;)

Oh das hätte ich machen sollen. :oops: Ich benutze Delphi 7.

[Helmi]

Hallo Sir,

hast du hier

Delphi-Quellcode:

if Felder[LIdx].KannDameHierSetzen then

nicht beim ersten Durchlauf eine undefinierte Situation?
Denn die Funktion

Delphi-Quellcode:

TFeld.KannHierDameSetzen

fragt zuerst die Property Dame ab, diese wurde aber zuvor nicht definiert, bzw. initialisiert

[Blup]

Zitat:

Zitat von Blackwolf96 (Beitrag 1265420)

Oh das hätte ich machen sollen. :oops: Ich benutze Delphi 7.

Delphi 7 kennt noch keine Generics, da muss man dann mehr von Hand machen.

Delphi-Quellcode:

type
  TFeld = class;
  TFeldList = class;

  TFeldListEnumerator = record
    constructor Create(AList: TFeldList);
  private
    FIndex: Integer;
    FList: TFeldList;
    function GetCurrent: TFeld;
  public
    function MoveNext: Boolean;
    property Current: TFeld read GetCurrent;
  end;

  TFeldList = class(TObjectList)
  protected
    function GetItem(Index: Integer): TFeld;
    procedure SetItem(Index: Integer; AObject: TFeld);
  public
    function GetEnumerator: TFeldListEnumerator;
    property Items[AIndex: Integer]: TFeld read GetItem write SetItem; default;
  end;

implementation

{ TFeldList }

function TFeldList.GetEnumerator: TFeld;
begin
  Result := TFeldListEnumerator.Create(Self);
end;

function TFeldList.GetItem(Index: Integer): TFeld;
begin
  Result := TFeld(inherited GetItem(Index));
end;

procedure TFeldList.SetItem(Index: Integer; AObject: TFeld);
begin
  inherited SetItem(Index, AObject);
end;

{ TFeldListEnumerator }

constructor TFeldListEnumerator.Create(AList: TFeldList);
begin
  FList  := AList;
  FIndex := -1;
end;

function TFeldListEnumerator.GetCurrent: TFeld;
begin
  Result := FList[FIndex];
end;

function TFeldListEnumerator.MoveNext: Boolean;
begin
  Result := (FIndex < FList.Count - 1);
  if Result then
    Inc(FIndex);
end;

Dann einfach TList<TFeld> durch TFeldList ersetzen.

[Sir Rufo]

Zitat:

Zitat von Helmi (Beitrag 1265427)

Hallo Sir,

hast du hier

Delphi-Quellcode:

if Felder[LIdx].KannDameHierSetzen then

nicht beim ersten Durchlauf eine undefinierte Situation?
Denn die Funktion

Delphi-Quellcode:

TFeld.KannHierDameSetzen

fragt zuerst die Property Dame ab, diese wurde aber zuvor nicht definiert, bzw. initialisiert

Das ist auch nicht nötig, denn bei der Erzeugung der Klasse TFeld wird dort der Default-Wert gesetzt und der ist

Delphi-Quellcode:

false