8 Damen Problem

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