---

Schreibe ein Python-Skript, welches alle Lösungen berechnet und ausgibt!

Hier ist ein kommentiertes, effizientes Python-Skript, das das Problem mittels Backtracking löst.

Es berechnet alle 92 Lösungen und gibt sie sowohl als Koordinaten-Liste als auch (optional) als visuelles Schachbrett aus.

Das Python-Skript

Download “2512012008_GG_Solution8QueenProblem.py”

def solve_8_queens():
    """
    Hauptfunktion, um das 8-Damen-Problem zu lösen.
    """
    n = 8
    solutions = []
    # Das Brett wird als 1D-Liste repräsentiert:
    # Der Index ist die Zeile, der Wert ist die Spalte.
    # board[2] = 4 bedeutet: In Zeile 2 steht die Dame in Spalte 4.
    board = [-1] * n 

    def is_safe(current_row, current_col):
        """
        Prüft, ob es sicher ist, eine Dame an (current_row, current_col) zu setzen.
        Wir müssen nur vorherige Zeilen (0 bis current_row - 1) prüfen.
        """
        for row in range(current_row):
            col = board[row]
            
            # 1. Gleiche Spalte prüfen
            if col == current_col:
                return False
            
            # 2. Diagonalen prüfen
            # Wenn der Betrag der Differenz der Zeilen gleich dem Betrag
            # der Differenz der Spalten ist, liegen sie auf einer Diagonalen.
            if abs(current_row - row) == abs(current_col - col):
                return False
        
        return True

    def backtrack(row):
        """
        Rekursive Funktion, die versucht, Damen Zeile für Zeile zu platzieren.
        """
        # Basisfall: Wenn wir Zeile 8 erreichen, haben wir alle 8 Damen platziert.
        if row == n:
            solutions.append(list(board)) # Lösung speichern
            return

        # Versuche jede Spalte in der aktuellen Zeile
        for col in range(n):
            if is_safe(row, col):
                board[row] = col    # Dame setzen
                backtrack(row + 1)  # Weiter zur nächsten Zeile
                # Backtracking passiert hier automatisch, indem die Schleife
                # weiterläuft und board[row] im nächsten Durchlauf überschrieben wird.

    # Start der Rekursion bei Zeile 0
    backtrack(0)
    return solutions

def print_board(board):
    """
    Hilfsfunktion, um eine Lösung visuell als Brett auszugeben.
    """
    n = len(board)
    print("   " + " ".join(str(i) for i in range(n))) # Spaltennummern
    print("  " + "-" * (2 * n))
    for row in range(n):
        line = f"{row}|" # Zeilennummer
        queen_col = board[row]
        for col in range(n):
            if col == queen_col:
                line += " Q"
            else:
                line += " ."
        print(line)
    print()

# --- Hauptprogramm ---
if __name__ == "__main__":
    print("Berechne Lösungen für das 8-Damen-Problem...\n")
    
    alle_loesungen = solve_8_queens()
    anzahl = len(alle_loesungen)
    
    print(f"Es wurden insgesamt {anzahl} Lösungen gefunden.")
    print("-" * 30)

    # Abfrage, ob alle ausgegeben werden sollen
    print("Hier ist die erste gefundene Lösung als Beispiel:\n")
    print_board(alle_loesungen[0])
    
    # Hinweis: Um alle 92 zu sehen, können wir über die Liste iterieren.
    # Hier geben wir alle aus (Achtung: lange Ausgabe in der Konsole!)
    print(f"--- Ausgabe aller {anzahl} Lösungen ---")
    for i, sol in enumerate(alle_loesungen):
        print(f"Lösung Nr. {i+1}: {sol}")
        # Wenn du jedes Brett grafisch sehen willst, entkommentiere die nächste Zeile:
        # print_board(sol) 

Erklärung des Codes

1. Das Board (Die Datenstruktur): Anstatt einer 8x8 Matrix verwenden wir eine einfache Liste board = [-1, -1, ...].

   • board[0] = 3 bedeutet: In Zeile 0 steht die Dame in Spalte 3.
   • Dadurch wird die Regel “Keine zwei Damen in derselben Zeile” automatisch erfüllt, da jeder Index der Liste (Zeile) nur einen Wert (Spalte) haben kann.

2. Die is_safe Funktion: Bevor wir eine Dame setzen, prüfen wir:

   • Steht schon eine Dame in dieser Spalte? (col == current_col)
   • Steht schon eine Dame diagonal? Der mathematische Trick hierbei ist: abs(x1 - x2) == abs(y1 - y2).

3. Backtracking: Der Algorithmus platziert eine Dame, geht in die nächste Zeile und versucht es dort erneut. Wenn er in einer Sackgasse landet (kein Platz sicher), geht er einen Schritt zurück (“backtrackt”) und schiebt die vorherige Dame ein Feld weiter.

---