Proof of work is not really a 'puzzle', this is just a simplification that is sometimes used to describe what happens.
Mining involves creating a new block: the miners will take data such as the previous block's hash, transaction data, a timestamp, a nonce, etc, and put them together in a certain pre-defined way. Doing so is computationally easy, but the block created is not necessarily valid. In order to determiner if the block is valid, the next step is important: the miner will take the block they have just created, pull the 'block header' portion of it out, and run that data through a hash function.
The output of the hash function is what matters in determining whether or not a block is valid. The output must be within a range of values, as defined by the current network difficulty (as more mining power joins the network, the difficulty will increase, and the range of accepted hash values will diminish).
If the block's hash does not fall within the accepted range, then the miner will change the data in the block slightly, and recompute the hash function to get a new output. In practice this is done an unimaginably large number of times in order to find a valid block, as the chances of finding a valid hash on any single attempt is very small at this point in time.
So you could describe the way a miner assembles data into the block structure as a sort of 'puzzle', but I think the word puzzle gives the wrong idea in some ways too. The 'puzzle' is not hard because it requires a lot of computational power to do, it just takes a LOT of tries in order to find a valid block (and it takes a lot of computational power to try that many times).
Any single attempt could find a valid block, so it is not a matter of "the miner with the most computer power will win", however a miner with a lot of computer power will have a better chance of winning.