My Python answer http://stackoverflow.com/questions/746082/how-to-find-list-o... runs in 200ms on my laptop. It probably isn't actually within a factor of 2 of this C code, since I don't know what input board it was tested with to get 100ms, and it matters how much of the dictionary gets pruned while loading. I just stuck in a random 5x5 board and got 412ms real time, still pretty tolerable.
Edit: The next Python answer there uses a trie and takes 16.7 seconds on the 4x4 board. I like tries because they're elegant, but I hardly ever use them because the built-in collections are well-engineered even for problems you'd think are made for a trie.
Edit: The next Python answer there uses a trie and takes 16.7 seconds on the 4x4 board. I like tries because they're elegant, but I hardly ever use them because the built-in collections are well-engineered even for problems you'd think are made for a trie.