15x15 Medium - are they actually difficult?

[CopperCable]

Maybe I've gotten really unlucky, but it seems that more often than not, the medium difficulty 15x15 puzzles can be hard.

So my question - what makes a 15x15 puzzle easy, medium or difficult? How does the system know which puzzle is harder than the others?