In particular you want something a problem with the following attributes:

- must derive somehow from the block data you're trying to mine, otherwise you could reuse your work for an different block and make double-spend attacks trivial. It's very important that once a new block is mined everybody else must start from scratch for the next one, otherwise you could "premine" an arbitrary number of blocks and later append them at an arbitrary position in the block "tree", potentially rewriting history.

- difficulty should easily be modifiable to account for the current "hashrate" otherwise your blockrate will go whack as the amount of computing power available changes. It also means that you should be able ahead of time to guess the difficulty of a problem and the average amount of processing power required to solve it.

- easy to validate: the nodes of the network should be able to check that the proof of work is valid using a tiny fraction of the computing power necessary to actually produce the proof (finding hash collisions is hard, verifying them is comparatively trivial).

- doesn't require access to a centralized resource. If you need to connect to some central repository to fetch the work set then not everybody is on equal footing. You have a single point of failure and some miners could have privileged access to the work data.

It's very difficult to find real world problems that have all these attributes.