Home » Tutorials » Programmierkonzepte » Wege aus dem Labyrinth

Wege aus dem Labyrinth

Acht Damen und ein berühmter Mathematiker

Dieser berühmte Mathematiker ist Carl Friedrich Gauß (1777-1855). Er studierte zunächst alte Sprachen, interessierte sich aber im Alter von 17 Jahren für die Lösung des klassischen Problems, ein reguläres Heptagon oder eine siebenseitige Form mit Lineal und Zirkel zu konstruieren. Er fand auch Methoden zur Konstruktion von Formen mit 17, 257 und 65.537 Seiten.
Dieser große Deutsche also beschäftigte sich bereits 1850 mit folgendem Problem:

Acht Damen sind auf einem Schachbrett so aufzustellen, dass keine Dame eine andere bedroht.
Trotz seines genialen Geistes konnte Gauß dieses Problem mit den mathematischen Mitteln seiner Zeit nicht vollständig lösen. Erst durch systematisches Ausprobieren und mit einem schnellen Computer können solche Lösungen leicht gefunden werden.
Das systematische Ausprobieren erinnert mich wieder an den Anfang dieses Tutorials, nämlich an das „Versuch und Irrtum“-Verfahren; mit einem anderen Namen auch Backtracking-Verfahren genannt.
Wir wollen dieses bekannte Backtracking-Problem des Herrn Gauß etwas allgemeiner fassen und sagen:

n Damen sind auf einem Schachbrett mit n mal n Feldern so aufzustellen, dass keine Dame eine andere bedroht. Gesucht sind alle möglichen Aufstellungen.
Nach den Schachregeln bedroht bzw. schlägt eine Dame alle anderen Schachfiguren, die in der gleichen Zeile, Spalte oder Diagonale stehen.
Lösungen zu unserem Problem kannst du in der Demonstrationsdatei AlleWege am Ende dieses Tutorials finden. Wenn du willst, sieh dir diese Datei daraufhin an.
Durch systematisches Vorgehen nach der Methode von „Versuch und Irrtum“ findet man alle Lösungen, indem man zunächst (ein Schachbrett mit vier mal vier Feldern vorausgesetzt) die erste Dame auf das erste Feld der ersten Zeile stellt. Da in jeder Zeile nur eine Dame stehen darf, prüft man der Reihe nach die Felder der zweiten Zeile. Auf das dritte Feld der zweiten Zeile kann die zweite Dame aufgestellt werden. Im nächsten Schritt werden nun der Reihe nach alle Felder der dritten Zeile geprüft. In der dritten Zeile sind alle Felder bedroht. Die zuletzt aufgestellte Dame in der zweiten Zeile wird zurückgenommen und auf das nächste Feld in der zweiten Zeile gestellt. Für die dritte Dame wird nun eine Aufstellung in der dritten Zeile gefunden. Jetzt kann in die vierte Zeile keine Dame mehr gestellt werden. Auch jetzt muss das Backtracking wieder einsetzen und die Aufstellung der dritten Dame zurücknehmen. Auch eine Aufstellung der dritten Dame auf die nächsten Felder der dritten Zeile führen nicht zum Erfolg. Die nächsten Backtrackingschritte nehmen die Aufstellung der dritten, zweiten und ersten Dame zurück. Die erste Dame wird jetzt in der ersten Zeile auf das zweite Feld gestellt und so weiter.
Um einen Algorithmus für unsere Fassung des Problems zu finden, wollen wir uns zunächst Gedanken über ein Struktogramm machen, das uns die einzelnen Lösungsschritte vor Augen führen kann.
Hier genügt uns eine vereinfachte Darstellung der Schritte.

Struktogramm prüfe Zeile

Bevor wir den beschriebenen Algorithmus codieren können, muss die Datenstruktur festgelegt werden.
Es wäre naheliegend, ein Schachbrett in einem zweidimensionalen Feld abbilden zu wollen, so wie wir das mit dem Labyrinth gemacht haben. In diesem Falle wäre das Prüfen möglicher Aufstellungen mit umständlichen Operationen verbunden.
Uns interessiert nicht so sehr die Position der Damen, sondern vielmehr, ob eine Dame auf einer Spalte oder auf einer Diagonale steht, in der wir eine Dame platzieren wollen. Dazu legen wir uns die drei Variablen Spalte, Diagonale1 und Diagonale2 vom Typ Boolean an. Da in jeder Zeile immer nur eine Dame steht, genügt es, im jeweiligen Element Dame[Zeile] die Spaltenposition zu speichern. Durch diese Überlegungen kommen wir zur folgenden Datenstruktur:

const
  Nmax            =  8;
  Nmax2           = 16;
  bedroht         = true;
  nichtbedroht    = false;

type
  tZlSp           = 1..nMax;
  tDiag1          = 1..nMax2;
  tDiag2          = -nMax..nMax;
  tStein          = (leer, marke, mauer);
  OwnBool         = (nein, ja);

var //global
  Dame: array [tZlSp] of tZlSp;
  Spalte: array [tZlSp] of OwnBool;
  Diag1: array [tDiag1] of OwnBool;
  Diag2: array [tDiag2] of OwnBool;

Für die eindeutige Adressierung des Feldelementes einer Diagonale benutzen wir eine aus der Mathematik bekannte Gesetzmäßigkeit:
Für die von links unten nach rechts oben verlaufende Diagonale ergibt sich für die Summe aus Zeilen- und Spaltennummer stets der gleiche Wert. Für die Diagonale von links oben nach rechts unten ergibt die Differenz aus Zeilen- und Spalten- nummer stets den gleichen Wert.
Damit ergibt sich, ganz gleich auf welchem Feld einer Diagonale man sich befindet, immer dasselbe Feldelement in dem Feld von Diagonale1 beziehungsweise Diagonale2.
Die nachstehende Prozedur SetzeDame stellt eine Dame auf das mit Zeile und Spalte adressierte Feld und sperrt die bedrohte Spalte und die beiden Diagonalen. Dabei werden Zeile und Spalte als Parameter übergeben. Die Prozedur EntferneDame macht die durch SetzeDame gespeicherte Bedrohung wieder rückgängig.

procedure TfrmDame.SetzeDame(zl, sp: tZlSp);
begin
  Dame[zl]     := sp;
  Spalte[sp]   := ja;
  Diag1[zl+sp] := ja;
  Diag2[zl-sp] := ja;
end;

procedure TfrmDame.EntferneDame(zl, sp: tZlSp);
begin
  Spalte[sp]   := nein;
  Diag1[zl+sp] := nein;
  Diag2[zl-sp] := nein;
end;

Das weiter oben genannte Struktogramm liefert uns den Algorithmus, den wir nun noch zu codieren haben.
Weitere Erklärungen dazu sind jetzt hier nicht mehr notwendig. Der Code der Unit uDame (im Unterordner Damen der gepackten Beispieldatei) zeigt das Vorgehen.

2 Gedanken zu „Wege aus dem Labyrinth“

Kommentare sind geschlossen.