I don’t remember how I originally came across this challenge problem, but it tickled my brain, and I wanted to give it a shot. It’s clear the problem is a variation on that good old depth-first-search problem of finding a Hamilton Path on a graph – in this case a 2D grid graph. I knew the general problem to be NP-complete, but I wasn’t sure whether the constrained problem (on a 2D graph) was too.
I did some research and found papers and resources online: here, here, and later, here. It turns out that searching a grid graph with holes for a Hamiltonian Path is indeed NP-complete. The Quora problem is in an even harder complexity class: we want to find ALL Hamiltonian Paths. I’m no complexity expert, but it appears this problem is in the class #P.
I also wanted to try coding it up in the D programming language, which I eventually did. But at first I found it a bit cumbersome to “think in D”, so I started hacking in Python. I used the NetworkX libary to model the problem abstractly, which gave me an easy way to work with vertices and edges as Python objects. I had a solution to the problem in short order, but on Quora’s 8×7 example input, it took over an hour!
It wasn’t until I looked at Faase’s work (in the links above) that I realized a much faster search would not care about edges. It would visit only vertices, and make only local decisions about what vertex to visit next and how to cut the search short. I revisited and finished the solution in D, and then ported it to C for speed (using GCC 4.2 with optimizations in XCode) . This was actually quite easy to do, since I didn’t use any major D-specific language constructs.
My final solution in C completes the 8×7 example in just over two seconds on my 2.53Ghz Macbook pro. The code is up as a protected post. If you’d like to check out the solution, contact me for the password!