Das Acht-Damen-Problem (C)

Die Benchmark-Tests für KI-Sprachen in der Juni-Ausgabe dieser Zeitschrift gaben mir den Anlaß, mich intensiver mit dem Acht-Damen Problem zu beschäftigen.

Ich möchte hiermit einen Vergleich der konventionellen optimierten Programmierung mit den Kl-Sprachen ermöglichen. Dieser Vergleich soll keinesfalls den Mutzen dieser Sprachen bestreiten, es soll vielmehr gezeigt werden, wie groß die Leistung herkömmlicher Programmiersprachen für klar umrissene Probleme ist.

Das hier vorgestellte Programm ist etwa um den Faktor 1000 (in Worten eintausend) schneller als die im Juni vorgestellten Lösungen.

Desweiteren soll an einem einfachen Beispiel gezeigt werden, wie die Umsetzung eines Problems in ein das Problem lösendes Programm erfolgt. Es wird das Prinzip der Rekursion erläutert und ein kurzer Einblick in Bitoperationen bei der Programmiersprache 'C' gegeben.

Problemdefinition

Das Acht Damen Problem beschäftigt sich, wie der Name schon sagt, mit acht Damen (Schachfiguren). Diese sollen so auf einem Schachbrett positioniert werden, daß sie sich gegenseitig nicht schlagen können. Die Bewegungsmöglichkeiten sind die einer Dame im Schachspiel (senkrecht, waagerecht und diagonal).

Lösungsansatz

Unser Programm könnte jetzt natürlich einfach alle acht Damen über das gesamte Schachbrett laufen lassen und abprüfen, ob die Damen erstens nicht auf identischen Positionen stehen und zweitens, daß sie sich gegenseitig nicht schlagen können.

Dieses Programm besteht aus acht ineinander geschachtelten Schleifen, die je einer Dame zugeordnet sind und diese über alle 64 Felder laufen lassen. Der damit verbundene Zeitaufwand liegt bei unserem Rechner bei etwa 7000 Jahren (optimistisch); ein wohl offensichtlich indiskutabler Zeitraum. Es obliegt also das Problem der Optimierung.

Optimierung

Wenn man sich an ein Schachbrett setzt und versucht, die Damen darauf zu verteilen, stellt man schnell fest, daß es sinnlos ist, mehr als eine Dame in einer Reihe aufzustellen.

Diese Erkenntnis nutzen wir, indem wir unser Schachbrett nicht etwa als Matrix mit acht mal acht Plätzen vereinbaren, sondern für jede Reihe nur ein Feldelement benutzen; der Wert, der in dem Feldelement steht, gibt uns hierbei die Position der Dame in der Reihe an (s. Abb. 1).

Abb.1: Die Damen bewegen sich jeweils nur in einer Reihe; für jede Reihe wird ein reserviert, unser Feld (acht Elemente) kann so das gesamte Spielfeld repräsentieren.

Die Werte in der Abbildung geben die Spalte an, in der sich die Dame befindet. Die Speicherrepräsentation geht aus Abb. 4 hervor.

Unsere Schleifen müssen nun nicht mehr über das gesamte Spielfeld laufen, sondern nur noch über die der Dame zugehörige Reihe (also nicht von eins bis 64, sondern von eins bis acht). Der Zeitaufwand verkürzt sich damit auf ca. 1600 Sekunden (wie oben wird von 10.000 Stellungsüberprüfungen pro Sekunde ausgegangen).

Eine weitere Möglichkeit der Optimierung ergibt sich, wenn man sich das Setzen der Damen in verschiedene Reihen auf dem Schachbrett vorstellt. Was für die Reihen gilt, gilt in gleicher Weise auch für die Spalten; es darf nur jeweils eine Dame gesetzt werden (die Überprüfung der Diagonalen folgt später).

Richten wir uns also eine Maske ein, die die bereits besetzten Spalten repräsentiert. Da ich als Implementationssprache ’C’ gewählt habe ist das auf eine sehr einfache Weise möglich: Man nimmt ein und setzt das der Spalte entsprechende Bit (s. Abb. 2).

Abb.2: Unsere Maske repräsentiert die durch Damen besetzten Spalten (siehe auch Abb. 4).

Unser Programm prüft nun ganz einfach, ob in der Spalte, in die wir unsere Dame setzen wollen, das entsprechende Bit gesetzt ist. Ist dies der Fall, so brauchen wir uns um die tieferen Reihen nicht mehr zu kümmern (es gibt ab dieser Reihe sowieso immer zwei Damen, die sich schlagen können).

Jetzt sind wir am einem Punkt angekommen, an dem es sinnvoll ist, die Möglichkeiten der rekursiven Programmierung (s. Abb. 3) zu nutzen.

Wir lassen unsere geschachtelten Schleifen das sein, was sie sind (schön und anschaulich), und begeben uns auf das Glatteis der Rekursion. Hierzu brauchen wir eine Funktion, deren Aufgabe es ist, eine Dame durch eine Reihe zu schieben (s. Abb. 4) und abzuprüfen, ob diese Dame von einer vorher plazierten geschlagen werden kann. Ist dies der Fall, so kann keine Kombination der Damen in den tieferliegenden Reihen eine Lösung ergeben. Kann die neu plazierte Dame jedoch nicht geschlagen werden, ruft sich die Funktion rekursiv (bzw. selbst) auf und erzeugt damit Damenstellungen in den tieferen Reihen. Der Ebenenparameter (vgl. Abb. 3) bei diesem Aufruf ist natürlich die tiefere Reihe. In ihr wird der beschriebene Vorgang wiederholt.

Abb. 3:
Rekursion bedeutet, daß eine Funktion sich selbst, evtl, über Zwischenaufrufe, aufruft. Das Prinzip ähnelt dem von geschachtelten Schleifen, hat jedoch den wesentlichen Vorteil, daß die Zahl der Schachtelungen nicht vorher festgelegt werden muß.

Die Anzahl der Schachtelungen wird durch die Rekursionstiefe bestimmt; außerdem werden in jeder Rekursionsebene die gleichen Operationen ausgeführt (nicht, wie bei geschachtelten Schleifen, nur in der innersten).

Damit die Funktion sich nicht unendlich oft selbst aufruft, muß sie überprüfen, wie oft sie bereits geschachtelt wurde; dies wird durch die Übergabe eines Parameters erreicht, der die aktuelle Rekursionstiefe (in gewünschter Form) enthält. Bei jedem Selbstaufruf der Funktion sollte dieser Parameter verändert werden, damit sich die tiefer geschachtelte Funktion über ihre Schachtelungsebene im klaren ist.

Die Rekursion wird abgebrochen. wenn sie ihre maximale Tiefe erreicht hat. Ein Abbruch bedeutet, daß die weitere Schachtelung beendet wird, als nächstes also die vorher aktive (aufrufende, höhere) Funktion aktiviert wird. Wird die oberste Rekursionsebene verlassen, so ist die Rekursion beendet. Mit jedem Funktionsaufruf innerhalb der Rekursion ist ein Ebenenwechsel verbunden. Rekursion ist das grundlegende Prinzip der KI-Sprachen.

Abb. 4:
Die Werte, die für eine Dame gespeichert werden, geben nicht etwa die Nummer der Spalte an, in der die Dame steht, sondern werden analog zu der in der Maske benutzten Repräsentation durch Bits benutzt.

Im hierzu genutzten Datentyp (vgl. Maske) , wird das B it gesetzt, das die Position in der Reihe kennzeichnet.

Dies läßt sich am einfachsten erreichen, indem man ein Bit des setzt und dieses durch ’shiften’ über die einzelnen Positionen schiebt. Durch eine ODER-Verknüpfung von Maske und Damenposition läßt sich so leicht prüfen, ob die Dame in eine bereits besetzte Spalte gesetzt werden soll.

Natürlich muß, wie jede Rekursion, unsere Funktion auch ein Abbruchkriterium haben, Dieses ist erfüllt, wenn wir eine Dame in der letzten (achten) Reihe plaziert haben. In diesem Fall wurde eine Lösung gefunden. Statt eine weitere Rekursionsebene zu erzeugen, zählen wir den Zähler für die Lösungen um eins hoch und fahren mit dem Verschieben der Dame fort.

Wenn eine Dame in der letzten Spalte angekommen ist, haben wir alle Positionierungsmöglichkeiten geprüft. Jetzt kann der Funktionsaufruf beendet und die Rekursion auf der tieferen Ebene fortgesetzt werden (d.h. wir schieben die Dame in einer höheren Reihe weiter).

Hat die Funktion der ersten Rekursionsebene (erste Reihe) die Dame auf das letzte Feld gesetzt und die zugehörigen Möglichkeiten überprüft, so wird auch sie terminieren. Die Rekursion ist dann vollständig abgearbeitet, und unser Zähler enthält die Anzahl der Möglichkeiten. Das Hauptprogramm wird wieder aktiviert und kann diese Zahl ausgeben.

Mit der Rekursion haben wir den wichtigen Effekt, daß für jede Ebene (Reihe) eine neue Maske angelegt wird; wir müssen also beim Aufstieg auf eine höhere Reihe nicht den alten Zustand wiederherstellen.

Wir haben durch die Rekursionsebenen sichergestellt, daß in jeder Reihe nur eine Dame stehen kann; die Maske garantiert uns, daß in jede Spalte nur eine Dame gesetzt wird; das letzte noch bleibende Problem ist das Überprüfen der Diagonalen.

Hierzu müssen wir prüfen, ob die zuletzt gesetzte Dame in einer Diagonalen mit den vorher gesetzten steht. Dazu kopieren wir uns einfach das Feldelement mit der Damenposition (wie aus Abb. 4 hervorgeht, kann man es als Maske für eine Reihe interpretieren) in zwei neue Masken, die mit rechts bzw. links bezeichnet werden. Diese beiden Masken werden pro Reihe, die wir nach oben laufen, jeweils um ein Bit nach links bzw. rechts verschoben und decken damit die Diagonalen zu der Dame ab (vgl. Abb. 5).

Abb. 5
Das Erzeugen der Diagonalen erfolgt, indem die Damenposition pro Reihe um eins nach links bzw. nach rechts geshiftet wird.

Wenn wir in einer der Diagonalen eine bereits gesetzte Dame finden, so können sich diese schlagen; es wird ein Fehlercode zurückgegeben. Sollten wir alle höheren Reihen überprüft haben, ohne auf eine Dame zu treffen, kann die neue Dame nicht geschlagen werden, es wird kein Fehlercode zurückgeliefert und der Rekursionsfunktion damit mitgeteilt, daß es sich lohnen kann, die tieferen Reihen (Rekursionsebenen) mit Damen zu besetzen.

Das so optimierte Programm hat eine Laufzeit von ca. 0.6 Sekunden, es fehlt uns allerdings noch der Vergleich zu den Benchmark-Tests der KI-Sprachen. Diese wurden für ein sechs-malsechs-Schachbrett mit sechs Damen gemacht; das abgedruckte Programm (Listing 1) berechnet die Lösungszahl für Schachbretter der Kantenlänge eins bis fünfzehn. Für ein sechs-mal-sechs-Brett habe ich bei meinen Tests Laufzeiten von etwa 0.04 Sekunden gemessen, selbstverständlich ohne Ausgabe der Lösungen (es kommt ja auf Zeit an). Damit ist wohl ein deutlicher Unterschied zu den Kl-Sprachen zu sehen, ihre Werte lagen zwischen 13 und 130 Sekunden.

Das hergeleitete Programm nutzt dieselben Methoden wie die KI-Sprachen (Rekursion); der Geschwindigkeitsunterschied entsteht aus der optimalen Abstimmung der Operationen und Datenstrukturen auf das Problem. Hierzu sind die KI-Sprachen nicht in der Lage, was aber nicht heißen soll, daß Probleme grundsätzlich besser auf herkömmliche Weise gelöst werden können.

Spielereien

Nachdem das Programm seinen Zweck nun erfüllt hat, können wir uns damit auseinandersetzen, dem Benutzer ein paar Bonbons für seine Aufmerksamkeit zu schenken. Als da wären: die Ausgabe der Lösungen oder sogar das bildliche Darstellen des "Damenwanderns”.

Beide Probleme sind sehr einfach lösbar, sofern der Leser rudimentäre Kenntnisse in ’C’ besitzt und bereit ist, den beschriebenen Lösungsweg am Programm nachzuvollziehen. Hierbei ist zu beachten, daß das abgedruckte Listing eine erweiterte Version für verschiedene Feldgrößen ist.

Die Ausgabe einer Möglichkeit kann erfolgen, sobald wir eine Lösung gefunden haben; es wird, statt die Lösungsanzahl hochzuzählen, eine Ausgaberoutine aufgerufen (s. Listing 2). Diese holt das Zählen der Möglichkeiten nach und gibt danach die Lösung auf dem Bildschirm aus; hierbei wird auf einen Tastendruck gewartet, um ein Betrachten des Bildschirms zu ermöglichen.

Die zweite Variante erfordert, daß jede Rekursionsebene ihre Reihe mit der entsprechend plazierten Dame selbst ausgibt. Die Ausgabe müßte also in der Schleife erfolgen, die die Dame über die Reihe schiebt. Wird die Rekursionsebene abgebrochen, so sollten die Felder der entsprechenden Reihe geleert werden, es gibt dann ja in dieser Reihe keine Dame mehr.

Listing 1:

/********************************************/
/*                                          */
/*   Timerfunktionen fuer Benchmark-Tests   */
/*                                          */
/********************************************/

#include <osbind.h>
#include <stdio.h>

typedef struct { 
    long takte; 
    long starttim;
} timer;

#define Systime         *((long X) (0x466))
#define tim_reset(tim)  (tim)->takte = (tim)->starttim = 0L 
#define tim_read(tim)   ((tim)->takte)

static char *supstack;

tim_start(tim) timer *tim; {

    supstack = (char *)Super(0L);
    tim->starttim = Systime;
    Super(supstack); 
    return(tim->starttim);
} /* timer Start */

tim_stop(tim) timer *tim: { 
    long stime;

    supstack = (char *)5uper(0L); 
    stime = Systime;
    tim->takte += stime - tim->starttim; 
    Super(supstack); 
    return(tim->takte);
} /* timer stop */

/********************************************/
/* (c) Paris  n-Damen  Problem   1.7.87     */
/*                                          */
/*              Minimal-Version             */
/*                                          */
/* Dokumentation in ST 1/88; Da Felder in   */
/* C grundsaetzlich bei Null beginnen er-   */
/* haelt die erste Reihe den Index Null,    */
/* jede tiefere ist als auch um eins        */
/* kleiner.                                 */
/********************************************/

#define MAX_FELD_GROESSE 15 /* zum Shiften muss das high-bit Null sein */

int Feldgroesse; 
int Spaltenmaske; 
long Anzahl;

Setze_Dame(Feld,Reihe,Maske) int *Feld; 
    register int Reihe; int Maske; { 
        int Spalte = 1,
            1oka1fe1d[MAX_FELD_GROESSE]; 
        register int k, links, rechts, *feldP, *lokalP;

        for (Spalte=1;Spalte<=Spaltenmaske; Spalte<<=1){
            if (Maske & Spalte) continue; 
            feldP = Feld + Reihe; 
            if (*feldP & Spalte) continue; 
            if (Reihe >= Feldgroesse-1) Anzahl++: 
            else {
                lokalP = lokalfeld + Reihe; 
                links = rechts = Spalte; 
                for (k=Reihe;k<Feldgroesse;k++) { 
                    links >>= 1; 
                    rechts <<= 1;
                    *(**lokalP) = (*(++feldP)
                        | links
                        | rechts) & Spaltenmaske;
                }
                if (lokalfeld[Reihe+1] != Spaltenmaske)
                    Setze_Dame(lokalfeld,Reihe+1, (Maske|Spalte));
            }
        }
} /* Setze eine Dame in die ReiheCReihe] */

main() {
    int i, Feld[MAX_FELD_GROESSE]; 
    timer tim;

    Spaltenmaske = 0; 
    for (Feldgroesse=1; Feldgroesse<=MAX_FELD_DROESSE; Feldgroesse++) {
        for (i=0; i<Feldgroesse; i++) Feld[i] = 0;
        Anzahl = 0L;
        Spaltenmaske = (Spaltenmaske << 1) + 1; 
        tim_reset(&tim); 
        tim_start(&tim);
        Setze_Dame(Feld,0,0);
        tim_stop(&tim); 
        printf("Feldgr =%3d: %61d Loesungen, VBL-Takte: %-81d(%-71d sec)\n",    Feldgroesse.Anzahl,tim_read(&tim) tim_read(&tim)/71L); 
        fflush(stdin); getchar();
    }
    fflush(stdin): getchar();
} /* Hauptprogramm */

Listing 2:

/*******************************************/
/* (c) Paris  acht-Dame Problem  1.7.87    */
/*                                         */
/*             Minimal-Version             */
/*                                         */
/* Dokumentation in 5T 1/88; Da Felder in  */ 
/* C grundsaetzlich bei Null beginnen er-  */ 
/* haelt die erste Reihe den Index Null,   */
/* jede tiefere ist als auch um eins       */
/* kleiner.                                */
/*******************************************/

#include <stdio.h>

int Feld [8]; 
long Anzahl;

Setze_Dame(Reihe,Maske) register int Reihe, Maske: {
    
    register int Spalte = 1;

    for (Spalte=1;Spalte<=0xFF;Spalte<<=1) {
        /* fuer alle Spalten der Reihe */ 
        if (Maske & Spalte) continue;
        /* weiter, wenn Spalte besetzt */ 
        Feld[Reihe] = Spalte; /* sonst 'merken'*/ 
        if (diagonal(Reihe)) continue; /* wenn schlagbar naechste Sp. */ 
        if (Reihe >= 7) Anzahl++; /* wenn achte Reihe => Loesung */ 
        else 5etze_Dame(Reihe+1,(Maske | Spalte))
            ; /* sonst naechste Reihe setzen */
    }
} /* Setze eine Dame in die Reihe[Reihe] */ 

diagonal(Reihe) register int Reihe; {

    register int i, *Testreihe, links, rechts;

    Testreihe = Feld + Reihe;
    links = rechts = *Testreihe--;
    for (i=1;i<=Reihe;i++,Testreihe--) {
        /* rueckwaerts ueber alle Reihen */ 
        links <<= 1; /* Diagonalenmaske fuer linke */ 
        rechts >>= 1; /* und rechte Diagonale bilden. */ 
        if ((*Testreihe & links) || /* wenn Dame in der Diag. steht */
            (*Testreihe & rechts)) /* koennen sich beide schlagen! */ 
                return(1); /* Rueckgabe des Fehlers. */
    }
    return(0); /* keine Dame in den Diagonalen */
        /* OK => weitere Reihen besetzen */
} /* Teste die linke und rechte Diagonale */

main() {

    Setze_Dame(0,0); /* Rekursion aktivieren */ 
    printf("Es gibt %1d Loesungen\n",Anzahl);
        /* Ausgabe der Loesung */ 
    fflush(stdin); getchar(); /* auf Bestaetigung warten */
} /* Hauptprogramm */

Thomas Pfoch
Aus: ST-Computer 01 / 1988, Seite 46

Links

Copyright-Bestimmungen: siehe Über diese Seite