algorithm - Placing archers on wall -

i have matrix (with 0 , 1), representing castle wall , surroundings.

my task place n archers on wall in way, covers surroundings can. there 2 rules:

1: every archer has range 1 - means, can shoot on adjoining tiles (each tile has 8-neighbours), aren't wall (friendly fire banned in army!).

2: if happens, multiple archers can shoot @ same tile, tile counts one.

i struggling find effective solution - partially because don't know, if there exist in polynomial time. is there any?

i guess first step use bfs algorithm rate every tile on matrix, don't know how effectivelly solve second rule. brute force solution quite simple - rate every position , try of them, very uneffective - think o(|possible placements|^n), isn't nice.

simple example:

the grey-colored tiles represents wall. numbers inside tiles representing coverage of archer placed on tile. sure, added orange ones, representing coverage of archer standing on tile b2. , last information - correct solution b2 , b6, coverage of 14. cannot b2 , b4, because covers 11 tiles.

i don't see how problem can solved in guaranteed polynomial time, can express problem integer linear program, can solved using ilp solver such glpk.

let c[i] 0-1 integer variables, 1 each square of surrounding. these represent whether square covered @ least 1 archer.

let a[i] 0-1 integer variables, 1 each square of castle wall. these represent whether archer stands on square.

there must @ n archers: sum(a[i] in castle walls) <= n

the c[i] must 0 if there's no adjacent archer: sum(a[j] j castle wall adjacent i) >= c[i]

the optimization target maximize sum(c[i]).

for example, suppose map (where . surrounding, , # castle wall), , want place 2 archers.

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

then have ilp problem, variables 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]