Sudoku solvers are not difficult to write. Efficient brute force solvers are probably a bit harder to implement well, but I wouldn't be surprised if a good number of people here could write a good solver in some form of another.
Automated theorem proving isn't very difficult either. It's another one where it's tricky to write one that is extensive, but it is by no means overly ambitious for someone who understands a few simple rules of propositional/prepositional logic.
Captcha solving is one where I'd be a bit at a loss, but that's because I have almost no background in graphics. I'm pretty confident that after talking with some people and reading a book or two, I'd be able to write one that can solve fairly simple captchas (eg, not distorted very much).
Honestly, I don't think any of those would be good thesis topics, unless you're doing something really revolutionary. I think all of the topics on the list have been beaten to death, and I've written everything on there except for an anagram and captcha solver.