To win, you must capture all enemy towns and castles and defeat all enemy heroes. Some Border Guards can only be passed if a Hero carries a quest artifact from a previous scenario, but the reward is great indeed.
Starting Bonus: Expert Navigation or 3 1st-level mage guilds or 1 3rd-level mage guild.
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
I recommend that you take the 3 1st-level mage towers as you will definitely be short on both gold and resources the first few weeks as you build up your three towns. In addition, you'll take one less day in building a City Hall in each of your towns which will help you out a lot. Alternatively, you could pick the 1 3rd-level mage tower in the hopes of being able to easily build a 4th-level mage tower and getting the Town Portal spell. However, you'll eventually have up to seven towns and so the odds of getting Town Portal is very high already. I'd go with the 3 1st-level mage towers, but it's all up to you.
A potentially sneaky tactic is to check out the secondary skills given to the three starting heroes and, if you don't like them, restart the map and they'll have a different set. It's possible to have up to two secondary skills (in addition to the one that won't change) so don't fret if one of them has a skill like Luck.
This is a HUGE map and it will definitely be easy for you to get overextended and find yourself lacking in gold and resources when you need to hire troops. In addition, there are a lot of powerful artifacts that the enemy can get before you and can that could very well tip the odds in their favor if you aren't fast and pay careful attention to what you build and when. You can explore in safety once you have holed up the enemy in O5a but until you do, don't get sidetracked.
Your first goal is to build a City Hall in each of your towns and a Capitol before week 2. There's a Hill Fort just north of the Tower town at A3 and so you can have 3 Titans at the start of week 3 if you build every creature generator and the castle. This will enable you to head below ground and start taking over enemy towns.
Meanwhile, build a castle in the Rampart and Castle towns and the level 1-4 creature generators with priority given to the Castle town. Resist the urge to build anything else in these towns because it's important to be able to have enough gold to buy all of the Tower troops at the start of week 3 and to upgrade them all. So first build the Tower structure, then the Castle structure, and finally the Rampart structure.
While you're building the structures, be sure to flag resource mines and pick up loose resources. Be sure to flag the gem mine northeast of the Rampart town when you have some troops as you'll need the gems to upgrade Giants into Titans. There are ore and wood mines next to the Castle and Tower towns so be sure to grab them first.
Sometime in the 3rd or 4th week, send out Jenova (with troops) and another hero from the Rampart town and have them take to the seas using the Shipyard to the northeast of the town. There are many artifacts and sources of gold and wood found in the water that will be very helpful as you continue building up your towns. There are also a few islands where you can land and get some more gold and flag some creature generators so having one hero with troops will be needed. You can build a Shipyard and then a Lighthouse in the Castle town to speed up movement in addition to flagging the Lighthouse on the water (marked on the map)
Be sure to have Astral head down E2a and pick up the Spellcaster's Hat (gives all level 5 spells) which is northeast of E2b. This, combined with Astral's more powerful army, should be the edge he needs. Now you can start taking over towns with Astral taking over either O1a/O3a or O2a/O4a and Christian taking the other one.
There will most likely be wandering enemies so you can't leave the conquered towns undefended. Until one of your heroes has Advanced Earth Magic and Town Portal, it will be a good idea to hire additional heroes in each of the towns, hire troops, and build up to a castle. If you went underground at the start of the third week, the enemy shouldn't have too much of a defense and so even nominal troops will defeat them. While they're waiting, have these additional heroes flag resource mines but don't have them go too far away in case an enemy hero comes wandering by. While you may not want to spend the money and resources to buy additional troops and buildings, this is far better than trying to backtrack to save a town from being taken over.
While you're exploring below ground, don't forget to keep on building the Rampart and Castle towns as well. You should have completely explored the water and if you have enough troops, have Jenova break through one of the Water Elementals and explore the land on the eastern side. There aren't any artifacts but quite a few resource mines and loose resources (if the enemy hasn't picked them up).
When all of the wandering heroes are killed and all of the enemy towns are taken over (except for O5a), it's time to keep a watch on the scouts they send out. There is one enemy hero with high stats who will also have already raided the Dragon Utopia to get the artifacts and who will have quite a few Black Dragons and will be using Armeggedon to good effect. Fortunately, he can't go very far away from O5a so if you don't go too close, you should be safe.
Now you can spend some time and explore the underground to pick up any artifacts, loose resources, and flag resource mines you may have missed. You can finish up the building of the Rampart and Castle towns if you haven't already and send out the hero who will face against the final enemy to gain some levels.
Once you're finished, give one hero the artifacts and troops and have him attack O5a. Astral should use have his troops focus on the Black Dragons while using his magic to whittle down everyone else. If there are just Black Dragons, as could be the case, use defensive magic and protect your archers. Once he's been beaten, track down any errant enemy heroes and you'll have won one of the hardest maps in Restoration of Erathia.