An efficient Algorithm for Hamiltonian circuit

Question

I recently discovered the Hamiltonian Path/Circuit in CodeBullet's Snake A.I. video and decided to give it a go myself. I wrote a basic Depth First Search algorithm to visit all the nodes in a graph and store the path when the circuit is complete.

Here is the pseudocode for the algorithm:

# Global list to store the Hamilton Circuit
hamiltonPath = []

# Recursive DFS Function
def dfs(node, start, currentPath = [], depth = 1):
    # Return if the circuit is already discovered
    if hamiltonPath != []: return

    # Add current node to current path
    curPath.append(node)

    # Explore neighbors of the current node
    for neighbor in node.neighbors:
        # Check if the neighbor completes the circuit
        if neighbor == start and depth == totalNodes:
            curPath.append(neighbor)
            hamiltonPath = curPath.copy()
            return

        # Otherwise if neighbor is unvisited continue DFS search
        if neighbor not in curPath:
            dfs(neighbor, start, curPath.copy(), depth + 1)

This implementation works in theory since it does provide me a solution for a 6x6 grid and below but the problem is, it is extremely slow. It could not even provide a solution for an 8x8 grid when in the video, it was mentioned that it was a very fast algorithm which also showed since he had computed Hamiltonian circuits for 50x50 grids.

I would really like to know how I can speed this up since I am sure my beginner skills are not enough to point out some glaring flaws which you could probably see pretty easily. Any help is appreciated.

Unless you're planning on parallelizing your dfs, there's no need to re-copy the entire path on each dfs call; just backtrack instead. For larger grids it'll reduce the time complexity to make subsequent dfs calls to O(1) instead of O(n), where O(n) is the path length. — wLui155, Apr 01 '21 at 16:06
Also when checking if a node has been visited already you should consider using a more efficient data structure over a list. It may help to use two data structures, where one is the path as a list and the other is the container checking if a node has been visited yet. — wLui155, Apr 01 '21 at 16:09
@wLui155 I think I figured it out. I believe the fundamental problem was trying to find the Hamiltonian Circuit using a DFS. DFS would generally be used to find the circuit in a general graph, but this is not a general graph! I am specifically dealing with grids here, which means the problem can be extremely simplified. I can basically hardcode some logic to find the Hamiltonian circuit based on the dimensions of the grid, since the circuit has a specific pattern depending on whether the rows are even or odd. And using that, I just calculated the circuit for a 1000x1000 grid! Works perfectly. — Ahmed Mustafa, Apr 03 '21 at 14:29
@AhmedMustafa " I can basically hardcode some logic to find the Hamiltonian circuit based on the dimensions of the grid, since the circuit has a specific pattern depending on whether the rows are even or odd." - can you share what logic this is? — umop apisdn, Mar 04 '22 at 18:06

score 1 · Answer 1 · answered Mar 08 '22 at 19:11

As mentioned in the comment above, I found a hardcoded approach to find the hamiltonian path in a grid. The only caveat is, it doesn't work with odd x odd grids.

Here is the code:

def HamiltionPath(rows, cols):
    # No solution case 
    if rows%2 != 0 and cols%2 != 0:
        print("No solution exists")
        return []
    
    # Initialize path
    path = []
    
    # If rows are even
    if rows%2 == 0:
        # Starting point
        j = 0
        # Start traversal
        for i in range(rows):
            if j <= 1:
                while j < cols - 1:
                    #print(i, j)
                    path.append(i * cols + j)
                    j += 1
            elif j == cols - 1:
                while j != 1:
                    #print(i, j)
                    path.append(i * cols + j)
                    j -= 1
            #print(i, j)
            path.append(i * cols + j)
        # Final row
        j = 0
        for i in range(rows):
            #print(rows - i - 1, j)
            path.append((rows - i - 1) * cols + j)
    # If cols are even
    else:
        # Starting point
        i = 0
        # Start traversal
        for j in range(cols):
            if i <= 1:
                while i < rows - 1:
                    #print(i, j)
                    path.append(i * cols + j)
                    i += 1
            elif i == rows - 1:
                while i != 1:
                    #print(i, j)
                    path.append(i * cols + j)
                    i -= 1
            #print(i, j)
            path.append(i * cols + j)
        # Final row
        i = 0
        for j in range(cols):
            #print(i, cols - j - 1)
            path.append(i * cols + (cols - j - 1))
    
    return path

path = HamiltionPath(6, 6)
print("Path:")
for i in path: print(i, end = ' ')

Path: 0 1 2 3 4 5 11 10 9 8 7 13 14 15 16 17 23 22 21 20 19 25 26 27 28 29 35 34 
33 32 31 30 24 18 12 6 0

An efficient Algorithm for Hamiltonian circuit

1 Answers1