[silentbicycle]

Several Prologs have extensions for constraint programming, which give it much smarter hueristics. Instead of trying every possible combination of choices and failing/backtracking as early as possible (generate-and-test), it can use constraints to narrow the intervals / sets of possible choices - which usually sets off a chain reaction and further constrains the search space.

Once constraint propagation can't narrow things any further, it can copy the search space, use various search hueristics (such as splitting each copy of the narrowest interval in half), and see if that triggers further constraint propagation (or hits a dead end). It usually greatly reduces the amount of depth-first search. There are other ways of implementing constraints besides propagator-networks and space copying, but that's the way I understand best.

Generate-and-test is great for prototyping, but doesn't scale up to larger problems. Constraint programming fares much better.