Have you tried it since the Mine King was re-re-adjusted to HP 10? It was much harder when he was HP 11, but now it seems comparable to the old version in difficulty.
My general strategy: in the early game, I try to open as much of the board as possible (so I favour multiple small monsters over one big one, and favour revealing squares over clearing known monsters). I never waste a heart -- if I have no other safe moves, I punch a wall. I try to reveal the monsters with the special scrolls (especially the Mine King) as soon as I can -- exploring the board helps to narrow down where they are. The sooner I can blow up the mines, the sooner I can get their points and make the board safer to clear! In the end game I try to clear the monsters largest first, so that I can use up exact numbers of hearts before levelling or using a heart scroll. The walls are more predictable now; in the previous version I would clear them before the lowest-level monsters, but now I leave them for last.