[tom_mellior]

The reason you have trouble thinking of an example is that there isn't one. If you know enough Prolog to write idiomatic Prolog code, you also know enough Prolog to think of the cases where your code will backtrack and where it won't. Because idiomatic Prolog code doesn't do unnecessary backtracking.

[YeGoblynQueenne]

That. Prolog will backtrack to get all solutions to a goal, but there is no reason why a goal must have multiple solutions. Unless you program it that way yourself.

[downerending]

You may well be right. As far as I can recall, though, as of the last time I was regularly using Prolog, trying to do serious work on a (say) 1000x1000 array was a recipe for disaster.

The exception would be Turbo Prolog, but it was a rather restrictive subset of the language. Fast as hell, though.