def hamiltonkreis(graph):
    kreisExistiert = False
    startKnoten = graph[0][0]
    wege = [[startKnoten]]
    wegeErweitert = []
    zaehler = 0
    while wege != [] and not kreisExistiert:
        aktuellerWeg = wege[0]
        wege = wege[1:]
        if len(aktuellerWeg) == len(graph):
            # Test, ob zu Hamiltonkreis erweiterbar
            zaehler = zaehler + 1
            letzterKnoten = aktuellerWeg[len(aktuellerWeg)-1]
            # bestimme die Nachbarn von letzterKnoten
            knotenGefunden = False
            i = 0
            while not knotenGefunden:
                if letzterKnoten == graph[i][0]:
                    knotenGefunden = True
                    listeNachbarknoten = graph[i][1]
                i = i+1
            # teste, ob es eine Kante zum startKnoten gibt
            if startKnoten in listeNachbarknoten:
                kreisExistiert = True
                #print(aktuellerWeg+[startKnoten])
        else:
            letzterKnoten = aktuellerWeg[len(aktuellerWeg)-1]
            # bestimme die Anzahl der Nachbarn von letzterKnoten
            knotenGefunden = False
            i = 0
            while not knotenGefunden:
                if letzterKnoten == graph[i][0]:
                    knotenGefunden = True
                    listeNachbarknoten = graph[i][1]
                i = i+1
            for nachbarKnoten in listeNachbarknoten:
                erweiterterWeg = aktuellerWeg + [nachbarKnoten]
                zaehler = zaehler + 1
                if not nachbarKnoten in aktuellerWeg:
                    erweiterterWeg = aktuellerWeg + [nachbarKnoten]
                    wege = [erweiterterWeg] + wege
    return (kreisExistiert, zaehler)




# Test - einfach

graph1 = [
    ['1', ['2', '3']],
    ['2', ['1', '5', '4', '3']],
    ['3', ['2', '4', '5', '1']],
    ['4', ['2', '3']],
    ['5', ['2', '3']]
]

graph2 = [
    ['1', ['2', '3', '7', '8']],
    ['2', ['1', '3']],
    ['3', ['2', '1', '8', '4']],
    ['4', ['3', '7', '9', '5']],
    ['5', ['9', '4']],
    ['6', ['7', '9']],
    ['7', ['1', '4', '9', '6']],
    ['8', ['1', '3']],
    ['9', ['4', '7', '6', '5']],
]

print(hamiltonkreis(graph1))

# Test - automatisiert

from random import *

def graph(n):
    graph = []
    for i in range(n):
        nachbarn = []
        for j in range(4): 
            nachbarn = nachbarn + [randint(0, n-1)]
        graph = graph + [[i, nachbarn]]
    return graph


for j in range(4, 20):
    zaehlerSumme = 0
    for i in range(100):
        aktuellerGraph = graph(j)
        (kreisExistiert, zaehler) = hamiltonkreis(aktuellerGraph)
        zaehlerSumme = zaehlerSumme + zaehler
    zaehlerDurchschnitt = zaehlerSumme // 100
    print(j, zaehlerDurchschnitt)