Maybe it is prudent to reduce the requirements based on difficulty (just like the army strength, per xp gain, gold income, etc.).
So, say, make it 50% of the current for easy and normal, 75% of the current for hard and 100% of it for impossible. That will not hurt the game.
__________________
|