Backtracking: Königinnenproblem

von | Aug. 29, 2022 | Python | 0 Kommentare

Backtracking: Königinnenproblem

Das Königinnenproblem

Die erste Anwendung der Klasse Backtrack.

Queens.py

# File queens.py

from backtrack import Backtrack

import datetime

 

class Queens(Backtrack):

 

    vector = [ ]

    diag1 =  [ ]  

    diag2 =  [ ]

    solutionNr: int = 0

 

    def __init__(self, test:bool = False, showAttempts:bool = False,

                 beautify:bool = False, size:int = 8):

        self.beautify = beautify

        self.size = size

        super().__init__(test, showAttempts)

   

    def moves(self, level: int):

        return range(self.size)

 

    def valid(self, level: int, move:int) -> bool:

        return not(                               # Was ist besetzt…                        

                     move in self.vector or       # …die Spalte?  

                     level-move in self.diag1 or  # …die Diagonale 1: links-oben nach rechts-unten

                     level+move in self.diag2     # …die Diagonale 2: links-unten nach rechts-oben?  

                  )

 

    def record(self, level: int, move):

        self.vector.append(move)

        self.diag1.append(level-move)

        self.diag2.append(level+move)

       

    def undo(self, level: int, move):

        self.vector.pop()

        self.diag1.pop()

        self.diag2.pop()

 

    def done(self, level: int):

        if level==self.size-1:

            self.solutionNr += 1

            print(f"\nLösung {self.solutionNr:4} {self.vector}")            

            if self.beautify:

                self.show()

            return True

        return False

 

    def show(self):

        # „Schöne“ Ausgabe

        for r in range(self.size):

            for c in range(self.size):                        

                print("Q  " if self.vector[r]==c else ".  ", sep="", end="")

            print()

        now = datetime.datetime.now()

        print(f"Berechnet am {now:%d. %b. %Y} um {now:%H:%M} Uhr.")            

 

if __name__ == "__main__":

    Queens(test=False, showAttempts=True, beautify=True, size=4)            

 

Das Programm im Detail

Mit super.__init__(...) wird die Steuerung an die __init__-Methode der Basisklasse Backtrack übergeben.

Diese Klasse wird als Modul in der Datei queens.py gespeichert. Zum Aufruf kann ein neues Python-Programm mit zwei Zeilen eingesetzt werden:

from queens import Queens

Queens(test=False, showAttempts=True, beautify=True, size=4)

Einfacher ist es aber, die folgenden zwei Zeilen am Ende von queens.py einzufügen:

if __name__ == "__main__":
    Queens(test=False, showAttempts=True, beautify=True, size=4)
  • showAttempts steuert die Anzeige der Anzahl der Versuche und der Dauer.
  • beautify gleich True bewirkt die Ausgabe der Lösung als Quadrat.
  • size hat den Standardwert 8 und wird hier auf 4 gesetzt.

Oder kürzer, aber weniger übersichtlich:

if __name__ == "__main__":
    Queens(False, True, True, 4)

Die letzten zwei Zeilen erlauben es, Queens direkt aus der Python IDLE heraus zu starten:

Wie werden gültige Plätze für Königinnen gefunden?

Zeilen und Spalten

Vorbemerkung

  • Ein Array ist in den meisten Programmiersprachen eine Zusammenfassung von gleichartigen Komponenten, zum Beispiel von ganzen Zahlen. Mehrdimensionale Arrays sind Arrays von Arrays.
  • Eine Liste erweitert dieses Konzept. Listen sind in Python sehr wichtige Sprachelemente. Die Liste ähnelt dem Array, kann aber beliebige Komponenten (und natürlich auch wieder Listen) enthalten

vector ist eine Liste, in der in der Reihenfolge der Zeilen jene Spalten abgespeichert werden, die Königinnen enthalten. Zu Beginn ist die Liste leer.

Bild 1 wird durch den vector mit dem Inhalt [0] beschrieben.

Zum besseren Verständnis hier die vector-Darstellung der einzelnen Bilder. Die Spalten diag1 und diag2 werden später erklärt.

Bildvectordiag1diag2
1[0][0][0]
2[0, 2][0, -1][0, 3]
3[0, 3][0, -2][0, 4]
4[0, 3, 1][0, -2, 1][0, 4, 3]
5[1][-1][1]
6[1, 3][-1, -2][1, 4]
7[1, 3, 0][-1, -2, 2][1, 4, 2]
8[1, 3, 0, 2][-1, -2, 2, 1][1, 4, 2, 5]
9[2, 0, 3, 1][-2, 1, -1, 2][2, 1, 5, 4]
Bild 1

Diagonale 1

In den Diagonalen darf auch nur je eine Königin stehen. Zuerst einmal betrachten wir die Diagonalen von links oben nach rechts unten. Für jeden Platz des Miniatur-Schachbretts wird eine Zahl mit der Differenz Zeilennummer – Spaltennummer berechnet. Im Programm steht für die Zeilennummer level und für die Spaltennummer in dieser Zeile move. Damit wird einerseits auf den Artikel der ACM Bezug genommen und andererseits werden weitere Programmbeispiele vorbereitet. Damit ergeben sich somit für level-move folgende Zahlen:

0-1-2-3
10-1-2
210-1
3210

diag1 ist eine Liste, die für jede Königin die so errechnete Zahl enthält. Für die erste Lösung enthält diag1 daher die Zahlen [-1, -2, 2, 1]. Jede Zahl darf nur einmal vorkommen – die Königinnen kommen einander in den Diagonalen von links oben nach rechts unten nicht in die Quere

Diagonale 2

Nun zu den Diagonalen von links unten nach rechts oben. Die Zahlen pro Feld werden aus der Summe Zeilennummer + Spaltennummer bestimmt:

0123
1234
2345
3456

Daher enthält die Liste diag2 für die erste Lösung die Zahlen [1, 4, 2, 5]. Auch hier kommt keine Zahl zweimal vor – die Bedingung für die Diagonalen von links unten nach rechts oben ist somit auch erfüllt.

Die Methoden

  • moves liefert alle Werte, die die Variable move bei den Versuchen (attempt) annehmen darf.
  • valid: Mit den Vereinbarungen wird valid recht einfach: die neue Position einer Königin in Zeile level und Spalte move ist dann zulässig, wenn weder move in vector enthalten ist noch level-move in diag1 und auch nicht level+move in diag2.
  • record: Die den Platz der Königin beschreibenden Zahlen sind an die Listen vector, diag1 und diag2 anzuhängen. vector wird um die Spaltennummer move erweitert, diag1 um die Differenz von Zeilennummer und Spaltennummer, also level-move und diag2 um die Summe der Zeilen- und Spaltennummern level+move.
  • undo wird benötigt, wenn es keine weiteren Möglichkeiten für move gibt und daher der Schritt rückgängig zu machen ist. Dazu sind jeweils die letzten Einträge aus den Listen vector, diag1 und diag2 mit pop() zu entfernen.
  • done: Eine Lösung ist gefunden, wenn in der letzten Zeile eine Königin einen Platz gefunden hat. Für das Anzeigen der Lösung reicht die Ausgabe des vector. Mit der Methode show wird die Lösung schöner dargestellt.
  • Die übersichtliche Ausgabe von Datum und Uhrzeit ist immer wieder eine Herausforderung. Älteren Python-Version borgen sich Funktionen wie strftime von C aus. Leider sind diese Funktionen nicht sehr benutzerfreundlich. Mit der format-Funktion oder mit Formatstrings geht das viel einfacher, wird aber nur selten in Dokumentationen erwähnt. Daher gibt es hier ein Anwendungsbeispiel. Mehr dazu in https://docs.python.org/3/library/datetime.html#strftime-and-strptime-format-codes

Gar nicht kompliziert!

Ergebnis

Folgende Lösungen werden gezeigt:

Lösung    1 [1, 3, 0, 2]
.  Q  .  . 
.  .  .  Q 
Q  .  .  . 
.  .  Q  . 
Lösung    2 [2, 0, 3, 1]
.  .  Q  . 
Q  .  .  . 
.  .  .  Q 
.  Q  .  . 
60 attempts in     0.24 seconds

Übrigens: die Berechnung und Ausgabe aller 92 Lösungen des 8-Königinnenproblems dauert nach 15.720 Versuchen 28,9 Sekunden und ohne beautify 1,2 Sekunden.

Zurück zu 4 Königinnen: natürlich sind noch weitere Verbesserungen möglich. moves liefert als zulässige Spaltennummern alle Zahlen von 0 bis zur Anzahl der Königinnen – 1. Aber Spaltennummern, die schon im vector enthalten sind und somit schon vergeben sind, brauchen nicht mehr untersucht zu werden. Das wird mit

    def moves(self, level: int):
        return list(set(range(self.size))-set(self.vector))

erreicht:

  • Zuerst wird mit range eine Liste [0, 1, 2, 3] erzeugt.
  • Diese Liste wird in eine Menge (set) umgewandelt.
  • Ebenso wird aus der Liste der bisher gefundenen Lösungen (vector) in eine Menge gebildet. 
  • Die Differenz dieser beiden Mengen gibt an, welche Spalten noch frei sind.
  • Die Differenzmenge wird für die weitere Verarbeitung wieder in eine Liste verwandelt.

Diese Version ist in der Datei queens_2.py gespeichert.

Nun sind nur mehr 32 Versuche notwendig. Da die meiste Zeit zur Ausgabe der vector-Werte gebraucht wird, sinkt die Gesamtzeit nicht wesentlich. Wenn wir in done die print-Zeile auskommentieren, wird die echte Rechenzeit mit weniger als 0,01 Sekunden angezeigt.

Noch ein paar Zahlen: bei 12 Königinnen werden nach 2.915.740 Versuchen die 14.200 Ergebnisse in 7,0 Sekunden errechnet oder zusammen mit den vector-Werten in 175.9 Sekunden angezeigt.

Es gibt viele weitere Varianten, die auf dem Königinnenproblem aufbauen.

  • Statt der Königinnen könnten Springer eingesetzt werden.
  • Oder Superköniginnen, die die Eigenschaften der Königin und des Springers vereinigen. Der Name dafür „Maharadscha“. Warum eigentlich nicht „Maharani“? Ich bin kein Gender-Fan, aber in dem Fall täte ein wenig Allgemeinbildung gut.

Wir brauchen nur die Methode valid zu verändern und schon können alle Varianten auch berechnet werden.

Kommentar absenden