After 2 won games, RNG finally blessed me with a random map fragment, and I could start the quest.
It ended rather quick with my demise, but I must say Katharamandus is the best boss in the game. Won't spoil anything, but its difficult and fun to fight.
On other hand, the behavior of stone statues in Rolf's fortress is really strange and uncalled for