A slightly different (still brute-force) approach would be to march through all 5-letter strings until you find one that meets all criteria. See if there are any words in the dictionary that are anagrams (you can do this by canonicalizing all the words in the dictionary, as well as your guess).

You can take some of the brutishness out by constructing your guess from the lowest-valued letters in the hints. There's probably a recursive algorithm lurking in there, but it's not clear to me.