Related: I wrote a mahjong game many years back (the tile matching version; not real mahjong).

It turns out you can have unwinnable boards if you build them purely randomly.

So I ended up having the app play the board in reverse to make sure it was winnable!

It still managed to hit stalemates, while playing backwards, but they were very rare. I just restarted instead of trying to avoid that situation algorithmicly.