To win, you must capture the city of Kleesive. Some Border Guards can only be passed if a Hero carries a Quest Artifact from a previous scenario, but the artifact beyond the Border Guard will travel with you to the next scenario. Starting Bonus: Scroll of: Protection from Fire or Ice Bolt or Precision.
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
The starting bonuses aren't that great, especially since the final battle will take place on Cursed Ground which will prevent all spells over level 1 from being used. Nevertheless, I'd take the Ice Bolt scroll since it's a nice upgrade from Magic Arrow and it'll help you take out wandering stacks until you get enough troops.
I've found that it's possible to win this map by using either the Castle or the Rampart troops so feel free to pick the one you like and use the other two towns for gold and resources. Whichever town you choose, it's important to explore the area surrounding your towns and to flag all mines and grab all resources. Be sure to use a might hero since Kleesive is built on Cursed Ground and you won't be able to use any magic above level 1. You will be protected for at least the first month because the only way to get to your areas are guarded by Pit Lords. By the beginning of the second month I had four Archangels and a sizeable amount of troops and made my way to the Inferno area.
There are four Inferno towns but most of them will not be built up and there will most likely be just one enemy hero in the area with low-level troops. Once you have taken over all four of the enemy towns, it will be a while before the enemy leaves Kleesive since the only path out is guarded by Archdevils. So you should take the time to go to the area south of A3 where the Quest is and turn in the Badge of Courage for the Charm of Mana that will carry over to the next map. There are quite a few refugee camps in this area so you might get lucky and pick up some good troops. Just watch out for the ambushes.
Seer 1 asks for the Sword of Hellfire and will gives you the Shield of the Damned which you take to Seer 2 to receive a Tome of Fire Magic to take to Seer 3 who gives you the Lion's Shield of Courage which gives you +4 to all skills. Alas, this artifact doesn't carry with you to the next map but is helpful especially since you can't use high-level magic in the final battle.
Once you have a good amount of troops, make your way to O5a and battle the Archdevils that guard the only path to it. It's not that hard to have one hero visit all of the places of learning in the Inferno area so you might want to do that to tilt the odds in your favor. If you want a higher score, use the same technique you probably used in Steadwick's Fall by luring the enemy out of the town by using a scout. You will face a few Archdevils but they will not be much of a threat, especially since they usually teleport from behind the safety of the castle walls. Once you've taken over Kleesive, this map is finished.