Python-Code

## nikohaus.py 
## Programm setzt das "Haus-des-Nikolaus"-Problem algorithmisch mit
## einer Adjazenzmatrix um und gibt die Möglichkeiten aus, wieviel mal 
## das Haus von jeder seiner Ecken ausgehend aufgebaut werden kann.


def haus_rek(mtrx, start, kn, count, weg):
        
        ''' Berechnen und Ausgabe der Moeglichkeiten '''
        
        for i in range(5):                                              # eine Matrix-Zeile durchgehen
                if mtrx[kn][i] == 1:                                    # wenn mit anderer Zeile verbunden...
                        weg_neu = "{0} -> {1}".format(weg,i)
                        #print(weg_neu)
                        if count == 7:                                  # Haus komplett errichtet
                                zaehl[start] +=1                        # Moeglichkeiten hochzaehlen
                                if start == 0:
                                        print("{0}: {1}".format(zaehl[start], weg_neu))
                                        continue
                                return
                        mtrx[kn][i] = 0; mtrx[i][kn] = 0                # diese Wege streichen
                        haus_rek(mtrx, start, i, count +1, weg_neu)     # naechster Knoten
                        mtrx[kn][i] = 1; mtrx[i][kn] = 1                # Wege wieder herstellen
        
        zaehl[start +5] +=1                                             # Nicht-Moeglichkeiten hochzaehlen



##--- main() ------------------------------------------------------------

# Adjazenzmatrix des "Haus' vom Nikolaus"
#         4                                                              
#        / \
#       2 - 3
#       | X |
#       0 - 1

mtrx = [[0,1,1,1,0],                      
        [1,0,1,1,0], 
        [1,1,0,1,1], 
        [1,1,1,0,1],
        [0,0,1,1,0]]


zaehl= [0] *10                                                          # speichert die Konstruktionsmöglichkeiten ab


print("Konstruktionsmoeglichkeiten vom Knoten 0 aus:\n")
for i in range(5):                                                      # alle Knoten einmal als Anfangsknoten
        weg = "{0}".format(i)
        haus_rek(mtrx, i, i, 0, weg)                                    # mtrx, start, kn, count, weg


for i in range(5): 
        print("\n-> Von Knoten {0} aus gibt es {1} Moeglichkeiten, {2} Sackgassen.".format(i, zaehl[i], zaehl[i +5]))