nDamen.py

# Backtracking am Beispiel des n-Damen-Problems

# ASCII-Ausgabe einer Stellung
# Bei der Codierung einer Stellung gehen wir davon aus, dass sich in jeder Spalte
# des Schachbrettes höchstens eine Dame befindet. Falls stellung[j] == i, so
# befindet sich die Dame in Spalte j in der i-ten Zeile des Schachbrettes.
def zeichne(stellung):
    n = len(stellung)
    for i in range(n):
        for j in range(n):
            if stellung[j] == i:
                print('D',end='')
            else:
                print('.',end='')
        print()

# Überprüfung der Zulässigkeit einer Stellung
def zulaessig(stellung):
    # Ermittle die Zahl der bisher platzierten Damen in der Teillösung.
    n = len(stellung)
    # Es genügt zu überprüfen, ob die zuletzt platzierte Dame von einer
    # davor platzierten Dame geschlagen werden kann.

    # Da sich die zuletzt platzierte Dame in Spalte n-1 befindet, betrachten
    # wir die Damen von Spalte 0 bis Spalte n-2.
    for j in range(n-1):
        if stellung[j] == stellung[n-1]:
            # Die Dame in Spalte j steht in der selben Zeile wie die Dame in Spalte n-1.
            return False
        if abs(stellung[j]-stellung[n-1]) == n-1-j:
            # Die Damen in Spalte j und Spalte n-1 stehen in einer gemeinsamen Diagonalen.
            return False
    # Wir haben keine Dame gefunden, die die letztplazierte Dame schlagen kann.
    return True

numberofexistingsolutions = 0

# Wir versuchen eine Teillösung (stellung) mittels Backtracking zu vervollständigen.
# Wenn dies gelingt, geben wir den Wert True zurück, ansonsten den Wert False.
def vervollstaendige(stellung):
    # Wenn alle n Damen in zulässiger Weise patziert wurden, haben wir eine
    # Gesamtlösung gefunden.
    if len(stellung) == n:
        return True

    # Wir probieren alle n Platzierungsmöglichkeiten für die nächste Dame in ihrer
    # Spalte aus.
    for y in range(n):
        # Wir erweitern die Teillösung
        stellung.append(y)
        # und überprüfen, ob sie zulässig ist.
        if zulaessig(stellung):
           # Falls dies der Fall ist, versuchen wir diese Teillösung zu vervollständigen.
           if vervollstaendige(stellung):
               # Wenn dies gelingt, haben wir eine Gesamtlösung gefunden.
               global numberofexistingsolutions
               numberofexistingsolutions += 1
               print(numberofexistingsolutions)
               return True
        # Es ist uns nicht gelungen, die gerade betrachtete Dame so zu platzieren, dass
        # diese Teillösung zu einer Gesamtlösung führen würde.
        # Deshalb machen wir den letzten Schritt rückgängig, indem wir diese Dame wieder
        # aus unserer Teillösung entfernen. Dies entspricht dem Backtracking Schritt.
        stellung.pop()

# Wir wollen das 8-Damen-Problem lösen.
n = 8
# Wir starten mit null platzierten Damen
stellung = []
# Wir versuchen diese Ausgangsstellung zu vervollständigen.
vervollstaendige(stellung)
# Wir geben die erste gefundene Lösung aus.
zeichne(stellung)

Teilmengen von M.py

# Als erstes definieren wir
def SubsetsOf (list, k):
    # Wenn die Liste keine items hat, dann gib [[]] zurueck
    if (len(list)==0):
        return [[]]
    # Wenn das nicht ist, dann:
    else:
        # wird als erstes subsets definiert
        subsets = SubsetsOf(list[:-1], k-1)
        # die wird dann iterativ durchgegangen.
        for subset in subsets:
            subset.append(list[-1])
        # Dann wird das zweite Binomial durchgegangen
        subsets += (SubsetsOf(list[:-1], k))
        # und das Ergebnis rueckgegeben
        return subsets