I always thought people generated sudokus with heuristics, e.g. the less numbers remain, the harder it is.