Proof of work scheme with one and only one correct answer
One obvious approach would be look at a discrete log problem.  That is, you pick an appropriate group of order $n$ (where $n$ is prime) and a generator $G$; for a challenge, you pick a random element $H$, and you ask for the value $0 \le k &lt; n$ such that $H = kG$.

This meets your requirements (1) the value produced is effectively random, requirement (2) one can search for the answer in $O(\sqrt n)$ time, (3) if $G$ is a generator, then there is exactly one such value, and (4) the answer can be verified in $O(\log n)$ time. In addition, the amount of work is tunable (by selecting groups of various sizes).  

For this to work, we need to select a group where we can't find discrete logs faster than $O(\sqrt n)$ time; I believe an appropriately sized random Elliptic Curve meets this requirement.

However, the chief difficulty with this suggestion is finding an Elliptic Curve group of the appropriate size; that's nontrivial, and all the precomputed Elliptic Curve groups I know are scaled to make the discrete log problem "infeasible", not "difficult".

Another group that would appear to be suitable is a small subgroup of a larger multiplicative group.  That is, we pick a large prime $p$ and a small prime $q$ where $q | p-1$.  We will then work in the multiplicative subgroup of size $q$ of the group $\mathbb{Z}^*_p$.  To create a random element of this subgroup, we select a random number $1 &lt; x &lt; p$, and compute $H = x^{(p-1)/q}$.  The order of the subgroup is, of course, $q$, and so if the work target is about $2^{32}$ operations, we may select a 1024 bit $p$ and a 64 bit $q$.  The chief advantage of this proposal over the Elliptic Curve idea is that it is much easier to devise a $p$ and $q$ of the appropriate sizes, rather than trying to define an Elliptic Curve.