More difficult vs more tedious
Often, I see puzzles that are labelled as difficult, but are in actuality just more tedious. Consider flat rectangular jigsaw puzzles. What makes such a puzzle easy? We could imagine a jigsaw where each male and female end are given numbers, so you know exactly which male end fits which female end. Such a puzzle doesn't become more difficult given more pieces, it just becomes more tedious. What else could make a puzzle more tedious? Well, if the puzzle were all one color, then beyond looking for edge pieces and middle pieces, your strategy must be trial-and-error. So we can see from these two examples, a puzzle taking longer to complete doesn't necessarily mean it's more intellectually stimulating.
So what does make a jigsaw puzzle stimulating? It's the fact that certain strategies can be discovered. After someone has done just a few jigsaws, they will start looking for edge pieces and middle pieces. They might also look for pieces that share a similar pattern, or solid color, and set those aside for last, as those are likely difficult to fit together.
Now finally, let's consider how we might tweak these puzzles in various ways. We've already mentioned changing the number of pieces, or making all the pieces one color. Another thing we could change is the shape. What about spherical puzzles, or puzzles that make other 3D shapes, such as a castle? Unfortunately, these are no more difficult than their flat rectangular brethren. The spherical variant is more tedious, and other 3D shapes will be more or less tedious, depending on the structure, but no more intellectually stimulating.
But all hope is not lost, there are at least two occasions on which we can inject mathematics into jigsaw puzzles. Here's one involving the hundred chart, and here's one involving the multiplication table for 1-10.