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

ans = 'y'

while ans == 'y':

  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 Hamiltonian circle\n")
            return False

        self.print_solution(path) 
        return True

    def print_solution(self, path): 
        print ("Hamiltonian circle:")
        for vertex in path: 
        #    print (vertex)
            print(vertex + 1)

  n = int(input('Anzahl der Knoten: '))
  print('Die Knoten 1, . . ,',n,'werden intern mit 0, . . ,',n-1,'indiziert.')

# 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 = "")
      a[i][j] = int(input())
      a[j][i] = a[i][j]

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

  g = Graph(n)
  g.adjacency_matrix = a
  g.find_hamiltonian_cycle()
  print()
  print()

  ans = input('Noch eine Adjazenzmatrix? <y> <n> ')
  print()