I'm imagining that constructing the 'solution worlds' is some balance of knowing when to pull back from the more RNG-y Keys (ones that merely increase the rate of certain rooms) and utilize the more guaranteed Keys (ones that spawn certain rooms). So theoretically, with the right Key loadout, you should have a pretty low chance of failure - part of making sure this is the case is the solutions being flexible (e.g. a desert being 4 contiguous Sand rooms, vs. an exact 2x2 pattern - allows for some failure with RNG. Likewise if a desert is 4 or *more*, vs. exactly 4).
That being said, I do feel like there's something off to the whole solution I outlined in the post. Namely, I wonder if I'm looking at the 3D section of the game wrong - I feel like there's little significance to the rooms themselves, if most of the time you're just playing a little card game with adding on the doors. There's probably some way to mitigate this (maybe adding some diversity to what you do in the shuffled world - not just trying to construct treasure paths. Maybe some more freeform exploration options), but it'll take some more thinking/testing!
And thanks for linking that game! It's interesting what can be accomplished through physical games in terms of randomness/deduction.