Proof of Work is an algorithm that rewards participants who solve a cryptographic puzzle...
This puzzle consists in scanning for a value (called Nonce) that when hashed, the hash begins with a number of zeros.
What you describe here is a specific Proof of Work algorithm known as Hashcash.
There are many alternative Proof of Work algorithms not based on hashing, as explained in this article
http://cryptorials.io/beyond-hashcash-proof-work-theres-mining-hashing/