Name of Bomberman algorithm?

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.

• Why not try reversing the goal? Start with all the targets T, and find all the locations of bombs that will blow it up. So if on the search it finds a bomb, you can extend the range to anything that would blow that bomb up. By the end you'll have a list of locations that will blow up each target, the location that occurs the most is the best place to put a bomb Aug 15, 2015 at 20:28
• Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. When posting a question, make sure to give enough context, and show how you tried to answer it on your own, so as to be very precise regarding your problem. This helps better answers. --- In this question, I do not understand the role of rocks and players. Aug 15, 2015 at 20:38
• @spyr03 You mean starting a new search from the beginning for every target? Or a width-first iterating over all targets, saving possible locations on a queue for further ? My current implementation handles the chain reaction but it's just the initial pathing choice which can mess it up (if another target is just besides the initial T location which is used it would have to move backwards almost..maybe I should think about that) Aug 15, 2015 at 21:29
• @babou Clear definitions for objects have been submitted. I tried to put the question more in general algorithm terms, since I wasn't sure my choice was correct and was wondering whether someone with more knowledge (or better memory) than me could immediately remember the name of an already existing algorithm suitable for this problem. If I were to post my implementation of all the C++ code (performance is on my mind) I would get into very minute specifics, which perhaps would be better framed as a question for the stackoverflow. Aug 15, 2015 at 21:34

As an example, Yellow denotes a target, red cells indicate the radius of the target such that if a bomb was placed in any of the red cells, it would blow up a target.

We can see from the picture that if we listed all the co-ordinates that are red

Pseudocode // Note that this tries to add the centre, or the x,y of the target twice
for target in targets:


Then compare two sets for overlap, and if there is overlap between all of them, then we have an answer.

Pinky Purple is a bomb, and the blue is the radius that if another bomb explodes within, it will detonate too

Note that now we have to do a check before adding the co-ordinate to the set

If it is a blank cell it is easy, just add it.

If it is a bomb, dont add it, but add all the possible co-ordinates that will set off the bomb, and if during our checks, we encounter another bomb, we need to add that list too. I would make a recursive method here

def bombLinks(candidate.x, candidate.y, bombSet):
for i in range(-radius): //0 to the -radius shouldn't be checked for bombs, since thats where we came from
candidateType = blockAtCell(candidate.x + i, candidate.y)
if(candidateType = "Blank"):
candidateType = blockAtCell(candidate.x, candidate.y + i)
if(candidateType = "Blank"):

candidateType = blockAtCell(candidate.x + j, candidate.y)
if(candidateType = "Blank"):
else if(candidateType = "Bomb"):
candidateType = blockAtCell(candidate.x, candidate.y + j)
if(candidateType = "Blank"):
else if(candidateType = "Bomb"):
return bombSet


If it is anything else, we could ignore it, or if we want it so that explosions can't pass through certain blocks, we can do some more checks here

for target in targets:
candidate.x, candidate.y = target.x + i, target.y
candidateType = blockAtCell(candidate.x, candidate.y)
if(candidateType == "Blank"):
else if(candidateType == "Bomb):

candidate.x, candidate.y = target.x, target.y + i
candidateType = blockAtCell(candidate.x, candidate.y)
if(candidateType == "Blank"):
else if(candidateType == "Bomb):