# hamCycle-q3
# Divyanshu Mehta
# hamiltonian cycle problem
# https://www.geeksforgeeks.org/hamiltonian-cycle/
# Exs for Section 46, Q.3


V = 5

def isSafe(v, pos, path):
  # Check if current vertex and last vertex
  # in path are adjacent
  if graph[path[pos-1]][v] == 0:
    return False

  # Check if current vertex not in path already
  for vertex in path:
    if vertex == v:
      return False
  return True


def hasHamCycle(path, pos):
  # base case: all vertices are
  # included in the path
  if pos == V:
    # Last vertex must be adjacent to the
    # first vertex in path to make a cycle
    return graph[path[pos-1]][path[0]] == 1

  # Try different vertices as a next candidate
  # in Hamiltonian Cycle. We don't try 0 as
  # we set 0 to be the starting point
  for v in range(1, V):
    if isSafe(v, pos, path):
      path[pos] = v
      if hasHamCycle(path, pos+1):
        return True
      path[pos] = -1   # backtrack
  return False



# main ----------------------------------

''' 
graph
  (0)--(1)--(2)
  |    / \   |
  |   /   \  |
  |  /     \ |
  (3)-------(4) 
'''
graph = [ [0, 1, 0, 1, 0], 
          [1, 0, 1, 1, 1],
          [0, 1, 0, 0, 1],
          [1, 1, 0, 0, 1],
          [0, 1, 1, 1, 0] ]

''' 
graph
  (0)--(1)--(2)
  |    / \   |
  |   /   \  |
  |  /     \ |
  (3)      (4) 

graph = [ [0, 1, 0, 1, 0], 
          [1, 0, 1, 1, 1],
          [0, 1, 0, 0, 1], 
          [1, 1, 0, 0, 0],
          [0, 1, 1, 0, 0] ]
'''


path = [-1]*V
path[0] = 0   # start at vertex 0

if not hasHamCycle(path, 1):
  print("No solution")
else:
  print("Hamiltonian Cycle:")
  for v in path:
    print(v, end=' ')
  print(path[0], "\n")  # back to start