He does like Sudoku. He loves Rush Hour, but that would be tempting to play with and might get wrecked.
These were 2 things I thought of right away - definitely Sudoku! Also a good maze or dot to dot book. Tangrams would be fun too.
At that age we liked the Brain Quest books and flip card sets. I like the idea of the logic book you mentioned and this might be a good time to introduce some kiddos to analogies too with a basic workbook or even a simple word scramble workbook.
A simple set of dominoes would be good and along the lines of Rush Hour - how about Quirkle.
That is all I can think of for now. I may have more for you later.
