# https://www.geeksforgeeks.org/hamiltonian-path-cycle-in-python/ 


class Graph(): 
    def __init__(self, vertices): 
        self.adjacency_matrix = [[0 for column in range(vertices)]
                                    for row in range(vertices)] 
        self.vertices_count = vertices 

    def is_safe_to_add(self, v, pos, path): 
        if self.adjacency_matrix[path[pos-1]][v] == 0: 
            return False

        for vertex in path: 
            if vertex == v: 
                return False

        return True

    def hamiltonian_cycle_util(self, path, pos): 
        if pos == self.vertices_count: 
            if self.adjacency_matrix[path[pos-1]][path[0]] == 1: 
                return True
            else: 
                return False

        for v in range(1, self.vertices_count): 
            if self.is_safe_to_add(v, pos, path): 
                path[pos] = v 

                if self.hamiltonian_cycle_util(path, pos+1): 
                    return True

                path[pos] = -1

        return False

    def find_hamiltonian_cycle(self): 
        path = [-1] * self.vertices_count 

        path[0] = 0

        if not self.hamiltonian_cycle_util(path, 1): 
            print ("No\n")
            return False

        self.print_solution(path) 
        return True

    def print_solution(self, path): 
        #print ("Yes\n")
        for vertex in path: 
        #    print (vertex)
            print(vertex + 1)

#n = int(input('Anzahl der Knoten: '))

# Erzeugen einer n x n - Matrix mit lauter Nullen
#a = [[0] * n for i in range(n)]

# Eingabe der Adjazenzmatrix
#for i in range(n):
#   for j in range(i+1,n):
#      print('a(',i+1,',',j+1,') = ', end = "")
#     print('a(',i,',',j,') = ', end = "")
#      a[i][j] = int(input())
#      a[j][i] = a[i][j]

# Ausgabe der Adjazenzmatrix
#print('Adjazenzmatrix:')
#print(a)
#for i in range(n): print(a[i])


# Example Dodekaeder
g = Graph(20) 
g.adjacency_matrix = [[0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                      [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
                      [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
                      [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
                      [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
                      [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1],
                      [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0]]

for i in range(20): print(g.adjacency_matrix[i])
print()
print('Hamiltonsche Rundreise auf dem Dodekaeder: \n')
g.find_hamiltonian_cycle()

print()
input('press ENTER to leave ')