The part of the original puzzle that made it difficult for me to envision a computer solution to was where they give arbitrary topics. For example, "US States". Obviously, this has 51 possible answers (ok, really 50 - I'm including Canada :-P), a subset of which would be valid depending on the maximum length of the word. Programmatically solving that would be a challenge unto itself. Now, if you're going to generate categories yourself, you could define it to be solvable.

In the original post, my wife had looked for answers in each category trying to maximise the count of 'a's, thinking that would get the best possible score. We don't know if 'e' would have been a better choice, since we didn't try to optimise that. However, a more general application could possibly handle many more answers by having categories with all possible answers in some sort of database. For example, if there is an on-line crossword dictionary, crossword clues make great categories, which is fitting since the original problem came from a puzzle book including crosswords, and then querying from said dictionary should be a relatively solvable problem. Of course, this blows "maximum words in a category" out of the water :-) Then again, even a crossword dictionary won't have every possible answer - just ones used in crosswords. I wouldn't expect a category of "historical English Monarch" to have every monarch ever in the dictionary...

Your assumption about points is correct. Every letter in all words counts.

Of course, you're free to define your own puzzle that is loosely based on the above. You could define your own categories as groups of words in each category (having overlapping words where they can only be used in one category does make it more interesting). Or, for example, you could try varying the score for each letter, especially since a computer is doing the addition anyway. For example, what happens if each letter counts for double the previous? How about each letter counts for its position in the Fibonacci sequence? Maybe each letter gets its own fibonacci sequence, and the last number for each letter counts (e.g., if there are 2 a's and 3 b's, the a's get 1 point as the second number in the sequence, and the b's get 2 points as the third number in the sequence)? Do these variations really make for any difference in tactic? I doubt it, but that'd be like a premature optimisation that'd need benchmarking :-)