Last couple of days I've been pulling my hair trying to find the name of a bomberman-esque algorithm which finds solutions to the question of where to place a single bomb so as to blow all targets up, either directly if all targets are within the blast radius (and axis) of a single bomb (placed in an empty cell) or via a chain-reaction by exploding nearby bombs which share the same x- or y-axis within the blast radius (hence the graph exploration issue).
I can describe the situation as following: given a square cell matrix S (the board state) of order n, containing symbols which differentiate between different objects(empty cells, rocks, targets and bombs), identify all empty cells P where a bomb with blast radius R can be placed so that all targets T will be destroyed. The other initially untriggered bombs also share the same blast radius.
Edit: The objects function as follows:
Empty cell; The only place where a bomb could be placed. Allows explosions to pass through.
Rocks; Blocks explosion waves.
Bombs; Sits passively in a cell until reached by an explosion wave, at which point it explodes and sends an explosion wave outwards in the the x- and y- axis, up to the defined blast radius-length away.
Targets; If reached by an explosion will be destroyed and counts towards the end goal of finding a solution where all targets are destroyed. Allows explosions to pass through.
I started out with a brute-force variant which simply went through all empty cells and started a search from there, which is quite inefficient if all objects are in one corner of a huge board. I came to the following pre-processing insight:
Since a solution is only regarded as valid if all targets have been destroyed, I can therefore begin my search from any random T and if the path generated from that initial T does not destroy all T then there is no solution to that particular S.
I've made an algorithm which manages to find some solutions, but not for all boardstates I'm testing with. (currently only works if no other target is within a blastradius-length from the starting target).
Is this description ringing any bells for you?
My first instinct was an MST, but I've been unable to merge that algorithm with my description above.