Just started the game myself. Playing Paladin though, but on impossible, so this should be somewhat the same (1,000 leadership at the moment).
First off, only Invincible could really be considered too tough, and Invincible has different levels in itself, so try and engage the enemy, see for yourself if the troop composition is indeed too tough to take out.
Try getting high hit point units, and healers/resurrecters. Debir has (possible) royal thorns, griffon eggs, beholders, inquisitors, priests. Scarlet has (possible) paladin, knight, royal griffin, archmages.
See attached no-loss battle I had on Scarlet against a supposed "lethal" enemy with hero. Used royal thorns, priests, inquisitors, knights, archmages. The only support abilities that I used for the fight was the dragon kick ability (1 upgrade), stone wall and Heal.
Mage shield on the knights who engages all opponents, stone wall to control enemy path, and pray that the enemy hero doesn't cast damage spells (or casts damage spells only on your archamges/royal thorns/knight who can take the hit without a loss).
|