While I don't have direct experience with either of these (I just googled for "python prolog backtracking"), you could probably do just as well in idiomatic Python using generators:

  * http://codespeak.net/pypy/extradoc/paper/prolog-in-python.pdf
  * http://mail.python.org/pipermail/python-list/2005-October/348485.html

I think Peter Norvig has written about this, too.