Labyrinth
Game check numbers in a row.
If not A, then B and so on.

Explore the beginning of the labyrinth.;
a) 50% for nothing
b) 20% lost (-morale)
c) 20% weak guards
d) 60% weak guards with treasure
If game skipped every option, you will get
gold 100+random 0 - 149
crystals 10+random 0 - 14
random item level 3, rarity >=1

Chances to get treasure
a)with guards - 0.5*0.8*0.8*0.6 = 19.2%
b)without guards 12.8%

Explore the depths of the labyrinth.;
a) 30% for nothing
b) 30% lost (-morale)
c) 30% average guards
d) 30% barracks
e) 70% average guards with treasure
If game skipped every option, you will get
gold: 300 + random 0 - 349
crystals: 30 + random 0-34
random item level 4, rarity >=2

Chances to hire minotaur
0.7*0.7*0.7*0.3=10.29%
Chances to get treasure
a)with guards - 0.7*0.7*0.7*0.7*0.7 = 16.8%
b)without guards 7.2%

Search for the Heart of the Labyrinth.;
a) 15% Heart with strong guards
b) 20% nothing
c) 40% lost
d) 30% strong guards
e) 30% barracks
f) 70% strong guards with treasure
If game skipped every option, you will get
gold: 500 + random 0 - 549
crystals: 50 + random 0 - 54
random item level 5, rarity >=2

Chances to hire minotaur
0.85*0.8*0.6*0.7*0.3=8.5%
Chances to get treasure
a)with guards - 0.85*0.8*0.6*0.7*0.7*0.7 = 14%
b)without guards 6%

If you destroy Heart:
Gold: 1000 + random 0 - 1199
Crystals: 100 + random 0 - 154
random item level 6, rarity >=3
random item level 5, rarity >=3
Labyrinth is destroyed.

I am curious what do you consider to be "Weak" or "Average" Guards? (guess I should throw Strong in but I know I have no chance lol)

Also are they always the same basic Type of Guards or does it vary greatly?

And just wanted to add Thank You Very Much for the info given thus far.

Weak
4-6 minotaurs with average level 6
Average
6-9 minotaurs with average level 9
Strong
9-13 minotaurs with average level 12

I also noticed that the lab resets when you leave the province. Its very useful for high levels crystal quests when you get the kill 3 minotaurs 5 times in a row!

There is no such mechanic as reset.
Game uses "pseudorandom" generator, so if you rewind and make things like you did them first time you will get same result.

I meant that if you leave the province and then come back the lab is full of new encounters again. Or did I draw the wrong conclusion somehow?

As I understand it, the labyrinth is never "emptied" (unless you get the collapse result, of course). You can keep going back in over and over; what you find depends entirely on the luck of the event generator.

So does the game roll once for a) if no match roll again for b), if no match roll again against c) and so on?

Yes, it is.

From my experience, after using option 1 or 2 several times, I don't get any effects using that option again (it's always the "nothing found" outcome), so the number of times these options can be used is limited. If it indeed resets when you leave a province, it's an interesting thing I didn't know about.

If you flip coin 10 times in a row, you still can get 10 tails in a row.
There is no such thing like "resetting labyrinth". Game doesn't track amount and outcomes of your previous entries.

Thanks for digging up all of this, it's really useful info!

One thing I noticed, if you want to recruit Minotaurs it's actually better to go for the depths and not the heart of the labyrinth. It also avoids the possibility of destroying the labyrinth altogether.

I must have done a Labyrinth I found well over 50 times now, and while it is a nice way to farm (borderline overpowered, I would say), I have never ever gotten the option to destroy the Labyrinth.

How do I do that?

The initial post says choose option 3: search for the heart, and the chance of finding it is 15%. Defeat the "strong guards" and that destroys it.