Wesnoth strategy tip for "The Scepter of Fire" level

I was playing this game and every strategy I tried was losing. First I had recalled all my best units from previous levels, going massively into debt. I tried having four Shamans to keep everyone healed. All paths led to defeat. I could never defeat all the enemy kings and always had a key character die at the hands of a mass of troll-grunts. Even though I kept "staring over," each new strategy I tried was played out on the same map. That's because I only went back to around turn 2, after I had already recruited a whole bunch of folks.

Then I read in some forum for developers of the game about "randomization" of the map.

All my "retries" of the level above however involved the same map. Every time you start over in the game, you start with a new map. Due to this randomization, it is possible for one to have the Scepter out in plain sight down the main pathway. Once I had restarted the level and had this new and easy map, the level was a cinch. I only got out about 10 characters, and we stumbled onto the Scepter before we'd fought our fifth troll-grunt.

In retrospect, this points to an unfortunate design of the level, in that the tension between "cinch" and "impossible" was tied to a randomization factor at the beginning of the game: the map and Scepter location.