8-Damen-Problem

Lösung des 8-Damen-Problems.

8-Damen-Problem Joachim Christ


Die Aufgabe beim 8-Damen-Problem besteht darin, auf einem herkömmlichen Schachbrett 8 Damen so zu plazieren, dass sie sich nicht schlagen können. Die Damen haben dabei die Gangmöglichkeiten wie eine normale Dame, obwohl es beim Schach natürlich nur eine Dame jeder Farbe gibt.

Bevor wir uns jedoch sozusagen der Königsdisziplin zuwenden − nämlich dem Schachbrett der Größe 8 × 8 − wollen wir mit kleineren Brettern beginnen. Dabei ist die Aufgabe dann, auf einem Brett z. B. der Größe 3 × 3 genau 3 Damen so zu stellen, dass sie sich nicht schlagen können.

Man erkennt schnell, dass es für Bretter der Dimensionen 1, 2 und 3 keine Lösungen gibt. Das erste Brett, für das die Aufgabe lösbar ist, ist das Brett der Dimension 4.

Eine Lösung ist z. B. folgende Stellung:

    ♛ 
♛     
      ♛
  ♛   


Der Algorithmus zur Bestimmung der Lösung des 8-Damen-Problems beruht darauf, z. B. alle Permutationen des Tupels [ 1, 2, 3, 4 ] zu erzeugen und zu überprüfen, ob das dadurch repräsentierte Brett eine gültige Lösung darstellt.

Eine Demo für die Lösung des 8-Damen-Problems.

 ↵

Bitte wählen Sie eine Brettgröße und starten Sie die Lösungsfindung durch Klicken des Icons.

Voriger Beitrag Nächster Beitrag