I just wanted to mention that there is a sort of solution to this problem but it is likely to not be available for you; the solution is called "homomorphic encryption" and it allows for a client to perform a known computation without knowing exactly what values they're computing with, and a server to therefore check the structure of the computed value to prove that the client did not just send a random string back but actually built it out of the several values provided.
The problem is, it is either slow or incomplete, with "incomplete" meaning "doesn't incorporate a full range of logical primitives." Very often it is a partial system allowing some encryption and decryption operations E(), D(), plus some complicated operation ⊕ such that
D(E(A) ⊕ E(B)) = A + B,
or the like.
So let's see how this solves the problem for some games. Consider a "lights out" type game where you are pressing on the N hexes of a hexagonal grid and each one toggles both its state and the states of those around it. This is a commutative algebra on those "presses" and hence there will be no more than N presses total in a given solution, plus each hex only depends on the initial state plus the presses of its own hex plus the 6 hexes around it.
Since our homomorphic encryption scheme only allows +, not XOR, we give each hex a 3-bit counter for the number of times it has been flipped. (The client software will automatically shrink each double-press of a hex to just one press.) The actual flip actions are therefore bit-vectors looking like,
001 001 000 000 000 001 001 001 000 001 001 000 000 ... 000 00000000 00000001
In other words they have 1s in each of these 3-bit fields that it flips, plus a 1 in some 16-bit counter.
We encrypt all of these with a homomorphic encryption scheme, send each of them to the client, and the client sends us back an encrypted value computed from these encrypted values we sent back. We then decrypt this and AND the decrypted value with the bitstring,
001 001 001 001 ... 001 11111111 00000000
and compare with the initial game-state adjoined with 0 for those 8 counter bits.
If they send us a random value, their chance that we accept it is 2-(N+8) and therefore their only useful way to pass the tests is to use the values we gave them in some allowed combination. They have access to some moves that we are not allowing them directly due to integer overflows, but we can always make the fields wider than 3 bits to make these costlier for the counter at right. But we were never transmitted their individual button-presses, much less replay the history: we accepted a vector saying "here is how I flipped the grid," which is the "super-insecure thing" that everyone is cautioning you about, but we did it in such a way that they cannot do the things we're worried about without access to a secret key.
Instead you see this sort of thing in cryptographic voting where you want some assurance that a voting machine doesn't spontaneously give 1000 votes to Alice.