This is the puzzle I have spent most of my time so far, including the VERY HARD ones.
I haven't found a perfect solution, but I have something to contribute - no one has mentioned memorization yet.
My program places one bomb at a random location (with the location hitting the most nodes played first), or it chooses to wait, and then recursively evaluates the board. Since a bomb and a round is consumed, the board becomes simpler and the recursion is guaranteed to finish, returning whether a bomb sequence is a winning one.
This is where the memorization comes in - my program remembers the losing bomb sequences that have been studied, for example, (0,0), (1,0), (2,0), so if the same sequence is repeated somewhere in the recursion in a different order, say (1,0), (0,0), (2,0), then the recursion can skip the evaluation.
The memorization has reduced the computation by about 100x, and my last case finished evaluation in about 2s, but it was still too slow to pass the test. Because in the last case the bomb sequence is not in the greedy path, it had to take some time to compute. Finally I passed the test by hard-coding the greedy evaluation to not consider bomb placements that only hits one node.
Many of the problems in the HARD category require some kind of memorization to reduce repeated evaluations, and I believe this puzzle requires it too.