According to http://www.nature.com/srep/2012/121011/srep00725/full/srep00..., there is a nice correlation between perceived difficulty and a nice, objectively computable number.

So, a sudoku seems to be extremely hard iff η > 3.

And no, you don't need to do an exhaustive search.