Hamiltonian Cycles
Over quarantine, I picked up a project to write an algorithm to find all Hamiltonian cycles in a square grid. A “grid” in this case is a graph made of nodes and links that connect those nodes. The nodes are arranged in a square with links connecting them vertically and horizontally, making a grid. A Hamiltonian cycle is a path through the grid that meets every node exactly once and returns to the starting node.
The grid is not directed, meaning that it is possible to travel in either direction on any link. Additionally, in a square grid, every node has two, three, or four neighboring nodes that connect via a link. To find a Hamiltonian cycle, my algorithm creates every possible directed graph, where every node links to only one of its neighbors in one direction. It then traverses each of these directed graphs to decide if they are Hamiltonian cycles. If a grid has a side length of m, meaning m nodes on one side and thus m2 nodes in total, there are 16⋅34(m-2)⋅4(m-2)(m-2) directed graphs that the algorithm has to generate and check. Even with all other optimizations, this brute force strategy is far too inefficient to be useful. However, it is still an interesting endeavor into algorithm design and computational complexity.
A personal computer can run the algorithm for an m of 4, which is 26,873,856 directed graphs. An m of 6 has 2,958,148,142,320,582,656 graphs. Even if a computer has the memory space to compute this many graphs, it will take over 3 millennia to do so. More details about the computational complexity and inner workings of this algorithm are in the PDF below, along with my Python code.