Tanktalus,
I agree that writing a program to find words that fit a category is a bigger challenge all unto itself. That's why I took your approach of assuming the words that fit were already known. My categories will just be cat 1 .. N. I just want variation to test the robustness of any possible solution. Using an existing database is also a possible approach but goes beyond the scope of what I am intending to do.

Regarding the "maximum words in a category". That is a configurable parameter that I envision being used to bound a given puzzle so that an implementation has a realistic chance of solving for the "best" combination of words. On the other hand, if you are going to go with a heuristic approach then it may not matter - but being configurable allows the user to make that decision.

Regarding making variations on the rules for the purposes of exploration - sure, but I wanted to make sure I had the basic idea since your original post left me more than a little confused. Now that I know I am on the right track I can think about it further. Thanks!