This is, perhaps, a controversial take on
Randy Abrams' post about password constraints, but I think it bears out. The more complexity constraints you enforce, the fewer passwords there are that can satisfy those constraints and the less time it takes to run through them all. If I enforced a set of constraints that were so strict that there were only 5 passwords left that would pass all the rules, you can bet those 5 passwords wouldn't be considered strong.
Another way of thinking about this is, password policies leak information about the passwords in the system - information about what all the passwords have in common (they all have a character from set X, Y, and Z). Leaking information about shared secrets doesn't improve the strength of those shared secrets.