a hamiltonian cycle hamiltonian circuit is a graph cycle through a graph that visits each node exactly once determining whether such paths and cycles exist in graphs is the hamiltonian path problem which is npcomplete wikipedia https en wikipedia orgwikihamiltonianpath checks whether it is possible to add next into path by validating 2 statements 1 there should be path between current and next vertex 2 next vertex should not be in path if both validations succeed we return true saying that it is possible to connect this vertices otherwise we return false case 1 use exact graph as in main function with initialized values 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 path 0 1 1 1 1 0 currind 1 nextver 1 validconnectiongraph nextver currind path true case 2 same graph but trying to connect to node that is already in path path 0 1 2 4 1 0 currind 4 nextver 1 validconnectiongraph nextver currind path false 1 validate that path exists between current and next vertices 2 validate that next vertex is not already in path pseudocode base case 1 check if we visited all of vertices 1 1 if last visited vertex has path to starting vertex return true either return false recursive step 2 iterate over each vertex check if next vertex is valid for transiting from current vertex 2 1 remember next vertex as next transition 2 2 do recursive call and check if going to this vertex solves problem 2 3 if next vertex leads to solution return true 2 4 else backtrack delete remembered vertex case 1 use exact graph as in main function with initialized values 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 path 0 1 1 1 1 0 currind 1 utilhamiltoncyclegraph path currind true path 0 1 2 4 3 0 case 2 use exact graph as in previous case but in the properties taken from middle of calculation 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 path 0 1 2 1 1 0 currind 3 utilhamiltoncyclegraph path currind true path 0 1 2 4 3 0 base case return whether path exists between current and starting vertices recursive step insert current vertex into path as next transition validate created path backtrack initialize path with 1 indicating that we have not visited them yet path 1 lengraph 1 initialize start and end of path with starting index path0 path1 startindex evaluate and if we find answer return path either return empty array return path if utilhamiltoncyclegraph path 1 else checks whether it is possible to add next into path by validating 2 statements 1 there should be path between current and next vertex 2 next vertex should not be in path if both validations succeed we return true saying that it is possible to connect this vertices otherwise we return false case 1 use exact graph as in main function with initialized values 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 path 0 1 1 1 1 0 curr_ind 1 next_ver 1 valid_connection graph next_ver curr_ind path true case 2 same graph but trying to connect to node that is already in path path 0 1 2 4 1 0 curr_ind 4 next_ver 1 valid_connection graph next_ver curr_ind path false 1 validate that path exists between current and next vertices 2 validate that next vertex is not already in path pseudo code base case 1 check if we visited all of vertices 1 1 if last visited vertex has path to starting vertex return true either return false recursive step 2 iterate over each vertex check if next vertex is valid for transiting from current vertex 2 1 remember next vertex as next transition 2 2 do recursive call and check if going to this vertex solves problem 2 3 if next vertex leads to solution return true 2 4 else backtrack delete remembered vertex case 1 use exact graph as in main function with initialized values 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 path 0 1 1 1 1 0 curr_ind 1 util_hamilton_cycle graph path curr_ind true path 0 1 2 4 3 0 case 2 use exact graph as in previous case but in the properties taken from middle of calculation 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 path 0 1 2 1 1 0 curr_ind 3 util_hamilton_cycle graph path curr_ind true path 0 1 2 4 3 0 base case return whether path exists between current and starting vertices recursive step insert current vertex into path as next transition validate created path backtrack wrapper function to call subroutine called util_hamilton_cycle which will either return array of vertices indicating hamiltonian cycle or an empty list indicating that hamiltonian cycle was not found case 1 following graph consists of 5 edges if we look closely we can see that there are multiple hamiltonian cycles for example one result is when we iterate like 0 1 2 4 3 0 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 hamilton_cycle graph 0 1 2 4 3 0 case 2 same graph as it was in case 1 changed starting index from default to 3 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 hamilton_cycle graph 3 3 0 1 2 4 3 case 3 following graph is exactly what it was before but edge 3 4 is removed result is that there is no hamiltonian cycle anymore 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 hamilton_cycle graph 4 initialize path with 1 indicating that we have not visited them yet initialize start and end of path with starting index evaluate and if we find answer return path either return empty array
def valid_connection(
    graph: list[list[int]], next_ver: int, curr_ind: int, path: list[int]
) -> bool:
    

    
    if graph[path[curr_ind - 1]][next_ver] == 0:
        return False

    
    return not any(vertex == next_ver for vertex in path)


def util_hamilton_cycle(graph: list[list[int]], path: list[int], curr_ind: int) -> bool:
    

    
    if curr_ind == len(graph):
        
        return graph[path[curr_ind - 1]][path[0]] == 1

    
    for next_ver in range(len(graph)):
        if valid_connection(graph, next_ver, curr_ind, path):
            
            path[curr_ind] = next_ver
            
            if util_hamilton_cycle(graph, path, curr_ind + 1):
                return True
            
            path[curr_ind] = -1
    return False


def hamilton_cycle(graph: list[list[int]], start_index: int = 0) -> list[int]:
    r

    
    path = [-1] * (len(graph) + 1)
    
    path[0] = path[-1] = start_index
    
    return path if util_hamilton_cycle(graph, path, 1) else []