title: Placing archers on wall
body: <p>I have a matrix (with 0 and 1), representing a castle wall and its surroundings. </p>
  
  <p>My task is to place <code>n</code> archers on the wall in a way, that they covers as much surroundings as they can. There are two rules:</p>
  
  <p><strong>1</strong>: 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!). </p>
  
  <p><strong>2</strong>: If so happens, that multiple archers can shoot at same tile, that tile only counts as one.</p>
  
  <p>I am struggling to find effective solution for this - partially because I don't know, if there exist any in polynomial time. <strong>Is there any?</strong></p>
  
  <p>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.</p>
  
  <p><strong>Simple example:</strong></p>
  
  <p>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.</p>
  
  <p><a href="https://i.stack.imgur.com/e8SKI.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/e8SKI.jpg" alt="sample test case"></a></p>