> How do we implement the lock boxes? I tell you SHA256(NONCE, VALUE) where the NONCE is chosen by me. Given the hash you cannot compute VALUE. To open the lock box, I tell you NONCE and VALUE, which you believe under the assumption that I cannot find a collision in SHA256.

That's the bit I was missing! The prover pre-registers the scrambled solution, so they can't cheat by making up values that fit the constraints.

Yes. The whole trick is a delicate balance between 1) committing to enough information that uniquely pins down the solution, assuming that one can open all the lock boxes, and 2) not opening too many lock boxes so that the verifier does not learn the solution.