Here is a nice paper on how to prune the execution tree when using amb: Non-deterministic lisp with dependency-directed backtracking; http://www.aaai.org/Papers/AAAI/1987/AAAI87-011.pdf

I've not played much with amb or Prolog, but it would be cool to try out some alternative strategies for exhausting the search tree, perhaps simulated annealing or something like that.