The miner's identity (more or less) has to be one of the inputs to the problem, so that everyone is actually working on a different problem and you can't "steal" a block just by broadcasting another person's solution faster and wider.

Maybe there could be useful problems with this property, but it's not trivial to find them.