Damenproblem

Das Damenproblem ist ein einfach zu beschreibendes Problem, das sich elegant durch Backtracking lösen lässt und dabei erlaubt, die beschriebenen Aspekte eines Suchproblems zu verdeutlichen. Es besteht darin, acht Damen so auf einem Schachbrett zu platzieren, dass sie sich weder horizontal noch vertikal noch diagonal schlagen können. Im Folgenden ist eine gültige Platzierung von vier Damen auf einem entsprechend verkleinerten Schachbrett dargestellt.

Um die Platzierung von Damen auf einem Schachbrett in Python darzustellen, können wir ausnutzen, dass diese, damit sie sich nicht horizontal schlagen können, in unterschiedlichen Zeilen (Reihen) platziert werden müssen. Wir stellen sie deshalb als Array aus Zahlen dar und speichern dabei im ersten Eintrag des Arrays, in welcher Spalte (Linie) die erste Dame steht, im zweiten Eintrag die Spalte der zweiten Dame und so weiter. Wir durchlaufen dabei die Zeilen von oben nach unten und zählen die Spalten von Null beginnend. Zum Beispiel entspricht das Array [2,0,3,1] der oben gezeigten Platzierung von vier Damen auf einem 4x4 Schachbrett.

Die Prozedur print_queens gibt eine so dargestellte Platzierung von Damen im Terminal aus.

def print_queens(queens):
    for i in range(0, len(queens)):
        print("  " * queens[i] + "Q")

Die Ausgabe von print_queens([2,0,3,1]) ähnelt der obigen grafischen Darstellung.

    Q
Q
      Q
  Q

Um das Damenproblem mit Hilfe von Backtracking zu lösen, implementieren wir eine Funktion is_complete, die testet, ob eine so dargestellte Platzierung vollständig ist. Da wir acht Damen auf einem richtigen Schachbrett platzieren wollen, testen wir dazu, ob das Array, die Größe acht hat. Unser Algorithmus soll also dem Array schrittweise Einträge hinzufügen, bis dieses acht Einträge enthält.

BOARD_SIZE = 8

def is_complete(queens):
    return len(queens) == BOARD_SIZE

Wir verwenden eine Konstante¹ BOARD_SIZE für die Anzahl der Damen, die auf dem Schachbrett platziert werden sollen. Diese definieren wir global (also außerhalb der Definition von is_complete), um sie auch in anderen Definitionen verwenden zu können.

Um zu testen, ob eine Platzierung gültig ist, müssen wir testen, ob alle Damen vor Angriffen anderer sicher sind. Da wir durch die Darstellung bereits sicher gestellt haben, dass Damen sich nicht horizontal schlagen können, brauchen wir dazu nur noch zu testen, ob sie sich vertikal oder diagonal bedrohen. Dazu durchlaufen wir jede Dame mit Hilfe einer Zählschleife und testen dann in einer weiteren Zählschleife, ob sie vor später platzierten Damen sicher ist.

def is_safe(queens):
    # search all pairs of different queens
    for i in range(0, len(queens)):
        for j in range(i + 1, len(queens)):
            # queens in same column
            if queens[i] == queens[j]:
                return False
            # row distance equals column distance: queens on same diagonal
            if j - i == abs(queens[j] - queens[i]):
                return False
    # found no attack
    return True

Ob sich Damen vertikal bedrohen, erkennen wir daran, ob sich die Spalten zweier verschiedener Damen gleichen. Um zu testen, ob sich Damen diagonal bedrohen, vergleichen wir deren Spaltenabstand mit dem Zeilenabstand. Sind diese gleich, stehen die Damen auf der selben Diagonale und können sich schlagen. Zur Berechnung des Spaltenabstandes verwenden wir den Absolutbetrag. Da wir für jede in der äußeren Schleife durchlaufene Dame nur später platzierte Damen betrachten, ist dies für den Zeilenabstand nicht nötig.

Schließlich implementieren wir noch eine Funktion place_next, die eine Platzierung um eine weitere Dame erweitert. Diese fügt dem Array einen Eintrag zwischen null und sieben hinzu und gibt ein Array aller so erzeugten Arrays zurück.

def place_next(queens):
    extensions = [None] * BOARD_SIZE

    for q in range(0, BOARD_SIZE):
        extensions[q] = queens + [q]

    return extensions

Wir können nun den zuvor umgangssprachlich formulierten Algorithmus als Funktion is_solvable implementieren. Statt im Schleifenrumpf eine return-Anweisung zu verwenden, speichern wir in einer Variablen solvable, ob eine Lösung gefunden wurde. Diese können wir dann in der Bedingung einer bedingten Schleife abfragen, um die Betrachtung überflüssiger Alternativen zu vermeiden.

def is_solvable(queens):
    if is_complete(queens):
        return is_safe(queens)

    exts = place_next(queens)
    for index in range(0, len(exts)):
        if is_solvable(exts[index]):
            return True

    return False

Falls die übergebene Teillösung vollständig ist, wird zurückgegeben, ob diese gültig ist. Falls nicht, werden alle Erweiterungen der übergebenen Teillösung berechnet und in der Variablen qs gespeichert. Die anschließende Schleife durchläuft die Erweiterungen, bis mit Hilfe eines rekursiven Aufrufs eine lösbare Erweiterung gefunden wurde.

Mit den gezeigten Definitionen läuft der Aufruf is_solvable([]) für einige Sekunden und liefert schließlich das Ergebnis True zurück, zeigt also an, dass das Damenproblem für acht Damen lösbar ist. Dabei werden alle Platzierungen von acht Damen auf einem Schachbrett nacheinandner daraufhin getestet, ob sich Damen bedrohen, bis die erste sichere Platzierung gefunden wurde. Da (bis zur ersten Lösung) der komplette Suchraum aller Platzierungen von acht Damen auf einem Schachbrett durchsucht wird, spricht man von einem sogenannten brute force Algorithmus. Der Suchraum wird mit voller Kraft vorraus aber auch blind durchsucht und erst vollständige Platzierungen werden auf Gültigkeit überprüft.

Da wir bereits unvollständige Teillösungen auf Gültigkeit überprüfen können, können wir die Laufzeit des Algorithmus deutlich verbessern. Wenn sich zum Beispiel schon die beiden zuerst platzierten Damen bedrohen, brauchen die restlichen sechs gar nicht mehr platziert zu werden. Dadurch werden große Teile des Suchbaums gar nicht erst durchlaufen.

Wir implementieren diese Idee, indem wir die Abbarbeitung des Rumpfes von is_solvable vorzeitig beenden, wenn die übergebene Teillösung nicht gültig ist. Dazu können wir die folgende optionale Anweisung am Anfang des Funktionsrumpfes notieren.

    if not is_safe(queens):
        return False

Nach dieser Änderung liefert der Aufruf is_solvable([]) das Ergebnis True ohne merkliche Verzögerung. Falls wie hier bereits Teillösungen auf ihre Gültigkeit überprüft werden können, kann auf diese Weise die Laufzeit des Backtracking-Verfahrens oft erheblich verbessert werden.

Dass das Damenproblem lösbar ist, haben wir möglicherweise bereits vorher vermutet. Um die gefundene Platzierung auszugeben, fügen wir in der bedingten Anweisung zu Beginn der Definition von is_solvable einen Aufruf von print_queens hinzu.

    if is_complete(queens):
        print_queens(queens)
        return True

Da is_solvable ungültige Teillösungen vorher verwirft, ist der Test is_safe(queens) für vollständige Teillösungen nun überflüssig und wir ersetzen ihn durch True. Der Aufruf is_solvable([]) gibt nun die folgende Darstellung einer sicheren Platzierung von acht Damen auf einem Schachbrett aus.

Q
        Q
              Q
          Q
    Q
            Q
  Q
      Q