Placing archers on wall

Question

I have a matrix (with 0 and 1), representing a castle wall and its surroundings.

My task is to place n archers on the wall in a way, that they covers as much surroundings as they can. There are two rules:

1: Every archer has range 1 - that means, he can shoot only on adjoining tiles (each tile has 8-neighbours), which aren't wall (friendly fire is banned in this army!).

2: If so happens, that multiple archers can shoot at same tile, that tile only counts as one.

I am struggling to find effective solution for this - partially because I don't know, if there exist any in polynomial time. Is there any?

I guess first step is to use BFS algorithm to rate every tile on matrix, but I don't know how to effectivelly solve it with second rule. The brute force solution is quite simple - rate every position and then try all of them, which would be very very uneffective - I think O(|possible placements|^n), which isn't nice.

Simple example:

The grey-colored tiles represents the wall. Numbers inside a tiles are representing coverage of archer placed on that tile. Just to be sure, I added orange ones, which are representing coverage of archer standing on tile b2. And the last information - correct solution for this is b2 and b6, with coverage of 14. It cannot be b2 and b4, because they covers only 11 tiles.

Answer 1

I don't see how the problem can be solved in guaranteed polynomial time, but you can express the problem as an integer linear program, which can be solved using an ILP solver such as GLPK.

Let c[i] be 0-1 integer variables, one for each square of surrounding. These will represent whether this square is covered by at least one archer.

Let a[i] be 0-1 integer variables, one for each square of castle wall. These will represent whether an archer stands on this square.

There must be at most n archers: sum(a[i] for i in castle walls) <= n

The c[i] must be zero if there's no adjacent archer: sum(a[j] for j castle wall adjacent to i) >= c[i]

The optimization target is to maximize sum(c[i]).

For example, suppose this is the map (where . is surrounding, and # castle wall), and want to place two archers.

....
.###
....

Then we have this ILP problem, where all the variables are 0-1 integer variables.

maximize (
      c[0,0] + c[0,1] + c[0,2] + c[0,3]
    + c[1,0]
    + c[2,0] + c[2,1] + c[2,2] + c[2,3])

such that:

a[1,1] + a[1,2] + a[1,3] <= 2

c[0,0] <= a[1,1]
c[0,1] <= a[1,1] + a[1,2]
c[0,2] <= a[1,1] + a[1,2] + a[1,3]
c[0,3] <= a[1,2] + a[1,3]
c[1,0] <= a[1,1]
c[2,0] <= a[1,1]
c[2,1] <= a[1,1] + a[1,2]
c[2,2] <= a[1,1] + a[1,2] + a[1,3]
c[2,3] <= a[1,2] + a[1,3]