The hard part here is encoding a heuristic that is capable of improving the time complexity of the naive exponential algorithm asymptotically so that it becomes

The hard part here is encoding a heuristic that is capable of improving the time complexity of the naive exponential algorithm asymptotically so that it becomes useful. People are really impressive. They're capable of realizing where they broke something and seeing when continuing down a path won't lead to a solution, which lets them mentally prune the search tree dramatically. Getting a computer to do the same... For fun: if you can encode a human's cognition and spatial awareness for things like this, you can probably do the same for NLP, then write a tl;dr app that massively outperforms summly and sell it to Google for more than $30M. :)