To win, you must capture all enemy towns and castles and defeat all enemy heroes. Your Heroes will be limited to 12th level in this scenario, but your 8 strongest Heroes will be available to you in the final scenario of this campaign. Starting Bonus: Pillar of Eyes or Mage Guild 1 or Battle Scholar Academy.
Click on a map to see a larger version.
Green - Friendly Town
Red - Enemy Town
Grey - Neutral Town
Yellow - Underground Passage
A# - Allied Towns
O# - Opponent Towns (a,b,c,d,e,f,g indicates which enemy)
N# - Neutral Towns
M# - Mirror Entrances (a) and exits (b). two-way unless stated
E# - Exit (a) entrance and (b) exit
S# - Seer (a) and the location of the item (b)
G# - Guard Tents (a) and the location of the Guard Tower (b)
J - Jail
X - Ambush
At the default Easy difficulty, it doesn't really matter which of the starting bonus you take since you'll end up by building all of them eventually. I took the Mage Guild 1 so that I could build a City Hall faster and give my starting hero some spells.
I followed the blue path to take over N1 and then N2 because N2 has an Upgraded Labyrinth and can produce Minotaur Kings. There are Medusas guarding N2 but with Magic and/or Tactics, you won't take many losses. This is the best unit you will have access to for quite some time and is powerful enough to subdue the surface. I suggest that you build a Castle at N2 and wait for the next week so you can take as many Minotaur Kings as possible through E1a. Except for O2a, most of the towns above ground are limited in what they can produce. So take over O1a (which is east of E1b), then head northwest to take over O2a, east to take over O3a, and finally southwest to O4a. You don't want to actually conquer O4a yet because you want the time to hire up to 8 heroes and to get them all to level 12. If you park a hero by O4a, you can effictively trap them and explore the rest of the map in piece.
While you're doing this explore the underground, build up A1 and N2, take over N3 and N4 (limited so use them for gold and resources), and build up heroes. If you work quickly in squelching the enemy, you probably won't even see them underground.
An easy way of leveling new heroes to level 12 quickly is to use the Altar of Sacrifice that is south of A1 in the underground or in the muddy area above ground. You can get rid of your less powerful troops as well as those that joined you to quickly level heroes without having to search out battles or Learning Stones.
Make sure you have your heroes visit the places of learning to bolster their stats and to build Mage Guilds in every town. Very few maps give you the opportunity to have seven level 4 Mage Guilds (and a few at level 5) so you can have very powerful magic heroes that will transfer over to the next map. Once you're finished attack O4a, which will have very few troops and will be an extremely easy battle, you will win this map.