Das 8-Damen-Problem

Beschreibung

Kann man 8 Spielfiguren, die jeweils wie eine Dame im Schach schlagen dürfen, so auf einem Schachbrett positionieren, daß keine die andere schlagen kann?

Für die Damen gelten für das Schlagen die üblichen Schachregeln:

Die Dame kann auf den Diagonalen schlagen
Die Dame kann auf der Horizontalen und Vertikalen schlagen
Die Dame kann über jede Entfernung schlagen

Dieses klassische Problem hat für das übliche Schachbrett mit 8×8 Feldern genau 92 Lösungen. Die hier vorgestellte JavaScript-Lösung des Problems kann Schachbretter beliebiger Größe bearbeiten.

Ursprünglich habe ich dieses Problem kennengelernt, als ich in einem Archiv durch verschiedene Jahrgänge der Zeitschrift 'bild der wissenschaft' blätterte und im Jahrgang 1978 ein Programm für den Taschenrechner SR-52 von Texas Instruments vorgestellt wurde, um dieses Problem zu lösen.

Der Artikel hat damals ein starkes Echo ausgelöst, zahlreiche Verbesserungsvorschläge gingen bei der Redaktion ein, so dass das Problem alleine durch Optimierungen im Algorithmus von 72 Stunden Laufzeit auf 13 Stunden reduziert werden konnte.

Wenn dieses Problem als Übungsaufgabe für Programmierer eingesetzt wird, dann ist es sinnvoll, einen rekursiven Ansatz zu verlangen. Der hier zu Grunde liegende Algorithmus ist allerdings iterativ und entspricht den optimierten Algorithmen für die damaligen Stars unter den programmierbaren Taschenrechnern, nämlich dem SR-52 und dem HP-67/97, die Rekursion nicht beherrschten. Auch heute noch dürften diese Algorithmen prinzipbedingt rekursiven Algorithmen überlegen sein, außerdem ist bei größeren n weder ein Stapelüberlauf noch eine Rechenzeitexplosion zu erwarten. Die Laufzeit des hier vorgestellten Alorithmus wächst ungefähr mit O(n³).

Ein paar Gedanken zu möglichen Anwendungen dieser Aufgabe finden sich unter www.buchegger.de/eightqueens.html und in der Wikipedia gibt es weiterführende Links und Infos.

Syntax

Start(BrettGroesse)

BrettGroesse Seitenlänge eines quadratischen Brettes

Anmerkungen

Die Funktion hat keinen Rückgabewert. Das Ergebnis wird in einem neuen Fenster angezeigt.
Zum Abschluß der Berechnung erscheint ein Meldungsfeld mit der Anzahl der ermittelten Lösungen.
BrettGroesse kann beliebig gewählt werden, die Rechenzeit nimmt jedoch mit Brettgröße zu.
Für Bretter mit weniger als 4 × 4 Feldern gibt es keine Lösungen.
Man kann sich überlegen, daß hier auch Symmetrien eine Rolle spielen, weil das Schachbrett ein Koordinatensystem hat: Hat man eine Lösung gefunden, so kann man das Brett unter den Damen um 90° drehen und erhält eine neue Lösung.
Einige Lösungen sind punktsymmetrisch, hier erhält man trotz 4-fachem Drehen des Schachbrettes nur zwei unterschiedliche Lösungen.

Funktions-Demo

Das folgende Formular demonstriert die Wirkung der Funktion.

Code

     <script><!--

      

          // Hintergrundfarbe und Inhalt der einzelnen Felder des Schachbretts

          let TabellenZelle = new Array(4);

              /* Inhalt des Arrays 'TabellenZelle' deklarieren */

              TabellenZelle[0] = "<TD
      BGCOLOR=white>&nbsp;</TD>";

              TabellenZelle[1] = "<TD
      BGCOLOR=gray>&nbsp;</TD>";

              TabellenZelle[2] = "<TD
      BGCOLOR=white><FONT COLOR=gray><B>D</B></FONT> </TD>";

              TabellenZelle[3] = "<TD BGCOLOR=gray><FONT
      COLOR=white><B>D</B></FONT> </TD>";

      

      

          /* Prueft, ob die zuletzt positionierte Dame von den anderen geschlagen
      werden kann */

          function DameKannSchlagen()

          {   // Erstellt von Ralf Pfeifer (www.arstechnica.de)

              for(let Spalte = LS - 1; Spalte >= 0; Spalte--)

              {   // Zwei Damen in der gleichen Zeile ?

                  if (SchachBrett[Spalte] ==
      SchachBrett[LS]) { return true; }

                  // Zwei Damen auf der
      gleichen Diagonalen ?

                  if
      (Math.abs(SchachBrett[Spalte] - SchachBrett[LS]) == LS - Spalte) { return true; }

              }

              return false;

          }

      

      

          /* Ermittelt die naechste Spielstellung */

          function NeueStellung()

          {   // Erstellt von Ralf Pfeifer (www.arstechnica.de)

              // Dame ein Feld nach oben verschieben.

              // Falls Brettrand erreicht, letzte Dame
      verschieben

              while (((++SchachBrett[LS]) >= BrettGroesse)
      && (LS > 0)) { LS--; }

      

              // Alle Stellungen durchprobiert ?

              Weiter = ((SchachBrett[0] != BrettGroesse) || (LS
      != 0));

          }

      

      

          function AusgabeInHTML()

          {   // Erstellt von Ralf Pfeifer (www.arstechnica.de)

              let Spalte, Tabelle;

              Tabelle  =
      "<P><P><HR><TABLE BORDER=1 CELLPADDING=3 CELLSPACING=0>";

              Tabelle += "<CAPTION>Stellung Nr. " +
      AnzLoesungen + "</CAPTION>";

      

              for (let Zeile = 0; Zeile < BrettGroesse;
      Zeile++)

              {

                 Tabelle += "<TR>";

                 for (Spalte = 0; Spalte <
      BrettGroesse; Spalte++)

                 {

                    
      FeldMuster  = (SchachBrett[Zeile] == Spalte) ? 2 : 0;

                    
      FeldMuster += (Zeile + Spalte) % 2;

                    
      Tabelle    += TabellenZelle[FeldMuster];

                 }

                 Tabelle += "</TR>";

              }

              Seite.writeln(Tabelle +
      "</TABLE><P><P>");

          }

      

          function Start(EingabeFeld)

          {   // Erstellt von Ralf Pfeifer (www.arstechnica.de)

      

              /* Variable vorbelegen */

              BrettGroesse = EingabeFeld.value;

              SchachBrett = new Array(BrettGroesse);

      

              LS =
      1;                       
      // Letzte Spalte

              Weiter = true;

              AnzLoesungen =
      0;        // Anzahl gefundener Loesungen

              NeuesFenster =
      open("","","scrollbars,resizable,menubar")

              Seite = NeuesFenster.document;

      

              // Brett aufraeumen

              for(let i = 0; i < BrettGroesse; )  {
      SchachBrett[i++] = 0; }

      

              // Neues Browser-Fenster fuer die Ausgabe oeffnen

      

              // Positionen ausprobieren

              while (Weiter)

              {

                  while (DameKannSchlagen())
      { NeueStellung(); }

      

                  if (LS == (BrettGroesse -
      1))

                     
      {   // Eine Loesung gefunden

                         
      AnzLoesungen++;

                         
      AusgabeInHTML();

                         
      NeueStellung();

                      }

                  else { SchachBrett[++LS] =
      0; }

              }

      

              // Anzahl der gefundenen Stellungen ausgeben

              alert(AnzLoesungen + " Stellungen augegeben");

      

              // Eingabe auf der HTML-Seite beenden

              NeuesFenster.focus();

              Seite.close();

          } // -->

        </script>