I remember implementing an n-queens solver in Prolog for a programming languages course. Prolog does backtracking on its own. The style of programming is very different from anything else I've ever programmed in--it's a really interesting language. It doesn't get used much in production, but I've seen isolated instances where it has been. Initial implementations of Erlang were written in it, for example.

https://secure.wikimedia.org/wikipedia/en/wiki/Prolog