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)