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.

Answer 1

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