Spatially oriented puzzles, density, and perceived complexity...
After taking about an hour in a game store, the owner finally told me a story about a bunch of genius Boeing employees that had spent large deals of time on a specific game, Rush Hour. Figured it was worth a shot with the game itself being 15 bucks and there being two expansion packs. Hell, with 120 puzzles after the expansions it has to provide some level of difficulty...
First, we have to realize the game is spatially oriented on a 6 by 6 grid. Generally speaking, the fewer pieces on the board the easier the puzzle is. You'll start out with small numbers of pieces for the low end puzzles and working with more pieces at the higher level. With more pieces you get a higher density of pieces on the board and the higher the density the fewer possible moves at any given time. In other words, increasing density decreases freedom of movement and therefore makes the decision tree of the game tall and thin.
In all there are a couple of possible decision trees for this type of game. you can have fat short trees where after each move there is a lot of freedom to decide the next move. This is great because it adds a level of thought at each level as you pick between the various moves. The tall thin trees discussed above happen as the density increases and you are forced to select specific moves with choices coming at critical tree sections as you switch from one tree section to another. The final option is a kind of free tree where there is both a large freedom and a large number of moves. A game like chess would fall into this last decision tree category.
Now, with most puzzles the more moves required to complete the puzzle, the more complex it supposedly is. I can kind of agree with this. However, I believe puzzles with a balance between freedom and move count actually turn out to be more complex. To bring this home, some of the Grand Master puzzles in Rush Hour only have 2 or 3 critical junctures and the rest of the movements are a fixed function of the density (aka required), while many of the Advanced and Expert puzzles have great freedom and often have 10 or more critical junctures and even false move sections.
The puzzle rating complexity, being based on move count often falls short in positively identifying the true complexity of the puzzle at hand. Especially when the mathematical complexity or algorithmic complexity has nothing to do with the human problem solving complexity. The perceived complexity is a much better measure where the complexity can be based on the difficulty from an actual player's stand-point. These are often relative measures, but when you have a series of puzzles, you can logically based complexity of your later puzzles from the first few puzzles. The complexity may take into account not only the number of moves, but also the initial analysis complexity (can I see how the puzzle can be completed at first look), move type complexity (the various types of transforms that are required), and freedom of movement (number of open decisions in the tree).
Just goes to show that more isn't always better, especially when it comes to puzzles.