Sudoku:
I would also consider the first 20 hours of playing Sudoku mentally challening, afterwards it is just repetition. Sure it can be nice, but you aren't realy learning new things any more.
I would recommend learning mnemonics I you want something that challenges your mind. It is also a useful skill to have.
I you want to play some game I would recommend Go. It has like Chess a high intelletual component, but intuition tends to be a bit more important than in chess. In addition the game is more about finding the best moves than about trying to lure your opponent into a trap.
If you want to try Go
here is a link to an online server.