I have done a LOT of programming in Prolog, and while I love the language for its expressive power, I have to agree with svenningsson that as soon as you try to do anything non-declarative it becomes a puzzle to use the ! operator (cut, discards backtracking options) in the right places, which is extremely error prone.
Though not perfect, one language that elegantly manages to combine backtracking and non-declarative (imperative/side effecting) code is Icon. It basically isolates expressions which can backtrack naturally from the general program structure (e.g. statements) such that it is relatively easy to see that backtracking will not lead to unexpected results, like in Prolog. I am not sure why not more languages are based on this execution model, my guess is that the majority of programmers are really stuck in sequential thinking, and backtracking is confusing.
I am not sure if backtracking compares with polymorphism directly. To me, it is more of an alternative to closures, as the #1 use for closures in most languages is custom iteration (think map/filter/fold etc). For example, in Icon I can say:
every write 10<(1..10)*2
Which takes a sequence of numbers, multiplies them by two, filters out those >10, and prints the result ("every" is bit like a repeat-fail loop in Prolog). In a list/closure based language, I have to write:
for (filter (map [1..10] \x.x*2) \x.x>10) \x.(write x)
granted, this is a bit contived as list comprehensions & currying can simplify this, and not all icon code is that terse, but you get the idea. The Icon version is not only more expressive obviously, but also has the advantage that it does not use intermediate lists and is "lazy" in a co-routine sense, i.e. it will write out the first number before getting to do *2 on the second element. This means it allows you to write code that is equally efficient even if you end up not using all results generated.