Hmm. A Markov chain where you actually do some kind of search? You build up a chain then backtrack and retry as necessary until you get something meeting the requirements.
Sounds like getting some sort of context free grammar out of it. There is a LR grammar algorithm that is very fast, you could use a Markov chain to generate and then a CFG to verify
[0] https://link.springer.com/article/10.1007/s10601-010-9101-4
[1] https://github.com/kastnerkyle/pachet_experiments