In some scenarios I had in mind, as long as the correct answer is given, it wouldn't be so important to have brute force attacks. The coins would not be supposed to be for someone in particular, but for anyone who could give the answer and made it public. Anyway, to prevent dictionary attacks I thought you could add some salt, like in password checking in computers.
Alright. If you don't care if somebody finds the coins then no problem. But perhaps "password" is not the right term to use for such a thing.
Salting doesn't help much. Modern GPUs can brute force billions of (salted) password hashes per second. It turns out that most peoples passwords can be found this way, given only a hash. Inhumanly strong passwords can still work, but then what you've got isn't really a word per se, it's a private key!
I was also thinking in solutions to problems that are hard to compute, but also easy to check (like NP problems). You could offer a reward for a solution which checks right. You wouldn't mind brute force attacks, in fact you would encourage them.
Script is probably too limited to express a program that can check solutions to interesting computational problems, but you may be interested in this:
https://en.bitcoin.it/wiki/Contracts#Example_4:_Using_external_state