If you don't ask "really hard" questions[1], candidates instead complain because "any child can solve this" and feel not taken seriously. Somebody will always complain.
"asking logical puzzles is fine"
No. NO. NO. That's the thing that isn't fine, because solving a logic puzzle relies on one critical insight. It's rolling the dice.
What you want is a question that has multiple answers, that's dirt easy, and where you can ramp up the difficulty to the moon if the candidate breezes through. These questions are hard to find, but they exist. They require investing some thought, so they're unfortunately not asked too often. But they work. (For small values of work. There is no good interview process)
[1] Somewhat hard. It's solvable in 45 minutes, it's not that hard.
What you want is a question that has multiple answers, that's dirt easy, and where you can ramp up the difficulty to the moon if the candidate breezes through. These questions are hard to find, but they exist. They require investing some thought, so they're unfortunately not asked too often. But they work. (For small values of work. There is no good interview process)
[1] Somewhat hard. It's solvable in 45 minutes, it's not that hard.