When my daughter was 6 we flew to Italy to see her grandparents house for the first time. I got her a handheld sudoku game (about £5 with unlimited games) and she's absolutely addicted to them now; solves 'extreme' ones in about 15 minutes and she's only 13-y-o!
So it could be I've just suggested something not to buy!