Dave Munger over at Cognitive Daily picked up the New York Times article on the Japanese gaming company responsible for the Sudoku craze. He recommends their Kakuro puzzles (see e.g. the Washington Post), which are rated one to four stars for difficulty. Some people are better than others at puzzles, and experience helps. But there's a limit to human cognitive capacity; as Dave says, "I've never seen a five-star puzzle."
The Times describes how Japanese puzzle solvers tinker and improve puzzles, presumably to make them just hard enough to be a challenge. If puzzles are too easy, it’s boring; if they’re too hard, there’s no point attempting them. We humans can clearly create puzzles we can’t solve ourselves. However, some of these “puzzles” aren’t games we can ignore if they’re too hard, or simplify at will. They’re critical artifacts and infrastructure like software, financial systems, and webs of trade.