The patent office should charge some amount with every software patent application to be used for the determination of obviousness or prior art. Then it should post the problems on sites such as this one or StackOverflow as a request for comments. In addition to that, it should post the problem on a rent-a-coder type site. If any of these produced a result reasonably close to what is being claimed the application is rejected.

Simple and cost-effective. This would be far more efficient than having the uninformed at the patent office make decision from position of ignorance.