He is using the classic AI method of heuristic-guided graph search with search-space pruning. That still doesn't make the worst case tractable, but it does improve a lot on brute force enumeration.