How to prove that a hash or an encrypted message was obtained from a plaintext that has a certain pattern?
You are correct that a normal hash can't do what you want.  They are designed to not leak any information about the message, so given just the hash output you can't determine if the message has any particular structure.

You can use format-preserving public key encryption on your messages to produce outputs that have the same structure as the inputs no matter what that structure is.  In this way, you have defined a permutation on your legal messages so every output has a pre-image.  In fact, the person running the game doesn't even need to know the answer in order to start a round.  That is, they can set a target value without picking a solution and hashing it.

In practice, this can be easier for some message types than others.  For your permutation example, there's a natural way to map messages to the range $[0, n!)$ so that it's simple to determine if a value is legal.  On the other hand, since your message space ($40! \approx 2^{160}$ bits) is so much smaller than the block size of a reasonable ECC key, it will take a lot of encryption operations to produce a legal message.

Maybe you can use another one-way function like $f(x) = g^x \mod p$ with a $p$ close to the number of valid messages.