![]() |
8 Damen Problem
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:
Ich hoffe ihr könnt wir helfen.
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; MfG, Blacky |
AW: 8 Damen Problem
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:
Zitat:
Zitat:
Delphi-Quellcode:
oder
if ... = False then
Delphi-Quellcode:
beibringt, dem sollte man mal auf die Finger hauen.
if ... = True then
Wobei es komisch ist, denn auch das war schonmal richtig. Zitat:
Delphi-Quellcode:
. :angel:
if not found then
|
AW: 8 Damen Problem
Zitat:
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:
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. |
AW: 8 Damen Problem
Mit einem OOP-Ansatz würdest du den Code erheblich vereinfachen können.
Delphi-Quellcode:
Pack alle Felder in eine Liste und teile dann jedem Feld die relevanten Nachbarn mit (bei 8x8 hat jedes Feld 21-27 relevante Nachbarn).
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; 21 Nachbarn
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:
(Frei hingetippt, müsste aber so funktionieren)
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; |
AW: 8 Damen Problem
Zitat:
|
AW: 8 Damen Problem
Zitat:
|
AW: 8 Damen Problem
Zitat:
|
AW: 8 Damen Problem
Hallo Sir,
hast du hier
Delphi-Quellcode:
nicht beim ersten Durchlauf eine undefinierte Situation?
if Felder[LIdx].KannDameHierSetzen then
Denn die Funktion
Delphi-Quellcode:
fragt zuerst die Property Dame ab, diese wurde aber zuvor nicht definiert, bzw. initialisiert
TFeld.KannHierDameSetzen
|
AW: 8 Damen Problem
Zitat:
Delphi-Quellcode:
Dann einfach TList<TFeld> durch TFeldList ersetzen.
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; |
AW: 8 Damen Problem
Zitat:
Delphi-Quellcode:
false
|
AW: 8 Damen Problem
Zitat:
|
AW: 8 Damen Problem
Weil private Felder immer mit der 0-Entsprechung ihres Typs initialisiert werden, im Falle von Boolean ist das false.
|
AW: 8 Damen Problem
Zitat:
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:51 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz