See Bleicher's "[Freezer][1]" that is a human/computer interactive proof agent: you make the "rules", and it iterates over positions. (The [article][2] from 2004 is rather old, and the given examples are solvable by brute means by now.)

  [1]: http://www.freezerchess.com
  [2]: http://www.minet.uni-jena.de/preprints/bleicher_04/FREEZER_.PDF