## Bomb dropping algorithm

212

118

I have an n x m matrix consisting of non-negative integers. For example:

2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4

"Dropping a bomb" decreases by one the number of the target cell and all eight of its neighbours, to a minimum of zero.

x x x
x X x
x x x

What is an algorithm that would determine the minimum number of bombs required to reduce all the cells to zero?

B Option (Due to me not being a careful reader)

Actually the first version of problem is not the one I'm seeking answer for. I didn't carefully read whole task, there's additional constraints, let us say:

What about simple problem, when sequence in row must be non-increasing:

8 7 6 6 5 is possible input sequence

7 8 5 5 2 is not possible since 7 -> 8 growing in a sequence.

Maybe finding answer for "easier" case would help in finding solution for harder one.

PS: I believe that when we have several same situations require minimum bombs to clear upper line, we choose one that use most bombs on "left side" of the row. Still any proof that might be correct?

Hint: under what circumstances is a bomb in one location just as good as a bomb in another, and maybe better? – Beta – 2013-03-08T17:56:23.010

2@beta, are you thinking greedy and drop on the biggest? Because that doesn't work. Take a 1x5 board with 2 2 4 2 2. Only such locations I can think of are the corners, where you can put a bomb in the diagonal neighbor, but that doesn't solve much. – Shahbaz – 2013-03-08T17:58:19.330

4Well I just find ot that some fields can be skipped like in example

2 3

1 5 Droping it on 2,3,1 is pointless, because dropping on them cause some subset damage which we can cause by dropping on 5. But can't find how to make it work globally (if it's correct way). Clearing 2 require use 2 bombs dropped on any of neighbour and 5 is containing other sets of damage. But then I don't know what to do later on since when you rewrite it (after decreasing), then you have two choice (there isn't one uber-set of damage). – abc – 2013-03-08T17:58:43.030

Great question. I have an idea I'm going to try before posting an answer. – Anthony Queen – 2013-03-08T18:00:07.107

23

Is this NP-hard by any chance? It looks to be a variant of the Maximum Coverage Problem.

– Mysticial – 2013-03-08T18:26:51.807

I think you could try searching for the number that has the most 1's around it. When there are 2 numbers with equal number of 1's you could look for the one with the lowest numbers or fewer 0's and repeat. – Osukaa – 2013-03-08T18:32:44.133

1@Mysticial I suspect the OP is some malicious guy trying to decide if P = NP by work of others. Shame on you for trying to deceive us, Kostek! :P – brandizzi – 2013-03-08T18:32:52.283

1Can't be NP it's use on contest (4 task -> 5hours). Can give you link to content if you understand polish language as a proof. – abc – 2013-03-08T18:34:56.017

1@Kostek It could still be NP and doable. The problem size that you've given isn't very large. It's hard enough to produce a working answer - let alone one that runs in polynomial time. – Mysticial – 2013-03-08T18:36:15.757

I wonder how fast the simplex algorithm would run on this type of problem? – Peter de Rivaz – 2013-03-08T18:44:31.067

14+1 for giving me something interesting to think about – Nick Mitchinson – 2013-03-08T18:49:39.087

Are you wanting a Coded solution, a Mathmatical expression, or just the thought process? – Anthony Queen – 2013-03-08T19:07:59.267

2"A bomb pattern is a term I dreamed up just several weeks ago. It means nothing, but you'd be surprised at how rapidly it's caught on. Why, I've got all sorts of people convinced I think it's important for the bombs to explode close together and make a neat aerial photograph. There's one colonel in Pianosa who's hardly concerned any more with whether he hits the target or not." — General Peckem, Catch 22. – Colonel Panic – 2013-03-08T19:14:05.867

3@Kostek, great problem! Please post the link. – Colonel Panic – 2013-03-08T19:29:53.707

@Shahbaz: No, I wasn't thinking of hit-the-highest (which doesn't fit my question). Yes, I was thinking of the corners, and actually it helps a lot. – Beta – 2013-03-08T19:34:47.237

3This looks a bit like Minesweeper, except that you could put bomb on a point more than once and the number only indicate the minimum number of bombs on and around a point instead of the exact number. – Lie Ryan – 2013-03-08T20:49:20.970

5perhaps you should clarify, you said the question is: what's the minimum amount of bombs required to clean the board? Does this means that it is not necessarily needed to find an actual bombing pattern, but just the minimal number of bombs? – Lie Ryan – 2013-03-08T21:25:35.447

Is it problem from some online judge? I would try to check my solution. – RiaD – 2013-03-08T21:27:30.027

@LieRyan Maybe you're seeing something that I don't, but I'm fairly sure you can't find the minimal number of bombs required without essentially having computed the actual pattern... – us2012 – 2013-03-08T21:38:31.440

3@us2012: It is fairly easy to find a lower bound and upper bound for possible number of bombs, and if they matches than that must be the exact number of bombs needed, that can be found without calculating the actual pattern. But that situation probably would only happen once in a blue moon, if ever. – Lie Ryan – 2013-03-08T21:45:25.510

@LieRyan: Well, exactly. Even if you are thinking of more sophisticated bounds than the immediately obvious ones (sum of values/9, sum of values), they are hardly ever going to coincide. Unless your bounds are much more sophisticated, in which case they might contribute to a solution and you should post an answer with details. – us2012 – 2013-03-08T21:49:01.873

@us2012: I've added an answer that describes what I'm thinking of, it's a method to find a minimum bound without finding a solution. When combined with a greedy algorithm, it can be used to prove that the solution found by the greedy, in this particular case, is indeed an optimal solution. – Lie Ryan – 2013-03-08T23:00:28.033

If from a contest, what are the limits of the inputs? – Winston Ewert – 2013-03-08T23:33:23.230

@Kostek: Would be interested in seeing the original problem. – nneonneo – 2013-03-08T23:53:27.597

Also, if your m and n and the numbers are all small enough, you can try doing full tree search, which indeed will give you optimal solution, however, it will take much time. – Sarge Borsch – 2013-03-09T09:16:40.127

2.4k views in a single day? That's something uh? – asprin – 2013-03-09T15:02:21.327

1

Are you interested in the decision problem (i.e., just knowing the minimum number of bombs required), or are you also interested in the optimization problem (i.e., knowing which bombs are required, not just how many)?

– ESultanik – 2013-03-09T18:52:23.003

@ESultanik: that's not how decision/optimization are defined. Decision is "can you do it with less than k bombs", optimization is "how few bombs does it take". Neither require you to actually specify the full solution except as proof. – nneonneo – 2013-03-09T19:59:24.010

@asprin some guy posts his homework and gets a ton of rep for it. :D – Meirion Hughes – 2013-03-09T20:46:31.587

@asprin 2.4k is nothing. I've seen over 100k in a day before. – Mysticial – 2013-03-09T21:36:18.940

For people to fiddle with: http://jsbin.com/ivaruj/2 (ignore the code please, thanks)

– mowwwalker – 2013-03-10T10:03:54.103

So many answers... Iwill try repost as many as can. If I omitted someone recomment pls.

@Anthony Queen Anything. Target is that I have to understand that - why? Why some approach works, how to deal with similar problems and so on. – abc – 2013-03-10T13:48:43.727

2

@Colonel Panic here you go https://www.deadline24.pl/assets/Uploads/dl24.elim.A.2012.pdf It's polish tho. You can try some translation but effects are not guarantee.

– abc – 2013-03-10T13:49:00.277

@RiaD I haven't found any test nor judge on the page above. But maybe just not search good enough. – abc – 2013-03-10T13:49:15.533

@Winston Ewert Board is up to 1000x1000 each field "health" as well 1000. No time limit given. – abc – 2013-03-10T13:49:42.833

@nneonneo Check 3 answers above – abc – 2013-03-10T13:50:57.247

@Sarge Borsch 4 tasks, 5 hours to do it. Limits were given 2 post above. Doubt I can fit with memory (32 bit machine I believe). – abc – 2013-03-10T13:52:26.073

@ESultanik I want to know singular integer number of bombs which are required to decrease all to 0. Number must be smallest possible. – abc – 2013-03-10T13:53:44.217

@Meirion Hughes Troll... It's just preparation to contest nothing to do with university. – abc – 2013-03-10T13:54:36.977

Also as I said suboptimal is not an option. Answer must be exact, because notes were binary 1 (correct), 0(incorrect). – abc – 2013-03-10T14:01:04.330

2I give update to task forgot about one constraint sequnce in row would not be increasing so

8 7 7 6 6 5 3 0 is valid row

4 2 3 2 1 8 7 7 is not valid row – abc – 2013-03-10T14:05:45.053

1@Kostek, please leave the problem as it was since the general case is a lot more interesting. You can add the new constraint as part (b) or bonus, or just new section. For instance, ask: "Bonus: can you find an efficient algorithm if the rows are non-decreasing?" – darksky – 2013-03-10T14:56:25.223

@darsky Ok. I will do so. – abc – 2013-03-10T14:57:15.533

@nneonneo Sure, I was being a bit lax with definitions. It depends, though; often the certificate for a combinatorial optimization problem is the variable assignment, not just the value of the objective function. It sounds like the certificate for which Kostek is interested is simpler (and perhaps amenable to a less computationally complex algorithm) than what most of the answers below assume. – ESultanik – 2013-03-10T19:59:13.763

I do not understand the constrain. Can you explain it again please? The edit, I mean. ( The B Option? ) – Koray Tugay – 2013-03-11T11:48:03.530

for the B constrain, is that sequence must be decreasing for both horizontal and vertical or only horizontal? – Lie Ryan – 2013-03-11T15:57:09.720

@Kostek, I recommend removing the B option, its easy to solve as nneonneo showed and it is a distraction from the original question which generated a huge amount of interest and responses. I think you should revert the question to its original form and let this good conversation continue, even if it is not the conversation you wanted to start :). – Ben Haley – 2013-03-12T16:23:05.573

Any chance you work for Roomba and are creating a bomb-dropping drone for the air force? – Brian Webster – 2013-03-13T21:09:34.860

If a bomb decreases only horizontal and vertical neighbors and all weights are allowed (version A), then the problem is NP-hard, as proven in web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdf (Theorem 5.1), as you can easily convert their grid graphs to a matrix using 0 and 1 entries. Dropping a bomb is then equivalent to adding that vertex to the dominating set. I'm pretty sure you can prove the case with diagonal neighbors NP-hard in the same way with a few modifications. – Alex ten Brink – 2013-03-16T16:28:15.043

38

There is a way to reduce this to a simple sub-problem.

There are 2 parts to the explanation, the algorithm, and the reason the algorithm provides an optimal solution. The first won't make sense without the second, so I'll start with the why.

If you think of bombing the rectangle (assume a big rectangle - no edge cases yet) you can see that the only way to reduce the hollow rectangle of squares on the perimeter to 0 is to bomb either the perimeter or to bomb the hollow rectangle of squares just inside the perimeter. I'll call the perimeter layer 1, and the rectangle inside it layer 2.

An important insight is that there is no point bombing layer 1, because the "blast radius" you get from doing so is always contained within the blast radius of another square from layer 2. You should be able to easily convince yourself of this.

So, we can reduce the problem to finding an optimal way to bomb away the perimeter, then we can repeat that until all squares are 0.

But of course, that won't always find an optimal solution if it's possible to bomb away the perimeter in a less than optimal fashion, but by using X extra bombs make the problem of reducing the inner layer simpler by >X bombs. So, if we call the permiter layer one, if we place an extra X bombs somewhere in layer 2 (just inside layer 1), can we reduce the effort of later bombing away layer 2 by more than X? In other words, we have to prove we can be greedy in reducing the outer perimeter.

But, we do know we can be greedy. Because no bomb in layer 2 can ever be more efficient in reducing layer 2 to 0 than a strategically placed bomb in layer 3. And for the same reason as before - there is always a bomb we can place in layer 3 that will affect every square of layer 2 that a bomb placed in layer 2 can. So, it can never harm us to be greedy (in this sense of greedy).

So, all we have to do is find the optimal way to reduce the permiter to 0 by bombing the next inner layer.

We are never hurt by first bombing the corner to 0, because only the corner of the inner layer can reach it, so we really have no choice (and, any bomb on the perimeter that can reach the corner has a blast radius contained in the blast radius from the corner of the inner layer).

Once we have done so, the squares on the perimeter adjacent to the 0 corner can only be reached by 2 squares from the inner layer:

0       A       B

C       X       Y

D       Z

At this point the perimeter is effectively a closed 1 dimensional loop, because any bomb will reduce 3 adjacent squares. Except for some weirdness near the corners - X can "hit" A,B,C,and D.

Now we can't use any blast radius tricks - the situation of each square is symmetric, except for the weird corners, and even there no blast radius is a subset of another. Note that if this were a line (as Colonel Panic discusses) instead of a closed loop the solution is trivial. The end points must be reduced to 0, and it never harms you to bomb the points adjacent to the end points, again because the blast radius is a superset. Once you have made your endpoint 0, you still have a new endpoint, so repeat (until the line is all 0).

So, if we can optimally reduce a single square in the layer to 0 we have an algorithm (because we have cut the loop and now have a straight line with endpoints). I believe bombing adjacent to the square with the lowest value (giving you 2 options) such that the highest value within 2 squares of that lowest value is the minimum possible (you may have to split your bombing to manage this) will be optimal but I don't (yet?) have a proof.

+1 - I was going to write something similar. I think you've got it! – Rex Kerr – 2013-03-09T11:37:12.183

there is no point bombing layer 1, because the "blast radius" you get from doing so is always contained within the blast radius of another square from layer 2 - You forget the case in which only layer 1 has non-zero values. In this case bombing layer 2 will only reduce the sum by 1 while bombing layer 1 will reduce it by up to 3. – beaker – 2013-03-09T15:15:07.290

5@beaker, please read the problem carefully. Bombing a square reduces all eight of its neighbors, so his assumption there is actually correct. – darksky – 2013-03-09T15:28:25.000

"the only way to reduce the hollow rectangle of squares on the perimeter [...]" Sorry, I may be a bit slow at understanding but could you define what is the hollow rectangle and the perimeter? – brandizzi – 2013-03-09T17:06:58.880

20But, we do know we can be greedy... - I'm not buying this. Consider 1 1 2 1 1 2 on the perimeter. The minimum number of bombs is 4, but there are three distinct solutions. Each solution has a different impact on the next layer. As long as there are multiple minimal solutions for a perimeter, you can't completely isolate the perimeter without consideration of the inner layers. I really don't think this problem can be solved without backtracking. – user1354557 – 2013-03-09T20:00:19.493

4I was thinking about this solution, but it dosent look that simple. It is true, that you can drop bomb at layer2 in order to clean, layer1, but if there are multiple solutions, they effect solutions for higher layers. – Luka Rahne – 2013-03-10T08:32:50.147

@user1354557 - You're right. I had planned to clean that up (it was a little hand-wavy) and that's the flaw. In my defense I have a lot of progress - working outside in, and a way to get one of the locally optimal solutions. I'm currently waiting to edit until I have a bit more progress though. Oh, you may well need backtracking, but the algorithm you use to do it is important - trying all combinations of bombs or something is terrible. – psr – 2013-03-11T17:46:47.273

12

@psr: This does not work. The bombing method that is optimal for the outer layer may not be globally optimal. Example: 0011100 0100010 0000000 0000000 1110111. The optimal way to bomb the first layer is to bomb in the middle of the second row, taking a total of three bombs to kill the outer layer. But then you need two bombs to take care of the next layer. Optimal requires only four bombs total: two for the first two rows and two for the last row.

– nneonneo – 2013-03-12T18:02:37.690

@nneonneo - Yep. +1 on your comment. I'll have to edit my answer. – psr – 2013-03-12T18:12:34.223

@user1354557 You are right! This problem is a typical use case for back tracking. The algorithm to use is quite simple, perhaps one has already described it, have to take a look. – Mare Infinitus – 2013-03-12T20:42:18.593

25

Pólya says "If you can't solve a problem, then there is an easier problem you can solve: find it."

The obvious simpler problem is the 1-dimensional problem (when the grid is a single row). Let's start with the simplest algorithm - greedily bombing the biggest target. When does this go wrong?

Given 1 1 1, the greedy algorithm is indifferent to which cell it bombs first. Of course, the centre cell is better - it zeros all three cells at once. This suggests a new algorithm A, "bomb to minimise the sum remaining". When does this algorithm go wrong?

Given 1 1 2 1 1, algorithm A is indifferent between bombing the 2nd, 3rd or 4th cells. But bombing the 2nd cell to leave 0 0 1 1 1 is better than bombing the 3rd cell to leave 1 0 1 0 1. How to fix that? The problem with bombing the 3rd cell is that it leaves us work to the left and work to the right which must be done separately.

How about "bomb to minimise the sum remaining, but maximise the minimum to the left (of where we bombed) plus the minimum to the right". Call this algorithm B. When does this algorithm go wrong?

Edit: After reading the comments, I agree a much more interesting problem would be the one dimensional problem changed so that the ends join up. Would love to see any progress on that.

40I'm not sure why this answer is getting so many upvotes - the 1D case is almost trivial, simply always bomb the element to the right of the first positive element. This works because there is always exactly one optimal way to bomb any element which contains only 0's to its left. This can be extended to 2D to optimally remove the corner squares, but I don't see an obvious way to extend it beyond that...? – BlueRaja - Danny Pflughoeft – 2013-03-08T22:28:42.633

3@BlueRaja, I upvoted because it clearly illustrated that the greedy approach discussed in the other answers was insufficient (at least, it needed to be supplemented with an additional criteria). Some choices of target, even if they result in an equal reduction in the total number, may leave things more spread out than others. I think this is a useful insight for the 2D problem. – Tim Goodman – 2013-03-08T22:36:58.623

I also think it suggests more than just that you should remove the corner squares in the 2D case. It suggests that, overall reduction being equal, it's better to bomb towards the edge of a region of non-zero numbers than it is to bomb in the middle (which would leave an unbombed ring on the outside that you'll have to take care of with multiple bombings later). – Tim Goodman – 2013-03-08T22:38:25.470

3And in general "If you're stuck on the 2D case, try the 1D case first" is good advice. – Tim Goodman – 2013-03-08T22:39:21.787

Also, consider the example of a 1D case which wraps around (the two ends are considered neighbors). There your "always bomb 1 to the right of the first non-zero one" is less optimal than the strategy Colonel Panic is describing. That may be a better analogue to the 2D case, where every space has multiple neighbors. – Tim Goodman – 2013-03-08T22:50:58.670

21@Tim: "'try the 1D case first' is good advice" Yes it is, which would make it an excellent comment; but it's not an answer... – BlueRaja - Danny Pflughoeft – 2013-03-08T22:51:08.690

Well, I took it as a "pointing you in a good direction" type answer... I haven't seen any answer posted yet that actually tells how to do it. – Tim Goodman – 2013-03-08T22:52:06.297

3I do think you have a good point though that the 1D case may be a bit misleading here because it has a simple solution that doesn't readily extend to higher dimensions. I think the 1D case with periodic boundary conditions (the wrap around case) may be better. – Tim Goodman – 2013-03-08T22:55:05.777

1I think solving the outer ring rather than a 1-D case might be a better way to break into a smaller problem? I gave it a shot in my answer. – psr – 2013-03-09T00:32:16.737

Danny, Tim, you're right - the 2d problem is much more subtle. The 1d wrap around problem must be more interesting too, because it can't be attacked from the edge. – Colonel Panic – 2013-03-09T00:49:32.097

12

I had to stop at only a partial solution since I was out of time, but hopefully even this partial solution provides some insights on one potential approach to solving this problem.

When faced with a hard problem, I like to come up with simpler problems to develop an intuition about the problem space. Here, the first step I took was to reduce this 2-D problem into a 1-D problem. Consider a line:

0 4 2 1 3 0 1

Somehow or another, you know you will need to bomb at or around the 4 spot 4 times to get it down to 0. Since left of the spot is a lower number, there is no benefit to bombing the 0 or the 4 over bombing the 2. In fact, I believe (but lack a rigorous proof) that bombing the 2 until the 4 spot goes down to 0 is at least as good as any other strategy to get that 4 down to 0. One can proceed down the line left to right in a strategy like this:

index = 1
while index < line_length
while number_at_index(index - 1) > 0
bomb(index)
end
index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
bomb(index - 1)
end

A couple sample bombing orders:

0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0

4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0

The idea of starting with a number that needs to go down some way or another is an appealing one because it suddenly becomes attainable to find a solution that as some claim to being at least as good as all other solutions.

The next step up in complexity where this search of at least as good is still feasible is on the edge of the board. It is clear to me that there is never any strict benefit to bomb the outer edge; you're better off bombing the spot one in and getting three other spaces for free. Given this, we can say that bombing the ring one inside of the edge is at least as good as bombing the edge. Moreover, we can combine this with the intuition that bombing the right one inside of the edge is actually the only way to get edge spaces down to 0. Even more, it is trivially simple to figure out the optimal strategy (in that it is at least as good as any other strategy) to get corner numbers down to 0. We put this all together and can get much closer to a solution in the 2-D space.

Given the observation about corner pieces, we can say for sure that we know the optimal strategy to go from any starting board to a board with zeros on all corners. This is an example of such a board (I borrowed the numbers from the two linear boards above). I've labelled some spaces differently, and I'll explain why.

0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

One will notice at the top row really closely resembles the linear example we saw earlier. Recalling our earlier observation that the optimal way to get the top row all down to 0 is to bomb the second row (the x row). There is no way to clear the top row by bombing any of the y rows and no additional benefit to bombing the top row over bombing the corresponding space on the x row.

We could apply the linear strategy from above (bombing the corresponding spaces on the x row), concerning ourselves only with the top row and nothing else. It would go something like this:

0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

The flaw in this approach becomes very obvious in the final two bombings. It is clear, given that the only bomb sites that reduce the 4 figure in the first column in the second row are the first x and the y. The final two bombings are clearly inferior to just bombing the first x, which would have done the exact same (with regard to the first spot in the top row, which we have no other way of clearing). Since we have demonstrated that our current strategy is suboptimal, a modification in strategy is clearly needed.

At this point, I can take a step back down in complexity and focus just one one corner. Let's consider this one:

0 4 2 1
4 x y a
2 z . .
1 b . .

It is clear the only way to get the spaces with 4 down to zero are to bomb some combination of x, y, and z. With some acrobatics in my mind, I'm fairly sure the optimal solution is to bomb x three times and then a then b. Now it's a matter of figuring out how I reached that solution and if it reveals any intuition we can use to even solve this local problem. I notice that there's no bombing of y and z spaces. Attempting to find a corner where bombing those spaces makes sense yields a corner that looks like this:

0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .

For this one, it is clear to me that the optimal solution is to bomb y 5 times and z 5 times. Let's go one step further.

0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .

Here, it feels similarly intuitive that the optimal solution is to bomb a and b 6 times and then x 4 times.

Now it becomes a game of how to turn those intuitions into principles we can build on.

Hopefully to be continued!

10

For updated question a simple greedy algorithm gives optimal result.

Drop A[0,0] bombs to cell A[1,1], then drop A[1,0] bombs to cell A[2,1], and continue this process downwards. To clean bottom left corner, drop max(A[N-1,0], A[N-2,0], A[N-3,0]) bombs to the cell A[N-2,1]. This will completely clean up first 3 columns.

With the same approach clean columns 3,4,5, then columns 6,7,8, etc.

Unfortunately this does not help finding solution for the original problem.

"Larger" problem (without "nonicreasing" constraint) may be proven to be NP-hard. Here is sketch of a proof.

Suppose we have a planar graph of degree up to 3. Let's find minimum vertex cover for this graph. According to Wikipedia article this problem is NP-hard for planar graphs of degree up to 3. This could be proven by reduction from Planar 3SAT. And hardness of Planar 3SAT - by reduction from 3SAT. Both these proofs are presented in recent lectures in "Algorithmic Lower Bounds" by prof. Erik Demaine (lectures 7 and 9).

If we split some edges of the original graph (left graph on the diagram), each one with even number of additional nodes, the resulting graph (right graph on the diagram) should have exactly the same minimum vertex cover for original vertices. Such transformation allows to align graph vertices to arbitrary positions on the grid.

If we place graph vertices only to even rows and columns (in such a way that no two edges incident to one vertex form an acute angle), insert "ones" wherever there is an edge, and insert "zeros" to other grid positions, we could use any solution for the original problem to find minimum vertex cover.

Where does that graph from the left come from? Sorry, I don't quite understand your explanation! – ryyst – 2013-03-12T16:13:15.790

1@ryyst: that graph from the left is just an example of a planar graph. It is used to demonstrate how to transform any planar graph of degree up to 4 to the grid-aligned graph and then to the n*m matrix. A "bomb dropping" algorithm applied to this matrix will solve vertex cover problem for this transformed graph and therefore for that "left" graph. – Evgeny Kluev – 2013-03-12T16:31:26.570

Ah, I get it now, and I believe your transformation is correct. Thanks! – ryyst – 2013-03-13T13:22:47.827

@EvgenyKluev, I think now you need to prove that vertex cover is still NP-hard for "planar graphs of degree up to 4". – Shahbaz – 2013-03-18T13:22:18.343

@Shahbaz: I'm afraid this proof would be too lengthy. So I added link to the proof. – Evgeny Kluev – 2014-10-09T18:15:48.120

9

This would be a greedy approach:

1. Calculate a "score" matrix of order n X m, where score[i][j] is the total deduction of points in the matrix if position (i,j) is bombed. (Max score of a point is 9 and min score is 0)

2. Moving row wise, find and pick the first position with highest score (say (i,j)).

3. Bomb (i,j). Increase bomb count.

4. If all elements of the original matrix are not zero, then goto 1.

I have my doubts that this is the optimal solution though.

Edit:

The Greedy approach I posted above, while it works, most probably doesn't give us the optimal solution. So I figured should add some elements of DP to it.

I think we can agree that at any point of time, one of the positions with the highest "score" (score[i][j] = total deduction of points if (i,j) is bombed) must be targeted. Starting with this assumption, here's the new approach:

NumOfBombs(M): (returns the minimum number of bombings required)

1. Given a Matrix M of order n X m. If all elements of M are zero, then return 0.

2. Calculate the "score" matrix M.

Let the k distinct positions P1,P2,...Pk (1 <= k <= n*m), be the positions in M with the highest scores.

3. return (1 + min( NumOfBombs(M1), NumOfBombs(M2), ..., NumOfBombs(Mk) ) )

where M1,M2,...,Mk are the resulting matrices if we bomb positions P1, P2, ..., Pk respectively.

Also, if we want the order of positions to nuke in addition to this, we would have to keep track of the results of "min".

3I wonder if setting score to be the sum of current values would produce better results. That would essentially flatten the ground more efficiently. – Eugene – 2013-03-08T18:43:18.020

@Eugene: Very interesting point. I can't think of a reason why your way shouldn't produce better results... – SidR – 2013-03-08T18:59:05.837

@Eugene: Perhaps the sum of current values in the vicinity could be used for "priority" measure? Nuke the node with highest score and highest priority.. – SidR – 2013-03-08T19:03:29.937

Just read this answer, I think it's similar to the second answer I just posted (maybe spelled out a little more in my answer). I think it would be optimal if there was always a single space with the max score, because you'd be guaranteed that every bombing has the greatest affect possible. The order of bombings doesn't matter, so going with the best one at each step should be optimal. But because there could be ties for "best", maybe for an optimal solution you'd need to back-track and try both when there's a tie. – Tim Goodman – 2013-03-08T20:46:13.963

1@Eugene, maybe I'm not following you. What's the difference between biggest reduction, and smallest sum of all remaining values? The sum of remaining values (after bombing) is just the current total value minus the reduction from bombing that space, so aren't these equivalent? – Tim Goodman – 2013-03-08T20:49:44.443

@Tim Goodman, the difference is that square with all 1s will have the same "reduction" value as square with all 9s. But we obviously want to hit the 9s, so "sum of remaining" is a slightly better heuristics (still not a perfect one though). In other words -- you want to leave the field as smooth as possible. – Eugene – 2013-03-08T21:08:20.847

What does a greedy solutıon mean? – Koray Tugay – 2013-03-10T14:36:30.780

– SidR – 2013-03-10T18:39:07.983

@SidR Thank you, I will take a look. – Koray Tugay – 2013-03-10T18:43:14.870

What's a counter example that shows this greedy algorithm doesn't work? – Jason L – 2014-01-31T05:19:36.563

9

You can represent this problem as integer programming problem. (this is just one of possible solutions to approach this problem)

Having points:

a b c d
e f g h
i j k l
m n o p

one can write 16 equations where for point f for example holds

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki

minimaised over sum of all indexes and integer solution.

Solution is of course sum of this indexes.

This can be further simplified by setting all xi on boundaries 0, so you end up having 4+1 equation in this example.

Problem is that there is no trivial algorhitm for solving such problems. tI am not expert on this, but solving this problem as linear programming is NP hard.

8All problems in NP can be formulated as integer programming problems, so this is not very helpful, unless we already know that the problem is NP-Complete – BlueRaja - Danny Pflughoeft – 2013-03-08T19:26:28.847

1I agree. It is also not necessary to know exact moves that has to be done in order to know what solution is. – Luka Rahne – 2013-03-08T19:37:01.793

1When you set the boundary to 0, the number of inequalities is still 16. – darksky – 2013-03-16T01:41:25.083

Yes you are right. – Luka Rahne – 2013-03-16T02:27:20.713

9

This is a partial answer, I'm trying to find a lower bound and upper bound that could be the possible number of bombs.

In 3x3 and smaller board, the solution is trivially always the largest numbered cell.

In boards larger than 4x4, the first obvious lower bound is the sum of the corners:

*2* 3  7 *1*
1  5  6  2
2  1  3  2
*6* 9  6 *4*

however you arrange the bomb, it is impossible to clear this 4x4 board with less than 2+1+6+4=13 bombs.

It has been mentioned in other answers that placing the bomb on the second-to-corner to eliminate the corner is never worse than placing the bomb on the corner itself, so given the board:

*2* 3  4  7 *1*
1  5  2  6  2
4  3  4  2  1
2  1  2  4  1
3  1  3  4  1
2  1  4  3  2
*6* 9  1  6 *4*

We can zero the corners out by placing bombs on the second-to-corner to give a new board:

0  1  1  6  0
0  3  0  5  1
2  1  1  1  0
2  1  2  4  1
0  0  0  0  0
0  0  0  0  0
0  3  0  2  0

So far so good. We need 13 bombs to clear the corners.

Now observe the number 6, 4, 3, and 2 marked below:

0  1  1 *6* 0
0  3  0  5  1
2  1  1  1  0
*2* 1  2 *4* 1
0  0  0  0  0
0  0  0  0  0
0 *3* 0  2  0

There is no way to bomb any two of those cells using a single bomb, so the minimum bomb has increased by 6+4+3+2, so adding to the number of bombs we used to clear the corners, we get that the minimum number of bombs required for this map has become 28 bombs. It is impossible to clear this map with less than 28 bombs, this is the lower bound for this map.

You can use greedy algorithm to establish an upper bound. Other answers have shown that a greedy algorithm produces a solution that uses 28 bombs. Since we've proven earlier that no optimal solution can have less than 28 bombs, therefore 28 bombs is indeed an optimal solution.

When greedy and the method to find the minimal bound I've mentioned above does not converge though, I guess you do have to go back to checking all combinations.

The algorithm for finding the lower bound is the following:

1. Pick an element with the highest number, name it P.
2. Mark all cells two steps away from P and P itself as unpickable.
3. Add P to the minimums list.
4. Repeat to step 1 until all cells are unpickable.
5. Sum the minimums list to get the lower bound.

8

Your new problem, with the nondecreasing values across rows, is quite easy to solve.

Observe that the left column contains the highest numbers. Therefore, any optimal solution must first reduce this column to zero. Thus, we can perform a 1-D bombing run over this column, reducing every element in it to zero. We let the bombs fall on the second column so they do maximum damage. There are many posts here dealing with the 1D case, I think, so I feel safe in skipping that case. (If you want me to describe it, I can.). Because of the decreasing property, the three leftmost columns will all be reduced to zero. But, we will provably use a minimum number of bombs here because the left column must be zeroed.

Now, once the left column is zeroed, we just trim off the three leftmost columns that are now zeroed and repeat with the now-reduced matrix. This must give us an optimal solution since at each stage we use a provably minimum number of bombs.

Yep, that's it. – user1354557 – 2013-03-10T21:17:01.820

I get it. I thought of similar idea. :S Next time I will read more carefully. But thanks to that many people have 'nice' problem to solve'. – abc – 2013-03-10T22:44:28.480

3

This greedy solution seems to be correct:

As pointed in comments, it'll fail in 2D. But maybe you may improve it.

For 1D:
If there is at least 2 numbers you don't need to shoot to the leftmost one because shooting to the second is not worse. So shoot to the second, while first isn't 0, because you have to do it. Move to the next cell. Don't forget about last cell.

C++ code:

void bombs(vector<int>& v, int i, int n){
ans += n;
v[i] -= n;
if(i > 0)
v[i - 1] -= n;
if(i + 1< v.size())
v[i + 1] -= n;
}

void solve(vector<int> v){
int n = v.size();
for(int i = 0; i < n;++i){
if(i != n - 1){
bombs(v, i + 1, v[i]);
}
else
bombs(v, i, v[i])
}
}

So for 2D:
Again: you don't need to shoot in the first row (if there is the second). So shoot to the second one. Solve 1D task for first row. (because you need to make it null). Go down. Don't forget last row.

5A counterexample: "0110","1110","1110" . You only need 1 shot, but I believe Your algorithm would use 2. – maniek – 2013-03-08T22:26:12.620

1@maniek, nice catch – RiaD – 2013-03-08T22:28:19.843

3

There is no need to transform the problem to linear sub-problems.

Instead use a simple greedy heuristic, which is to bomb the corners, starting with the largest one.

In the given example there are four corners, { 2, 1, 6, 4 }. For each corner there is no better move than to bomb the cell diagonal to the corner, so we know for a fact our first 2+1+6+4 = 13 bombings must be in these diagonal cells. After doing the bombing we are left with a new matrix:

2 3 4 7 1      0 1 1 6 0      0 1 1 6 0     1 1 6 0     0 0 5     0 0 0
1 5 2 6 2      0 3 0 5 1      0 3 0 5 1  => 1 0 4 0  => 0 0 3  => 0 0 0
4 3 4 2 1      2 1 1 1 0      2 1 1 1 0     0 0 0 0     0 0 0     0 0 3
2 1 2 4 1  =>  2 1 2 4 1  =>  2 1 2 4 1     0 0 3 0     0 0 3
3 1 3 4 1      0 0 0 0 0      0 0 0 0 0
2 1 4 3 2      0 0 0 0 0      0 0 0 0 0
6 9 1 6 4      0 3 0 2 0      0 0 0 0 0

After the first 13 bombings we use the heuristic to eliminate 3 0 2 via three bombings. Now, we have 2 new corners, { 2, 1 } in the 4th row. We bomb those, another 3 bombings. We have reduced the matrix to 4 x 4 now. There is one corner, the upper left. We bomb that. Now we have 2 corners left, { 5, 3 }. Since 5 is the largest corner we bomb that first, 5 bombings, then finally bomb the 3 in the other corner. The total is 13+3+3+1+5+3 = 28.

1I don't understand what do you do in general case after bombing corners – RiaD – 2013-03-08T22:38:27.397

Bombing the corner is never more effective than bombing diagonally inward from the corner. – psr – 2013-03-08T23:08:55.813

1psr you misunderstand my post, I AM bombing diagonally from the corner, reread the post – Tyler Durden – 2013-03-08T23:10:24.233

11@TylerDurden: this only works because the matrix is small. On bigger matrices, after bombing the corner, you generally would not be able to cut the edges anymore. – Lie Ryan – 2013-03-08T23:39:40.870

3

This does a breadth-search for the shortest path (a series of bombings) through this "maze" of positions. No, I cannot prove that there is no faster algorithm, sorry.

#!/usr/bin/env python

M = ((1,2,3,4),
(2,3,4,5),
(5,2,7,4),
(2,3,5,8))

def eachPossibleMove(m):
for y in range(1, len(m)-1):
for x in range(1, len(m[0])-1):
if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
m[y][x-1]   == m[y][x]   == m[y][x+1] ==
m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
continue
yield x, y

def bomb(m, (mx, my)):
return tuple(tuple(max(0, m[y][x]-1)
if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
else m[y][x]
for x in range(len(m[y])))
for y in range(len(m)))

def findFirstSolution(m, path=[]):
#  print path
#  print m
if sum(map(sum, m)) == 0:  # empty?
return path
for move in eachPossibleMove(m):
return findFirstSolution(bomb(m, move), path + [ move ])

def findShortestSolution(m):
black = {}
nextWhite = { m: [] }
while nextWhite:
white = nextWhite
nextWhite = {}
for position, path in white.iteritems():
for move in eachPossibleMove(position):
nextPosition = bomb(position, move)
nextPath = path + [ move ]
if sum(map(sum, nextPosition)) == 0:  # empty?
return nextPath
if nextPosition in black or nextPosition in white:
continue  # ignore, found that one before
nextWhite[nextPosition] = nextPath

def main(argv):
if argv[1] == 'first':
print findFirstSolution(M)
elif argv[1] == 'shortest':
print findShortestSolution(M)
else:
raise NotImplementedError(argv[1])

if __name__ == '__main__':
import sys
sys.exit(main(sys.argv))

1This algorithm will find the fewest number of moves, but it could take a very long time. Have you run this on the given data set? That would give a baseline for other algorithms to compare against. – Ryan Amos – 2013-03-09T05:41:11.997

1A subset of 5x4 of the given matrix was solved in about 2 seconds, 5x5 already took over 2 minutes. I didn't try more yet ;-) Yes, this algorithm isn't optimized for anything but the original task: Find the shortest solution. – Alfe – 2013-03-09T11:27:38.760

2Such is the beauty of exponential complexity. – Ryan Amos – 2013-03-09T18:07:36.380

3

It seems that a linear programming approach can be very helpful here.

Let Pm x n be the matrix with the values of the positions:

Now let define a bomb matrix B(x, y)m x n,with 1 ≤ x ≤ m, 1 ≤ y ≤ n as below

in such a way that

For example:

So we are looking to a matrix Bm x n = [bij] that

1. Can be defined as a sum of bomb matrices:

(qij would be then the quantity of bombs we would drop in position pij)

2. pij - bij ≤ 0 (to be more succint, let us say it as P - B ≤ 0)

Also, B should minimize the sum .

We can also write B as the ugly matrix ahead:

and since P - B ≤ 0 (which means P ≤ B) we have the following pretty linear inequality system below:

Being qmn x 1 defined as

pmn x 1 defined as

We can say we have a system The system below represented as product of matrices http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D being Smn x mn the matrix to be reversed to solve the system. I did not expand it myself but I believe it should be easy to do it in code.

Now, we have a minimum problem which can be stated as

I believe it is something easy, almost trivial to be solved with something like the simplex algorithm (there is this rather cool doc about it). However, I do know almost no linear programming (I will take a course about it on Coursera but it is just in the future...), I had some headaches trying to understand it and I have a huge freelance job to finish so I just give up here. It can be that I did something wrong at some point, or that it can't go any further, but I believe this path can eventually lead to the solution. Anyway, I am anxious for your feedback.

(Special thanks for this amazing site to create pictures from LaTeX expressions)

Are you sure your inequalities are not reversed? That is Sq >= P? that is, the total number of times a square is bombed is greater than or equal to the given matrix. – darksky – 2013-03-09T20:59:55.120

@darksky you are right. Corrected! – brandizzi – 2013-03-10T12:55:04.047

1

When the variables of a linear program are constrained to integers, we call that "integer linear programming" (IP). Unlike the continuous case, IP is NP-Complete. Unfortunately, the simplex algorithm does not help, unless an approximation is acceptable. And IP has already been mentioned in another answer.

– BlueRaja - Danny Pflughoeft – 2013-03-11T02:38:37.533

@BlueRaja-DannyPflughoeft correct. "Despite the many crucial applications of this problem, and intense interest by researchers, no efficient algorithm is known for it. see page 254. Integer linear programming is a very hard computational problem. Our only hope to be efficient is to exploit intrinsic properties about your matrix S. It's not that arbitrary after all.

– darksky – 2013-03-16T03:44:28.730

3

## Mathematica Integer Linear Programming using branch-and-bound

As it has already been mentioned, this problem can be solved using integer linear programming (which is NP-Hard). Mathematica already has ILP built in. "To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method." [see Constrained Optimization Tutorial in Mathematica.. ]

I've written the following code that utilizes ILP libraries of Mathematica. It is surprisingly fast.

solveMatrixBombProblem[problem_, r_, c_] :=
Module[{},
bombEffect[x_, y_, m_, n_] :=
Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y ||
j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
bombMatrix[m_, n_] :=
Transpose[
Table[Table[
Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m,
n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0,
m*n - 1}], {i, 0, m*n - 1}]];
X := x /@ Range[c*r];
sol = Minimize[{Total[X],
And @@ Thread[bombMatrix[r, c].X >= problem] &&
And @@ Thread[X >= 0] && Total[X] <= 10^100 &&
Element[X, Integers]}, X];
Print["Minimum required bombs = ", sol[[1]]];
Print["A possible solution = ",
MatrixForm[
Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0,
c - 1}]]];]

For the example provided in the problem:

solveMatrixBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5]

Outputs

## For anyone reading this with a greedy algorithm

Try your code on the following 10x10 problem:

5   20  7   1   9   8   19  16  11  3
17  8   15  17  12  4   5   16  8   18
4   19  12  11  9   7   4   15  14  6
17  20  4   9   19  8   17  2   10  8
3   9   10  13  8   9   12  12  6   18
16  16  2   10  7   12  17  11  4   15
11  1   15  1   5   11  3   12  8   3
7   11  16  19  17  11  20  2   5   19
5   18  2   17  7   14  19  11  1   6
13  20  8   4   15  10  19  5   11  12

Here it is comma-seperated:

5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12

For this problem, my solution contains 208 bombs. Here's a possible solution (I was able to solve this in about 12 seconds).

As a way to test the results Mathematica is producing, see if your greedy algorithm can do any better.

I was able to do it in 219 with this answer: http://stackoverflow.com/questions/15300149/bomb-dropping-algorithm/15301559#15301559

– Anthony Queen – 2013-03-18T17:34:22.197

2

Here's another idea:

Let's start by assigning a weight to each space on the board for how many numbers would be reduced by dropping a bomb there. So if the space has a non-zero number, it gets a point, and if any space adjacent to it has a non-zero number, it gets an additional point. So if there is a 1000-by-1000 grid, we have a weight assigned to each of the 1 million spaces.

Then sort the list of spaces by weight, and bomb the one with the highest weight. This is getting the most bang for our buck, so to speak.

After that, update the weight of every space whose weight is affected by the bomb. This will be the space you bombed, and any space immediately adjacent to it, and any space immediately adjacent to those. In other words, any space which could have had its value reduced to zero by the bombing, or the value of a neighboring space reduced to zero.

Then, re-sort the list spaces by weight. Since only a small subset of spaces had their weight changed by the bombing, you won't need to resort the whole list, just move those ones around in the list.

Bomb the new highest weight space, and repeat the procedure.

This guarantees that every bombing reduces as many spaces as possible (basically, it hits as few spaces which are already zero as possible), so it would be optimal, except that their can be ties in weights. So you may need to do some back tracking when there is a tie for the top weight. Only a tie for the top weight matters, though, not other ties, so hopefully it's not too much back-tracking.

Edit: Mysticial's counterexample below demonstrates that in fact this isn't guaranteed to be optimal, regardless of ties in weights. In some cases reducing the weight as much as possible in a given step actually leaves the remaining bombs too spread out to achieve as high a cummulative reduction after the second step as you could have with a slightly less greedy choice in the first step. I was somewhat mislead by the notion that the results are insensitive to the order of bombings. They are insensitive to the order in that you could take any series of bombings and replay them from the start in a different order and end up with the same resulting board. But it doesn't follow from that that you can consider each bombing independently. Or, at least, each bombing must be considered in a way that takes into account how well it sets up the board for subsequent bombings.

it will still be a lot of backtracking, at the beginning since the fields has very little zero, the weights of most cells will be all nines. – Lie Ryan – 2013-03-08T21:04:30.473

Yeah, that's a good point, since there isn't a big range in the possible weights (only 0 to 9). – Tim Goodman – 2013-03-08T21:07:32.487

I'm still not 100% sure how necessary the backtracking is... it might be instructive to construct a grid where one choice of greedy bombing is inferior to another choice of greedy bombing. Maybe there's some consistent way to anticipate which is better. – Tim Goodman – 2013-03-08T21:09:34.700

Actually, I see Colonel Panic has done this in his answer. The reason one greedy choice can be better than another is that one leaves the remaining numbers more spread out. – Tim Goodman – 2013-03-08T21:13:20.047

31010101,0010100 might be a counterexample that proves this approach to be non-optimal. This approach requires 3. It can be done in 2. – Mysticial – 2013-03-09T19:01:12.760

@Mysticial: Great example. So I guess reducing the total as much as possible on a given bomb drop can actually be less important than not leaving the remaining numbers too spread out. I wonder if it's always better to start near the edge of a contiguous region and bomb in from there (where we count it as contiguous if it's all non-zero or has zeroes which are adjacent to non-zeros). – Tim Goodman – 2013-03-11T00:16:53.387

2

I believe that to minimize the amount of bombs you simply need maximize the amount of damage.. for that to happen need to check the area that has the strongest force.. so you first analyze the field with a 3x3 kernel and check where the sum is stronger.. and bomb there.. and do until the field is flat.. for this filed the answer is 28

var oMatrix = [
[2,3,4,7,1],
[1,5,2,6,2],
[4,3,4,2,1],
[2,1,2,4,1],
[3,1,3,4,1],
[2,1,4,3,2],
[6,9,1,6,4]
]

var nBombs = 0;
do
{
var bSpacesLeftToBomb = false;
var nHigh = 0;
var nCellX = 0;
var nCellY = 0;
for(var y = 1 ; y<oMatrix.length-1;y++)
for(var x = 1 ; x<oMatrix[y].length-1;x++)
{
var nValue = 0;
for(var yy = y-1;yy<=y+1;yy++)
for(var xx = x-1;xx<=x+1;xx++)
nValue += oMatrix[yy][xx];

if(nValue>nHigh)
{
nHigh = nValue;
nCellX = x;
nCellY = y;
}

}
if(nHigh>0)
{
nBombs++;

for(var yy = nCellY-1;yy<=nCellY+1;yy++)
{
for(var xx = nCellX-1;xx<=nCellX+1;xx++)
{
if(oMatrix[yy][xx]<=0)
continue;
oMatrix[yy][xx] = --oMatrix[yy][xx];
}
}
bSpacesLeftToBomb = true;
}
}
while(bSpacesLeftToBomb);

This is the same algorithm as a few of the other answers, but much later. – psr – 2013-03-09T02:02:50.303

@psr Not only that. It is not optimal. – Mysticial – 2013-03-09T18:53:27.450

I posted it, because, while this algorithm was proposed, I found no post of code or "prof of concept". so I thought it could help the discution.. but.. btw @Mysticial do you have prof that there is a more optimal way? – CaldasGSM – 2013-03-10T22:01:16.123

@CaldasGSM No worries, the original problem (without the sequencing) is hard. There's only one answer so far that solves it optimally, but it runs in exponential time.

– Mysticial – 2013-03-12T16:43:21.103

2

To minimize the number of bombs, we have to maximize effect of every bomb. To achive this, on every step we have to select the best target. For each point summing it and it's eight neighbours - could be used as an efficiency quantity of bombing this point. This will provide close to optimal sequence of bombs.

UPD: We should also take number of zeros into account, becouse bombin them is inefficiently. In fact the problem is to minimize number of hitted zeros. But we can not know how any step gets us closer to this aim. I agree with idea that the problem is NP-complete. I sugest a greedy approach, which will give an answer close to real.

This is not optimal. Counter-example: 1010101,0010100 (top row, bottom row) Your approach will require 3. It can be done in 2. – Mysticial – 2013-03-09T18:51:47.140

2

Here is a solution that generalizes the good properties of the corners.

Let's assume that we could find a perfect drop point for a given field, that is, a best way to decrease the value in it. Then to find the minimum number of bombs to be dropped, a first draft of an algorithm could be (the code is copy-pasted from a ruby implementation):

dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
coordinates = choose_a_perfect_drop_point
drop_bomb(coordinates)
dropped_bomb_count += 1
end
return dropped_bomb_count

The challenge is choose_a_perfect_drop_point. First, let's define what a perfect drop point is.

• A drop point for (x, y) decreases the value in (x, y). It may also decrease values in other cells.
• A drop point a for (x, y) is better than a drop point b for (x, y) if it decreases the values in a proper superset of the cells that b decreases.
• A drop point is maximal if there is no other better drop point.
• Two drop points for (x, y) are equivalent if they decrease the same set of cells.
• A drop point for (x, y) is perfect if it is equivalent to all maximal drop points for (x, y).

If there is a perfect drop point for (x, y), you cannot decrease the value at (x, y) more effectively than to drop a bomb on one of the perfect drop points for (x, y).

A perfect drop point for a given field is a perfect drop point for any of its cells.

Here are few examples:

1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

The perfect drop point for the cell (0, 0) (zero-based index) is (1, 1). All other drop points for (1, 1), that is (0, 0), (0, 1), and (1, 0), decrease less cells.

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

A perfect drop point for the cell (2, 2) (zero-based index) is (2, 2), and also all the surrounding cells (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), and (3, 3).

0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

a perfect drop points for the cell (2, 2) is (3, 1): It decreases the value in (2, 2), and the value in (4, 0). All other drop points for (2, 2) are not maximal, as they decrease one cell less. The perfect drop point for (2, 2) is also the perfect drop point for (4, 0), and it is the only perfect drop point for the field. It leads to the perfect solution for this field (one bomb drop).

1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
1 0 0 0 0

There is no perfect drop point for (2, 2): Both (1, 1) and (1, 3) decrease (2, 2) and another cell (they are maximal drop points for (2, 2)), but they are not equivalent. However, (1, 1) is a perfect drop point for (0, 0), and (1, 3) is a perfect drop point for (0, 4).

With that definition of perfect drop points and a certain order of checks, I get the following result for the example in the question:

Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28

However, the algorithm only works if there is at least one perfect drop point after each step. It is possible to construct examples where there are no perfect drop points:

0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

For these cases, we can modify the algorithm so that instead of a perfect drop point, we choose a coordinate with a minimal choice of maximal drop points, then calculate the minimum for each choice. In the case above, all cells with values have two maximal drop points. For example, (0, 1) has the maximal drop points (1, 1) and (1, 2). Choosing either one and then calcualting the minimum leads to this result:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2

This is pretty much the greedy algorithm presented above. – darksky – 2013-03-11T18:09:37.030

Well, it is a greedy algorithm as well, but instead of focussing on corners and edges, I defined how to choose the next drop point. With the example square of 5x7, it is easy to talk about corners, on a 1000x1000 field, not so much. If you check the order in which my algorithm clears the field, it is not from the outside in, but top-to-bottom/left-to-right. – Tammo Freese – 2013-03-11T20:32:32.793

1

If you want the absolute optimal solution to clean the board you will have to use classic backtracking, but if the matrix is very big it will take ages to find the best solution, if you want an "possible" optimal solution you can use greedy algorithm, if you need help writing the algorithm i can help you

Come to think of it that is the best way. Make another matrix there you store the points you remove by dropping a bomb there then chose the cell with maximum points and drop the bomb there update the points matrix and continue. Example:

2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))

cell value +1 for every adjacent cell with a value higher than 0

7will have to use classic backtracking. Do you have a proof for this? – Shahbaz – 2013-03-08T18:02:25.227

I'm not sure. It's from contest I'm preparing to (from previous year). Limits are 1 <= n,m <= 1000 (don't know if big or not). Anyway you need exact answer (it's similar to CERC contest and so on). Time limit is not given tho, no answers, no solutions on contest page either. – abc – 2013-03-08T18:05:06.083

well every other algorithm will give you a possible optimal solution but until you try them all (backtracking) you won't know if that solution is the best – cosmin.danisor – 2013-03-08T18:05:32.577

2you dont need to use backtracking becuase it is combination you search, not permutaion. Order of droping bombs is not important – Luka Rahne – 2013-03-08T18:05:54.363

then you can try using a variation of greedy. at every step create a new matrix and every point will have the value of his cell + 1 for every cell next to it >0 this way will chose better where to drop the next bombs – cosmin.danisor – 2013-03-08T18:10:45.257

isn't order important because some orders may result in the board being clear earlier than others, even though they all end up at zero? – Mikeb – 2013-03-08T20:56:14.007

Well, order is not important in the sense that if you have a particular sequence of bombings, going back and re-bombing those same spaces each the same number of times as before but in a different order produces the same final grid. But on the other hand your choice of which space to bomb can affect which remaining space has the highest weight, so at least when your greedy algorithm is choosing between two spaces of equal weight I think the choice could make a difference. – Tim Goodman – 2013-03-08T21:02:20.293

making the matrix with points for each cell gives you some order because at every step you throw the bomb on the cell with the most points – cosmin.danisor – 2013-03-08T21:09:47.730

1

Well, suppose we number the board positions 1, 2, ..., n x m. Any sequence of bomb drops can be represented by a sequence of numbers in this set, where numbers can repeat. However, the effect on the board is the same regardless of what order you drop the bombs in, so really any choice of bomb drops can be represented as a list of n x m numbers, where the first number represents the number of bombs dropped on position 1, the second number represents the number of bombs dropped on position 2, etc. Let's call this list of n x m numbers the "key".

You could try first calculating all board states resulting from 1 bomb drop, then use these to calculate all board states resulting from 2 bomb drops, etc until you get all zeros. But at each step you would cache the states using the key I defined above, so you can use these results in calculating the next step (a "dynamic programming" approach).

But depending on the size of n, m, and the numbers in the grid, the memory requirements of this approach might be excessive. You can throw away all the results for N bomb drops once you've calculated all the results for N + 1, so there's some savings there. And of course you could not cache anything at the cost of having it take a lot longer -- the dynamic programming approach trades memory for speed.

1Doubt it's possible since (if I understood you correctly). n = m. I need 10^6 int pointers to (10^6)^2 int cells. I have as many boards as keys in table. 10^12 doubt I can allocate so much in 32bit machine. – abc – 2013-03-08T18:16:20.783

Yeah, I just saw your comment about boards being up to 1000 by 1000. So that's a million ints for the state of each board, plus a million ints for the count of bombs dropped on each position. So for each board you store, you need 2 million ints, and there are a lot of possible boards... – Tim Goodman – 2013-03-08T19:25:07.773

I've added a second answer which uses a different approach. – Tim Goodman – 2013-03-08T20:40:21.063

this is basically a breadth-first search? – Lie Ryan – 2013-03-08T21:06:49.893

1Yeah. Kind of a brute force approach, but I guess not very practical for a large board. – Tim Goodman – 2013-03-08T21:16:36.610

@Kostek, why such a low estimate? It's more like k^(m*n) memory with k being the limit for the numbers the board is initially filled with. – Rotsor – 2013-03-09T03:29:02.673

1

1. Never bomb border (unless square does not have nonborder neighbour)
2. Zero corner.
3. To zero corner, drop value of corner one square away diagonaly (the only nonborder neighbour)
4. This will create new corners. Go to 2

Edit: did not notice that Kostek suggested almost same approach, so now I make stronger claim: If corners to clear are chosen to be always on outermost layer, then it is optimal.

In OP's example: dropping 2 (as 1+1 or 2) on anything else than on 5 does not leads to hitting any square that dropping on 5 would hit. So we simply must drop 2 on 5 (and 6 on lower left 1 ...)

After this, there is only one way how to clear (in top left) corner what was originaly 1 (now 0), and that is by dropping 0 on B3 (excel like notation). And so on.

Only after clearing whole A and E columns and 1 and 7 rows, start clearing one layer deeper.

Consider cleared only those intentionaly cleared, clearing 0 value corners costs nothing and simplifies thinking about it.

Because all bombs dropped this way must be dropped and this leads to cleared fields, it is optimal solution.

After good sleep I realized that this is not true. Consider

ABCDE
1 01000
2 10000
3 00000
4 00000

My approach would drop bombs on B3 and C2, when dropping on B2 would be enough

But is this optimal though? – Mysticial – 2013-03-08T18:18:55.123

7New corners can be bomb on 2 ways (if most corner point contains lowest of all 4 values). Which one is optimum bombing? – abc – 2013-03-08T18:20:46.503

I was thinking about a similar approach, and when you reach a situation like Kostek described, then start to use backtracking... – Karoly Horvath – 2013-03-08T18:27:02.060

Corners give you minimum amounts of bombs to be dropped on diagonal square. But once you zeroed them, next border tile will not necessarily have obvious optimal point. It is a good way to reduce the search space though. – Eugene – 2013-03-08T18:28:27.123

What about choosing the new corner diagonal that yields the highest total count in the hit box? – Judge Maygarden – 2013-03-08T18:29:18.043

That is just a version of greedy approach -- will get you some optimum, but it might not be the global one. – Eugene – 2013-03-08T18:32:29.740

This is where the expression "cutting the corners" came from! – Eugene – 2013-03-08T18:46:41.990

I would give +1 except Kostek mentioned this exact strategy in the comments of the question – BlueRaja - Danny Pflughoeft – 2013-03-08T19:22:18.320

1

Brute Force !

I know it is not efficient, but even if you find a faster algorithm, you can always test against this result to know how accurate it is.

Use some recursion, like this:

void fn(tableState ts, currentlevel cl)
{
// first check if ts is all zeros yet, if not:
//
// do a for loop to go through all cells of ts,
// for each cell do a bomb, and then
// call:
// fn(ts, cl + 1);

}

You can make this more efficient by caching, if different way lead to same result, you shouldn't repeat the same steps.

To elaborate:

if bombing cell 1,3,5 leads to the same result as bombing cell 5,3,1 , then, you shouldn't re-do all the next steps again for both cases, only 1 is enough, you should store somewhere all table states and use its results.

A hash of table stats can be used to do fast comparison.

1

Here's my solution.. I won't write it out in code yet since I don't have time, but I believe this should produce an optimal number of moves each time - though I'm not sure how efficient it would be at finding the points to bomb.

Firstly, as @Luka Rahne stated in one of the comments, the order in which you bomb is not important- only the combination.

Secondly, as many others have stated, bombing 1-off the diagonal from the corners is optimal because it touches more points than the corners.

This generates the basis for my version of the algorithm: We can bomb the '1-off from the corners' first or last, it doesn't matter (in theory) We bomb those first because it makes later decisions easier (in practice) We bomb the point which affects the most points, while simultaneously bombing those corners.

Let's define Points Of Resistance to be the points in the board with the most non-bombable points + largest number of 0's around them

non-bombable points can be defined as points which don't exist in our current scope of the board we're looking at.

I'll also define 4 bounds which will handle our scope: Top=0, Left=0, Bottom=k,right=j. (values to start)

Finally, I'll define optimal bombs as bombs which are dropped on points that are adjacent to points of resistance and are touching (1) the highest valued point of resistance and (2) the largest number of points possible.

Regarding the approach- it's obvious we're working from the outside in. We will be able to work with 4 'bombers' at the same time.

The first points of resistance are obviously our corners. The 'out of bound' points are not bombable (there are 5 points outside the scope for each corner). So we bomb the points diagonally one off the corners first.

Algorithm:

1. Find the 4 optimal bomb points.
2. If a bomb point is bombing a resistance point which is touching 2 bounds (i.e. a corner), bomb till that point is 0. Otherwise, bomb each until one of the points of resistance touching the optimal bomb point is 0.
3. for each bound: if(sum(bound)==0) advance bound

repeat until TOP=BOTTOM and LEFT=RIGHT

I will try to write the actual code later

1

I got 28 moves as well. I used two tests for the best next move: first the move producing the minimum sum for the board. Second, for equal sums, the move producing the maximum density, defined as:

number-of-zeros / number-of-groups-of-zeros

This is Haskell. "solve board" shows the engine's solution. You can play the game by typing "main", then enter a target point, "best" for a recommendation, or "quit" to quit.

OUTPUT:
*Main> solve board
[(4,4),(3,6),(3,3),(2,2),(2,2),(4,6),(4,6),(2,6),(3,2),(4,2),(2,6),(3,3),(4,3),(2,6),(4,2),(4,6),(4,6),(3,6),(2,6),(2,6),(2,4),(2,4),(2,6),(3,6),(4,2),(4,2),(4,2),(4,2)]

import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)

board = [2,3,4,7,1,
1,5,2,6,2,
4,3,4,2,1,
2,1,2,4,1,
3,1,3,4,1,
2,1,4,3,2,
6,9,1,6,4]

n = 5
m = 7

updateBoard board pt =
let x = fst pt
y = snd pt
precedingLines = replicate ((y-2) * n) 0
bomb = concat \$ replicate (if y == 1
then 2
else min 3 (m+2-y)) (replicate (x-2) 0
++ (if x == 1
then [1,1]
else replicate (min 3 (n+2-x)) 1)
++ replicate (n-(x+1)) 0)
in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)

showBoard board =
let top = "   " ++ (concat \$ map (\x -> show x ++ ".") [1..n]) ++ "\n"
chunks = chunksOf n board
in putStrLn (top ++ showBoard' chunks "" 1)
where showBoard' []     str count = str
showBoard' (x:xs) str count =
showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)

instances _ [] = 0
instances x (y:ys)
| x == y    = 1 + instances x ys
| otherwise = instances x ys

density a =
let numZeros = instances 0 a
groupsOfZeros = filter (\x -> head x == 0) (group a)
in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)

boardDensity board = sum (map density (chunksOf n board))

moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]

bestMove board =
let lowestSumMoves = take 1 \$ groupBy ((==) `on` snd)
\$ sortBy (comparing snd) (map (\x -> (x, sum \$ updateBoard board x)) (moves))
in if null lowestSumMoves
then (0,0)
else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves)
in fst \$ head \$ reverse \$ sortBy (comparing snd)
(map (\x -> (x, boardDensity \$ updateBoard board x)) (lowestSumMoves'))

solve board = solve' board [] where
solve' board result
| sum board == 0 = result
| otherwise      =
let best = bestMove board
in solve' (updateBoard board best) (result ++ [best])

main :: IO ()
main = mainLoop board where
mainLoop board = do
putStrLn ""
showBoard board
putStr "Pt: "
a <- getLine
case a of
"quit"    -> do putStrLn ""
return ()
"best"    -> do putStrLn (show \$ bestMove board)
mainLoop board
otherwise -> let ws = splitOn "," a
in do mainLoop (updateBoard board pt)

1

You could use state space planning. For example, using A* (or one of its variants) coupled with an heuristic f = g + h like this:

• g: number of bombs dropped so far
• h: sum over all values of the grid divided by 9 (which is the best result, meaning we have an admissible heuristics)

1

There seems to be a nonbipartite matching substructure here. Consider the following instance:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

The optimal solution to this case has size 5 since that's the size of a minimum cover of the vertices of a 9-cycle by its edges.

This case, in particular, shows that the linear programming relaxation a few people have posted isn't exact, doesn't work, and all those other bad things. I'm pretty sure I can reduce "cover the vertices of my planar cubic graph by as few edges as possible" to your problem, which makes me doubt whether any of the greedy/hill-climbing solutions are going to work.

I don't see a way to solve this in polynomial time in the worst case. There might be a very clever binary-search-and-DP solution that I'm not seeing.

EDIT: I see that the contest (http://deadline24.pl) is language-agnostic; they send you a bunch of input files and you send them outputs. So you don't need something that runs in worst-case polynomial time. In particular, you get to look at the input!

There are a bunch of small cases in the input. Then there's a 10x1000 case, a 100x100 case, and a 1000x1000 case. The three large cases are all very well-behaved. Horizontally adjacent entries typically have the same value. On a relatively beefy machine, I'm able to solve all of the cases by brute-forcing using CPLEX in just a couple of minutes. I got lucky on the 1000x1000; the LP relaxation happens to have an integral optimal solution. My solutions agree with the .ans files provided in the test data bundle.

I'd bet you can use the structure of the input in a much more direct way than I did if you took a look at it; seems like you can just pare off the first row, or two, or three repeatedly until you've got nothing left. (Looks like, in the 1000x1000, all of the rows are nonincreasing? I guess that's where your "part B" comes from? )

Yup. Sometimes I just skip "irrelevant" part of text. Just briefly get idea and so on. This time it basically change level from easy to hard as hell :P Anyway I know you can try to make a heuristic having "known" input set. On the other hand I just think that if answer is not percentage points, there must be some algorithm that will easily perform during 5h. All I found had too big complexity. Then I read it more carefully, when somebody asked about origin :) – abc – 2013-03-11T06:15:52.283

We can say thanks to that many people have nice problem, to think about, but doubt it can be do in polynomial time. It's funny how one simple constraint, changes level of task from easy to impossible. – abc – 2013-03-11T06:16:18.257

@Kostek: Sorry if I was unclear. I'm...pretty bad at pitching explanations at an appropriate level for the audience. :) Whereabouts was I unclear? – tmyklebu – 2013-03-11T07:47:06.977

1

This can be solved using a tree of depth O(3^(n)). Where n is the sum of all of the squares.

First consider that it is trivial to solve the problem with a tree of O(9^n), simply consider all of the possible bombing locations. For an example see Alfe's implementation.

Next realize that we can work to bomb from the bottom up and still get a minimum bombing pattern.

1. Start from the bottom left corner.
2. Bomb it to oblivion with the only plays that make sense (up and to the right).
3. Move one square to the right.
4. While the target has a value greater than zero, consider each of the 2 plays that make sense (straight up or up and to the right), reduce the value of the target by one, and make a new branch for each possibility.
5. Move another to the right.
6. While the target has a value greater than zero, consider each of the 3 plays that make sense (up left, up, and up right), reduce the value of the target by one, and make a new branch for each possibility.
7. Repeat steps 5 and 6 until the row is eliminated.
8. Move up a row and repeat steps 1 to 7 until the puzzle is solved.

This algorithm is correct because

1. It is necessary to complete each row at some point.
2. Completing a row always requires a play either one above, one below, or within that row.
3. It is always as good or better to choose a play one above the lowest uncleared row than a play on the row or below the row.

In practice this algorithm will regularly do better than its theoretical maximum because it will regularly bomb out neighbors and reduce the size of the search. If we assume that each bombing decreases the value of 4 additional targets, then our algorithm will run in O(3^(n/4)) or approximately O(1.3^n).

Because this algorithm is still exponential, it would be wise to limit the depth of the search. We might limit the number of branches allowed to some number, X, and once we are this deep we force the algorithm to choose the best path it has identified so far (the one that has the minimum total board sum in one of its terminal leaves). Then our algorithm is guaranteed to run in O(3^X) time, but it is not guaranteed to get the correct answer. However, we can always increase X and test empirically if the trade off between increased computation and better answers is worthwhile.

1

I can't think of a way to calculate the actual number without just computing the bombing campaign using my best heuristic and hope I get a reasonable result.

So my method is to compute a bombing efficiency metric for each cell, bomb the cell with the highest value, .... iterate the process until I've flattened everything. Some have advocated using simple potential damage (i.e. score from 0 to 9) as a metric, but that falls short by pounding high value cells and not making use of damage overlap. I'd calculate cell value - sum of all neighbouring cells, reset any positive to 0 and use the absolute value of anything negative. Intuitively this metric should make a selection that help maximise damage overlap on cells with high counts instead of pounding those directly.

The code below reaches total destruction of the test field in 28 bombs (note that using potential damage as metric yields 31!).

using System;
using System.Collections.Generic;
using System.Linq;

namespace StackOverflow
{
internal class Program
{
// store the battle field as flat array + dimensions
private static int _width = 5;
private static int _length = 7;
private static int[] _field = new int[] {
2, 3, 4, 7, 1,
1, 5, 2, 6, 2,
4, 3, 4, 2, 1,
2, 1, 2, 4, 1,
3, 1, 3, 4, 1,
2, 1, 4, 3, 2,
6, 9, 1, 6, 4
};
// this will store the devastation metric
private static int[] _metric;

// do the work
private static void Main(string[] args)
{
int count = 0;

while (_field.Sum() > 0)
{
Console.Out.WriteLine("Round {0}:", ++count);
GetBlastPotential();
int cell_to_bomb = FindBestBombingSite();
PrintField(cell_to_bomb);
Bomb(cell_to_bomb);
}
Console.Out.WriteLine("Done in {0} rounds", count);
}

// convert 2D position to 1D index
private static int Get1DCoord(int x, int y)
{
if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
else
{
return (y * _width) + x;
}
}

// Convert 1D index to 2D position
private static void Get2DCoord(int n, out int x, out int y)
{
if ((n < 0) || (n >= _field.Length))
{
x = -1;
y = -1;
}
else
{
x = n % _width;
y = n / _width;
}
}

// Compute a list of 1D indices for a cell neighbours
private static List<int> GetNeighbours(int cell)
{
List<int> neighbours = new List<int>();
int x, y;
Get2DCoord(cell, out x, out y);
if ((x >= 0) && (y >= 0))
{
List<int> tmp = new List<int>();
tmp.Add(Get1DCoord(x - 1, y - 1));
tmp.Add(Get1DCoord(x - 1, y + 1));
tmp.Add(Get1DCoord(x + 1, y - 1));
tmp.Add(Get1DCoord(x + 1, y + 1));

// eliminate invalid coords - i.e. stuff past the edges
foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
}
return neighbours;
}

// Compute the devastation metric for each cell
// Represent the Value of the cell minus the sum of all its neighbours
private static void GetBlastPotential()
{
_metric = new int[_field.Length];
for (int i = 0; i < _field.Length; i++)
{
_metric[i] = _field[i];
List<int> neighbours = GetNeighbours(i);
if (neighbours != null)
{
foreach (int j in neighbours) _metric[i] -= _field[j];
}
}
for (int i = 0; i < _metric.Length; i++)
{
_metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
}
}

//// Compute the simple expected damage a bomb would score
//private static void GetBlastPotential()
//{
//    _metric = new int[_field.Length];
//    for (int i = 0; i < _field.Length; i++)
//    {
//        _metric[i] = (_field[i] > 0) ? 1 : 0;
//        List<int> neighbours = GetNeighbours(i);
//        if (neighbours != null)
//        {
//            foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
//        }
//    }
//}

// Update the battle field upon dropping a bomb
private static void Bomb(int cell)
{
List<int> neighbours = GetNeighbours(cell);
foreach (int i in neighbours)
{
if (_field[i] > 0) _field[i]--;
}
}

// Find the best bombing site - just return index of local maxima
private static int FindBestBombingSite()
{
int max_idx = 0;
int max_val = int.MinValue;
for (int i = 0; i < _metric.Length; i++)
{
if (_metric[i] > max_val)
{
max_val = _metric[i];
max_idx = i;
}
}
return max_idx;
}

// Display the battle field on the console
private static void PrintField(int cell)
{
for (int x = 0; x < _width; x++)
{
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
else
}
Console.Out.Write(" || ");
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
else
}
Console.Out.WriteLine();
}
Console.Out.WriteLine();
}
}
}

The resulting bombing pattern is output as follows (field values on the left, metric on the right)

Round 1:
2   1   4   2   3   2   6  ||   7  16   8  10   4  18   6
3   5   3   1   1   1   9  ||  11  18  18  21  17  28   5
4  [2]  4   2   3   4   1  ||  19 [32] 21  20  17  24  22
7   6   2   4   4   3   6  ||   8  17  20  14  16  22   8
1   2   1   1   1   2   4  ||  14  15  14  11  13  16   7

Round 2:
2   1   4   2   3   2   6  ||   5  13   6   9   4  18   6
2   4   2   1   1  [1]  9  ||  10  15  17  19  17 [28]  5
3   2   3   2   3   4   1  ||  16  24  18  17  17  24  22
6   5   1   4   4   3   6  ||   7  14  19  12  16  22   8
1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 3:
2   1   4   2   2   1   5  ||   5  13   6   7   3  15   5
2   4   2   1   0   1   8  ||  10  15  17  16  14  20   2
3  [2]  3   2   2   3   0  ||  16 [24] 18  15  16  21  21
6   5   1   4   4   3   6  ||   7  14  19  11  14  19   6
1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 4:
2   1   4   2   2   1   5  ||   3  10   4   6   3  15   5
1   3   1   1   0   1   8  ||   9  12  16  14  14  20   2
2   2   2   2   2  [3]  0  ||  13  16  15  12  16 [21] 21
5   4   0   4   4   3   6  ||   6  11  18   9  14  19   6
1   2   1   1   1   2   4  ||  10   9  10   9  13  16   7

Round 5:
2   1   4   2   2   1   5  ||   3  10   4   6   2  13   3
1   3   1   1   0  [0]  7  ||   9  12  16  13  12 [19]  2
2   2   2   2   1   3   0  ||  13  16  15  10  14  15  17
5   4   0   4   3   2   5  ||   6  11  18   7  13  17   6
1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 6:
2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
1   3   1   1   0   0   6  ||   9  12  16  11   8  13   0
2   2   2   2   0   2   0  ||  13  16  15   9  14  14  15
5   4  [0]  4   3   2   5  ||   6  11 [18]  6  11  15   5
1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 7:
2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
1   3   1   1   0   0   6  ||   8  10  13   9   7  13   0
2  [1]  1   1   0   2   0  ||  11 [15] 12   8  12  14  15
5   3   0   3   3   2   5  ||   3   8  10   3   8  15   5
1   1   0   0   1   2   4  ||   8   8   7   7   9  13   5

Round 8:
2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
0   2   0   1   0   0   6  ||   7   7  12   7   7  13   0
1   1   0   1   0   2   0  ||   8   8  10   6  12  14  15
4   2   0   3   3  [2]  5  ||   2   6   8   2   8 [15]  5
1   1   0   0   1   2   4  ||   6   6   6   7   9  13   5

Round 9:
2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
0   2   0   1   0   0   6  ||   7   7  12   7   6  12   0
1   1   0   1   0  [1]  0  ||   8   8  10   5  10 [13] 13
4   2   0   3   2   2   4  ||   2   6   8   0   6   9   3
1   1   0   0   0   1   3  ||   6   6   6   5   8  10   4

Round 10:
2   1   4   2   1   0   4  ||   1   7   2   4   2  10   1
0   2  [0]  1   0   0   5  ||   7   7 [12]  7   6  11   0
1   1   0   1   0   1   0  ||   8   8  10   4   8   9  10
4   2   0   3   1   1   3  ||   2   6   8   0   6   8   3
1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 11:
2   0   3   1   1   0   4  ||   0   6   0   3   0  10   1
0   1   0   0   0  [0]  5  ||   4   5   5   5   3 [11]  0
1   0   0   0   0   1   0  ||   6   8   6   4   6   9  10
4   2   0   3   1   1   3  ||   1   5   6   0   5   8   3
1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 12:
2   0   3   1   0   0   3  ||   0   6   0   2   1   7   1
0   1   0   0   0   0   4  ||   4   5   5   4   1   7   0
1   0   0   0   0  [0]  0  ||   6   8   6   4   5  [9]  8
4   2   0   3   1   1   3  ||   1   5   6   0   4   7   2
1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 13:
2   0   3   1   0   0   3  ||   0   6   0   2   1   6   0
0   1   0   0   0   0   3  ||   4   5   5   4   1   6   0
1  [0]  0   0   0   0   0  ||   6  [8]  6   3   3   5   5
4   2   0   3   0   0   2  ||   1   5   6   0   4   6   2
1   1   0   0   0   1   3  ||   6   6   6   3   4   4   0

Round 14:
2   0   3   1   0  [0]  3  ||   0   5   0   2   1  [6]  0
0   0   0   0   0   0   3  ||   2   5   4   4   1   6   0
0   0   0   0   0   0   0  ||   4   4   4   3   3   5   5
3   1   0   3   0   0   2  ||   0   4   5   0   4   6   2
1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 15:
2   0   3   1   0   0   2  ||   0   5   0   2   1   4   0
0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
0   0   0   0   0   0   0  ||   4   4   4   3   3   4   4
3   1   0   3   0  [0]  2  ||   0   4   5   0   4  [6]  2
1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 16:
2  [0]  3   1   0   0   2  ||   0  [5]  0   2   1   4   0
0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
3   1   0   3   0   0   1  ||   0   4   5   0   3   3   1
1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 17:
1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
3   1  [0]  3   0   0   1  ||   0   4  [5]  0   3   3   1
1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 18:
1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
0   0   0   0   0   0   0  ||   3   3   2   2   2   3   3
3  [0]  0   2   0   0   1  ||   0  [4]  2   0   2   3   1
1   0   0   0   0   0   2  ||   2   4   2   2   2   3   0

Round 19:
1   0   2   1   0  [0]  2  ||   0   3   0   1   1  [4]  0
0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
0   0   0   0   0   0   0  ||   2   2   2   2   2   3   3
2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 20:
1  [0]  2   1   0   0   1  ||   0  [3]  0   1   1   2   0
0   0   0   0   0   0   1  ||   1   3   3   3   1   2   0
0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 21:
0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
2   0   0   2   0  [0]  1  ||   0   2   2   0   2  [3]  1
0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 22:
0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
[0]  0   0   0   0   0   0  ||  [2]  2   2   2   2   1   1
2   0   0   2   0   0   0  ||   0   2   2   0   2   1   1
0   0   0   0   0   0   1  ||   2   2   2   2   2   1   0

Round 23:
0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
0   0  [0]  0   0   0   1  ||   0   1  [2]  2   1   2   0
0   0   0   0   0   0   0  ||   1   1   2   2   2   1   1
1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 24:
0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
0   0  [0]  0   0   0   0  ||   1   1  [2]  2   2   1   1
1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 25:
0   0   0   0   0  [0]  1  ||   0   0   0   0   0  [2]  0
0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
0   0   0   0   0   0   0  ||   1   1   1   1   1   1   1
1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 26:
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
[0]  0   0   0   0   0   0  ||  [1]  1   1   1   1   0   0
1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 27:
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
0   0  [0]  0   0   0   0  ||   0   0  [1]  1   1   0   0
0   0   0   1   0   0   0  ||   0   0   1   0   1   1   1
0   0   0   0   0   0   1  ||   0   0   1   1   1   1   0

Round 28:
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
0   0   0   0   0  [0]  0  ||   0   0   0   0   0  [1]  1
0   0   0   0   0   0   1  ||   0   0   0   0   0   1   0

Done in 28 rounds

1

evaluation function, total sum:

int f (int ** matrix, int width, int height, int x, int y)
{
int m[3][3] = { 0 };

m[1][1] = matrix[x][y];
if (x > 0) m[0][1] = matrix[x-1][y];
if (x < width-1) m[2][1] = matrix[x+1][y];

if (y > 0)
{
m[1][0] = matrix[x][y-1];
if (x > 0) m[0][0] = matrix[x-1][y-1];
if (x < width-1) m[2][0] = matrix[x+1][y-1];
}

if (y < height-1)
{
m[1][2] = matrix[x][y+1];
if (x > 0) m[0][2] = matrix[x-1][y+1];
if (x < width-1) m[2][2] = matrix[x+1][y+1];
}

return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}

objective function:

Point bestState (int ** matrix, int width, int height)
{
Point p = new Point(0,0);
int bestScore = 0;
int b = 0;

for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
{
b = f(matrix,width,height,i,j);

if (b > bestScore)
{
bestScore = best;
p = new Point(i,j);
}
}

retunr p;
}

destroy function:

void destroy (int ** matrix, int width, int height, Point p)
{
int x = p.x;
int y = p.y;

if(matrix[x][y] > 0) matrix[x][y]--;
if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;

if (y > 0)
{
if(matrix[x][y-1] > 0) matrix[x][y-1]--;
if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
}

if (y < height-1)
{
if(matrix[x][y] > 0) matrix[x][y+1]--;
if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
}
}

goal function:

bool isGoal (int ** matrix, int width, int height)
{
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
if (matrix[i][j] > 0)
return false;
return true;
}

linear maximization function:

void solve (int ** matrix, int width, int height)
{
while (!isGoal(matrix,width,height))
{
destroy(matrix,width,height, bestState(matrix,width,height));
}
}

This is not optimal, but can be optimized through finding a better evaluation function ..

.. but thinking about this problem, I was thinking that one of the main issues is getting abandoned figures in the middle of zeroes at some point, so I'd take another approach .. which is dominate minimal values into zero, then try to escape zeroes as possible, which lead to general minimization of minimal existing value(s) or so

0

This was an answer to the first asked question. I hadn't noticed that he changed the parameters.

Create a list of all targets. Assign a value to the target based on the number of positive values impacted by a drop (itself, and all neighbors). Highest value would be a nine.

Sort the targets by the number of targets impacted (Descending), with a secondary descending sort on the sum of each impacted target.

Drop a bomb on the highest ranked target, then re-calculate targets and repeat until all target values are zero.

Agreed, this is not always the most optimal. For example,

100011
011100
011100
011100
000000
100011

This approach would take 5 bombs to clear. Optimally, though, you could do it in 4. Still, pretty darn close and there is no backtracking. For most situations it will be optimal, or very close.

Using the original problem numbers, this approach solves in 28 bombs.

Adding code to demonstrate this approach (using a form with a button):

private void button1_Click(object sender, EventArgs e)
{
int[,] matrix = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3},
{17, 8, 15, 17, 12, 4, 5, 16, 8, 18},
{ 4, 19, 12, 11, 9, 7, 4, 15, 14, 6},
{ 17, 20, 4, 9, 19, 8, 17, 2, 10, 8},
{ 3, 9, 10, 13, 8, 9, 12, 12, 6, 18},
{16, 16, 2, 10, 7, 12, 17, 11, 4, 15},
{ 11, 1, 15, 1, 5, 11, 3, 12, 8, 3},
{ 7, 11, 16, 19, 17, 11, 20, 2, 5, 19},
{ 5, 18, 2, 17, 7, 14, 19, 11, 1, 6},
{ 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}};

int value = 0;
List<Target> Targets = GetTargets(matrix);
while (Targets.Count > 0)
{
BombTarget(ref matrix, Targets[0]);
value += 1;
Targets = GetTargets(matrix);
}
Console.WriteLine( value);
MessageBox.Show("done: " + value);
}

private static void BombTarget(ref int[,] matrix, Target t)
{
for (int a = t.x - 1; a <= t.x + 1; a++)
{
for (int b = t.y - 1; b <= t.y + 1; b++)
{
if (a >= 0 && a <= matrix.GetUpperBound(0))
{
if (b >= 0 && b <= matrix.GetUpperBound(1))
{
if (matrix[a, b] > 0)
{
matrix[a, b] -= 1;
}
}
}
}
}
Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
}

private static List<Target> GetTargets(int[,] matrix)
{
List<Target> Targets = new List<Target>();
int width = matrix.GetUpperBound(0);
int height = matrix.GetUpperBound(1);
for (int x = 0; x <= width; x++)
{
for (int y = 0; y <= height; y++)
{
Target t = new Target();
t.x = x;
t.y = y;
SetTargetValue(matrix, ref t);
}
}
Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
return Targets;
}

private static void SetTargetValue(int[,] matrix, ref Target t)
{
for (int a = t.x - 1; a <= t.x + 1; a++)
{
for (int b = t.y - 1; b <= t.y + 1; b++)
{
if (a >= 0 && a <= matrix.GetUpperBound(0))
{
if (b >= 0 && b <= matrix.GetUpperBound(1))
{
if (matrix[ a, b] > 0)
{
t.value += 1;
t.sum += matrix[a,b];
}

}
}
}
}

}

A class you will need:

class Target
{
public int value;
public int sum;
public int x;
public int y;
}

1Not optimal. Counterexample: 09090 This approach requires 18 bombs. It can be done in 9. – Mysticial – 2013-03-09T18:54:44.653

@Mysticial You didn't read the answer thoroughly. Since it's based on the number of non-zero fields impacted, this algorithm would bomb the middle zero and would be done in 9 drops. The high value of 9 is because there are up to eight neighbors and itself. – Anthony Queen – 2013-03-12T12:27:20.233

Then how about 1010101,0010100? – Mysticial – 2013-03-12T15:11:13.140

@Mysticial For the first, First zero, then last zero would be hit. It would be two drops. That's because each time it drops a bomb, it recalculates the next best target. For the last example, the middle zero again; One drop. – Anthony Queen – 2013-03-12T16:09:37.980

I don't see how your algorithm works at all then. It's not clear to me. It'd be better if you went ahead and implemented it in some major language. Then we can test it through various sample inputs. – Mysticial – 2013-03-12T16:21:13.393

@Mysticial Just to clarify the process... In the first example 09090, the first integer has a value of 1 because only one field is impacted if a bomb is droped there. The second integer also has a value of 1. The third integer has a value of 2 (two neighbors impacted). The third integer a value of 1, and the fourth a value of 1. After the first bomb hits the highest value target, it recalculates to get the next highest value target... which is again the third integer in your set. I hope this clarifies some. – Anthony Queen – 2013-03-12T16:28:11.553

Sorry if I'm being a jerk, but that's how it usually works with proofs. (Since it only takes one counter-example to prove something wrong.) How about this? 2010102, 0010100 This can be done in 4 bombs. But if I'm understanding your algorithm correctly, it will bomb the middle first - which is essentially wasted. – Mysticial – 2013-03-12T16:38:51.000

No problem. This is a good example with just 2010102. You would get three targets with a value 2. In this case, it might hit the 2nd, 4th, or 6th target somewhat randomly, depending on how the objects sort. So, in this case, it would have a chance of NOT working optimally. – Anthony Queen – 2013-03-12T16:42:34.530

Yeah, the original problem (without the sequencing) is hard - possibly NP-hard. So I wasn't expecting anybody to be able to come up with an answer that doesn't require back-tracking (which would imply exponential time). This answer seems to be the only one here that produces an optimal solution - but in exponential time with back-tracking.

– Mysticial – 2013-03-12T16:46:14.533

yeah, I saw that. It would be long running for anything very big. Without backtracking, I think this is as close as you can get. With backtracking, you can verify that a particular logic branch was in fact optimal. – Anthony Queen – 2013-03-12T16:49:30.240

I'll +1 you for putting up with my asshattery. :) – Mysticial – 2013-03-12T16:51:36.353

1

@AnthonyQueen: this doesn't work. please see http://chat.stackoverflow.com/transcript/message/8224273#8224273 for my counterexample.

– nneonneo – 2013-03-12T17:32:58.783

There, I implemented it with code. Quick hack, but it works. Please test any scenarios with it. – Anthony Queen – 2013-03-12T18:09:45.363

@AnthonyQueen: "pretty darn close" only works if you want to make an approximation algorithm. You should try to quantify "pretty darn close". I think you may be surprised at how off the mark your algorithm can be. I did not aim for "maximum badness" when writing the counterexample. – nneonneo – 2013-03-12T18:53:59.090

To take a dumb example, just multiply everything in the grid by 1000. Then your algorithm uses 5000 bombs while optimal is 4000. That's "much worse" in some sense. – nneonneo – 2013-03-12T18:54:59.607

I get it. Still, I'd love to see a solution that does better without backtracking. Given the original parameters and a randomized matrix, I still think this is a pretty solid solution. – Anthony Queen – 2013-03-12T19:12:21.957

0

All this problem boils down to is computing an edit distance. Simply calculate a variant of the Levenshtein distance between the given matrix and the zero matrix, where edits are replaced with bombings, using dynamic programming to store the distances between intermediate arrays. I suggest using a hash of the matrices as a key. In pseudo-Python:

memo = {}

def bomb(matrix,i,j):
# bomb matrix at i,j

def bombsRequired(matrix,i,j):
# bombs required to zero matrix[i,j]

def distance(m1, i, len1, m2, j, len2):
key = hash(m1)
if memo[key] != None:
return memo[key]

if len1 == 0: return len2
if len2 == 0: return len1

cost = 0
if m1 != m2: cost = m1[i,j]
m = bomb(m1,i,j)
dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
memo[key] = dist
return dist

0

The slowest but simplest and error free algorithm is generate and test all valid possibilities. for this case is very simple (because result is independent on the order of bomb placement).

1. create funct which N times apply bomp
2. create loop for all bompb-placement/bomb-count posibilities (stop when matrix==0)
3. remember always the best solution.
4. at the end of loop you have the best solution
• not only count of bombs, but also their placement

code can look like this:

void copy(int **A,int **B,int m,int n)
{
for (int i=0;i<m;i++)
for (int j=0;i<n;j++)
A[i][j]=B[i][j];
}

bool is_zero(int **M,int m,int n)
{
for (int i=0;i<m;i++)
for (int j=0;i<n;j++)
if (M[i][j]) return 0;
return 1;
}

void drop_bomb(int **M,int m,int n,int i,int j,int N)
{
int ii,jj;
ii=i-1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i-1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i-1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i  ; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i  ; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i  ; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
}

void solve_problem(int **M,int m,int n)
{
int i,j,k,max=0;
// you probably will need to allocate matrices P,TP,TM yourself instead of this:
int P[m][n],min;             // solution: placement,min bomb count
int TM[m][n],TP[m][n],cnt;   // temp
for (i=0;i<m;i++)            // max count of bomb necessary to test
for (j=0;j<n;j++)
if (max<M[i][j]) max=M[i][j];
for (i=0;i<m;i++)            // reset solution
for (j=0;j<n;j++)
P[i][j]=max;
min=m*n*max;
copy(TP,P,m,n); cnt=min;

for (;;)  // generate all possibilities
{
copy(TM,M,m,n);
for (i=0;i<m;i++)   // test solution
for (j=0;j<n;j++)
drop_bomb(TM,m,n,TP[i][j]);
if (is_zero(TM,m,n))// is solution
if (min>cnt)       // is better solution -> store it
{
copy(P,TP,m,n);
min=cnt;
}
// go to next possibility
for (i=0,j=0;;)
{
TP[i][j]--;
if (TP[i][j]>=0) break;
TP[i][j]=max;
i++; if (i<m) break;
i=0; j++; if (j<n) break;
break;
}
if (is_zero(TP,m,n)) break;
}
//result is in P,min
}

this can be optimized in lot of ways,... simplest is to reset solution with M matrix, but you need change the max value and also the TP[][] decrement code

0

Several answers so far give exponential time, some involve dynamic programming. I doubt if those are necessary.

My solution is O(mnS) where m, n are dimensions of the board, S is the sum of all integers. The idea is rather bruteforce: find the location that can kill the most each time and terminate at 0.

It gives 28 moves for the board given, and also prints out the board after each drop.

Complete, self-explanatory code:

import java.util.Arrays;

public class BombMinDrops {

private static final int[][] BOARD = {{2,3,4,7,1}, {1,5,2,6,2}, {4,3,4,2,1}, {2,1,2,4,1}, {3,1,3,4,1}, {2,1,4,3,2}, {6,9,1,6,4}};
private static final int ROWS = BOARD.length;
private static final int COLS = BOARD[0].length;
private static int remaining = 0;
private static int dropCount = 0;
static {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
remaining = remaining + BOARD[i][j];
}
}
}

private static class Point {
int x, y;
int kills;

Point(int x, int y, int kills) {
this.x = x;
this.y = y;
this.kills = kills;
}

@Override
public String toString() {
return dropCount + "th drop at [" + x + ", " + y + "] , killed " + kills;
}
}

private static int countPossibleKills(int x, int y) {
int count = 0;
for (int row = x - 1; row <= x + 1; row++) {
for (int col = y - 1; col <= y + 1; col++) {
try {
if (BOARD[row][col] > 0) count++;
} catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
}
}

return count;
}

private static void drop(Point here) {
for (int row = here.x - 1; row <= here.x + 1; row++) {
for (int col = here.y - 1; col <= here.y + 1; col++) {
try {
if (BOARD[row][col] > 0) BOARD[row][col]--;
} catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
}
}

dropCount++;
remaining = remaining - here.kills;
print(here);
}

public static void solve() {
while (remaining > 0) {
Point dropWithMaxKills = new Point(-1, -1, -1);
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
int possibleKills = countPossibleKills(i, j);
if (possibleKills > dropWithMaxKills.kills) {
dropWithMaxKills = new Point(i, j, possibleKills);
}
}
}

drop(dropWithMaxKills);
}

System.out.println("Total dropped: " + dropCount);
}

private static void print(Point drop) {
System.out.println(drop.toString());
for (int[] row : BOARD) {
System.out.println(Arrays.toString(row));
}

System.out.println();
}

public static void main(String[] args) {
solve();
}

}