There are no reliable Purist solutions to the Labyrinth. It's not so much that it generates unsolvable maps (although it might, I'm not sure), but that it generates maps that become unsolvable if you take the forks in the wrong order. The really nasty ones end up being one long corridor with most of the monsters staggered a few squares apart. You have some smaller corridors that can be used for recovery, but if you explore those before you find the "real" hallway you're totally boned. You'll start running into several powerful monsters in a row and be forced to use all of your potions, and then it happens again and it's game over. The problem isn't really Rex, it's being forced to fight monsters in an inappropriate order with no chance of recovery.
The humble Bearmace opens up the solution space quite nicely, but if I had to bet real money on a Purist Labyrinth I would either take the Gorgon, the Half-Dragon, or decline the bet.
You can get a technically Purist victory by taking the Transmuter and using LEMISEE to scum for a nearby Binlor altar.