Anecdotally, for awhile I was solving Soduku entirely in my head, and I had a noticeable improvement in memory. Once I stopped the improvement went away. So, there seems to be benefit to some sorts of brain training.
I memorize the layout, and solved the puzzle by imagining the grid. Don't use paper at all. The easy puzzles tend to have a certain symmetry that make them not too difficult to memorize.
