Python-Code

m=[(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(4,5)]
s=[[[1],[2],[3],[4],[5]]]
d=0
for i in range(len(m)):
    m.append((m[i][1],m[i][0]))
    
def wegcheck(x,y):
    u=0
    for i in range(len(m)):
        if (m[i][0],m[i][1])==(x[-1],y):
            u=u+1
    return(u)

def ungenutzt(x,y):
    a=1
    for p in range(len(x)-1):
        if (x[p],x[p+1])==(x[-1],y) or (x[p+1],x[p])==(x[-1],y):
            a=a+1
    return(a)

def möglich(x):
    u=[]
    for i in range(5):
        if wegcheck(x,i+1)!=0 and ungenutzt(x,i+1)==1:
            u.append(i+1)
    return(u)

while d<12:
    s.append([])
    for u in range(len(s[-2])):
        for k in range(len(möglich(s[-2][u]))):
            s[-1].append([])
            for ö in range(len(s[-2][u])):
                s[-1][-1].append(s[-2][u][ö])
            s[-1][-1].append(möglich(s[-2][u])[k])
            
    d=d+1

for ä in range(len(s[8])):
    print(s[8][ä])

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]))