Love logic puzzles and have shared quite a few types with my kids over the years. Never got to grips with chess though!
I can't remember what they could do at 5 but these might be worth a try:
Some online and printable easy sudokus on my site kershaw kids along with a simple mastermind style game.
conceptis has lots of sample puzzles including some ultra easy ones that may be suitable - you will need to search through each section though.
I enlarged and copied a few japanese style picture puzzles from a nonograms book (sunday telegraph book 1) for one of my children when they were quite young - they had the logic to do the easiest ones, but not the fine motor skills required to shade in the tiny boxes - hence the enlargements.
We had kakuro for kids book 1 which I think my son enjoyed from about age 6 - his numbers were enormous though, so could have benefited from enlargements here too.
On android there is a game called 'unblock me' which is like rushhour. I think sokoban might be worth a try too.
Looking through the games cupboard, these are the ones my kids liked:
hoppers, logic links, junior mastermind, towers of hanoi, rush hour, set.
Also, I picked up various logic books from "The Works" and just tore out the ones I thought they could do.
Good for keeping them occupied when out for meals, in waiting rooms etc.