This is exactly what the Cuckoo Cycle [1] family of graph-theory Proof-of-Work systems gets its name from.
The puzzle instances are pseudo-random graphs in which edges are defined by the siphash24 hash function, and the solutions are cycles of length L, which have a chance of about 1/L of occurring.