Okay what does come to our mind when we think of backtracking problems? I bet the eight Queens problem. Now as old as it might seem, given the fact that chess is being played 5th century AD onward in India, this problem was posed in the form known to use only back in 1848 ( http://en.wikipedia.org/wiki/Eight_queens_puzzle ); not old enough!!
While backtracking is sophisticated and you would assume that it would have required a mathematical mind to formulate a problem using it, you might be disappointed to know that perhaps the most perfect us of backtracking was thought of in creating myth :).....
Ever heard of Ariadne's thread .... I guess the early Greek priests weren't a bunch of idiots after all.
In case you haven't, go read the wiki thread on Minotaur of Crete ( http://en.wikipedia.org/wiki/Minotaur ) and marvel at the smartness of using such a thing in a myth.... not bad, eh?