The puzzle would have to be procedurally generated so as to prevent the price feed publishers from possible insider trading (If they know the solution they can act upon this insight or share this info with a select few).
What would the puzzle frequency be? One per day to determine the next day's price direction? Or multiple puzzles per day? What kind of puzzle?
For a random direction we could have the feed producers monitoring a hash somewhere that is entirely unpredictable, the characters in the hash determine the outcome for the feed price (range of letters/numbers for positive/negative, potentially additional characters to determine the size of the price feed change)?
I see that the puzzle idea gets more complicated than I thought.... Will have to give it some more thought.
As for the random idea, there are several services that provide random feeds based on natural phenomena, which ensures a high degree of true randomness. Like you mentioned, we would need an algorithm to translate that into movement