Originally, I thought the CryptoNight puzzle was similar to the SHA2 puzzle, with a more exotic hash function replacing SHA2. In other words, the puzzle was essentially H(prev||nonce) < diff, but with H being the slow_hash in the CryptoNote code.
However, the CryptoNote website's description actually says, "As opposed to scrypt, every new block (64 bytes in length) depends on all the previous blocks. As a result a hypothetical "memory-saver" should increase his calculation speed exponentially."
I looked at the mining code, but I couldn't figure out how the puzzle differed from the one I described above. With that in mind, what exactly is the CryptoNight puzzle? How, exactly, does it depend on all the previous blocks (rather than merely the one immediately prior to it) in a way that scrypt does not?