Building your own armies
I think the game would be more interesting if there was some kind of deckbuilding element to it like in Clash Royale, or how you get to build your own armies in Clash of Clans. One way of achieving this could be attaching a color (green, blue, purple, ...) to each kind of troop. Instead of having puzzles with X Barbarians, Y Archers, ..., you would have puzzles with X Green troops, Y Blue troops, and so forth. The color requirements are specific for each puzzle, but you would yourself get to decide how to meet them. Lets say the puzzle requires you to use 10 Green troops. You could choose to use 10 troops that are identical, or maybe 5 of one kind of green troop and 5 of another kind. During battles, all adjacent troops of the same color would attack together, even if they don't have the same type (e.g. barbarian). I think this would keep the core gameplay very similar, but add a lot of strategic depth to the game.