The digital signatures which are included in a transaction input to authorize the spending commit to (largely) the entire spending transaction. If any part of it changes (including which outputs are spent by it, or where the resulting funds are sent), the signatures are invalidated.
The "cryptographic puzzles" you refer to, if we ignore the script system, boil down to a cryptographic primitive called a digital signature. It is a collection of 3 algorithms:
- KeyGen(): generate a private key with corresponding public key
- Sign(message, private_key): given a message to sign, and a private key to sign with, produce a signature.
- Verify(message, public_key, signature): given a message that was allegedly signed, a public key, and a signature, verify if that signature was created by the corresponding private key on that message.
The key generation is generally handled by key derivation logic, which you've already been asking about here. The signing/verify functions come from ECDSA (for pre-segwit, or segwit v0) or from BIP340 (for segwit v1). The message argument is important here: when the message changed between signing and verifying, verification will (almost certainly) fail. If an attacker can construct a signature on a different message than messages they've already seen signed, without access to the private key, we consider the signature scheme broken. ECDSA and BIP340 are, as far as we know, not broken.
In the context of Bitcoin transactions, this message is called the "sighash". The details are somewhat complicated, but slightly simplified, it consists of most of the fields of the spending transaction (so the transaction which contains the signatures).
If an attacker takes a valid transaction's inputs, and reconstructs a new transaction with different outputs with those same inputs, the signatures won't verify anymore, because some of the message being signed changed.