@JilltheTooth Yes, the fact that every post beyond it contradicted it.
@gamefu91 Any type of learned skill, specifically those that require balance. Playing a musical instrument is a mental exercise vastly superior to all the puzzles in the world. Learning sleight of hand, riding a unicycle, balancing on one leg, dice-stacking, devil sticking, yo-yoing, etc. These are all extraordinarily useful mental exercises.
The best bet is to try a regiment that uses the two in unison. I have a friend that does crossword puzzles while he is on his treadmill. Listening to educational podcasts while jogging/biking/whatevering is another solid way to work the two sides of your brain in concert.
The larger point is that the brain is more than a computational engine and working out only part of it is very much like only working the muscles on one side of your body. The computational end can advance only so far if the physical end is not being exercised as well.