if multiple people can submit solutions, first one getting paid, then you could do this mining style.
Multiple people submit computational power to the problem. First one to it gets the reward, if no one does it goes back to you. Time limited and searchers only have to submit as much CPU time as they're willing to.
However, I don't know this system well enough to know if that's feasible.
From reading up on this a little (and confirming with Sean), it seems that before the payment is committed the solution must already be available, so this may not be a good protocol for expensive to produce, bespoke solutions that are only of interest to a single buyer. If, for example, I wanted to buy the factorization of a 768 bit RSA modulus, someone working on a solution for me would have the risk of me not paying - I still would not get the solution, but they'd be out the computation costs.