title: identifying custom shapes in a 2D grid
body: <p>Dear stackoverflowers.</p>
  
  <p>So, let's say there's a grid, whose values at certain x and y represent whether there is a tile there (1) or it's missing (0).</p>
  
  <p>For example,</p>
  
  <pre><code>100110100010
  100100111110
  111110000000
  000010000000
  </code></pre>
  
  <p>And there are some already known shapes A, B and C, for example,</p>
  
  <pre><code>(A)  (B)  (C)
    1  1     1
  111, 111, 11 
  </code></pre>
  
  <p>So what I am trying to achieve is to identify which 1's on a grid belong to which shape.
  All of 1's should be used up, exact number of shapes is known, but rotation (no mirroring) is allowed, so I guess it's better to add rotated versions and think, that some shapes won't be found on grid. </p>
  
  <p>So, the expected result would be (it's known that it should be exactly 1xA, 2xB, 2xC):</p>
  
  <pre><code>A00CC0B000C0
  A00C00BBBCC0
  AABBB0000000
  0000B0000000
  </code></pre>
  
  <p>If there are several possible matches, any would suit, as long as every tile gets allocated to it's own shape.</p>
  
  <p>Moreover, finding out whether a tile is present or not ("uncovering") is an expensive operation (but results are cached, tiles don't appear out of nowhere), so I am actually seeking for a way to identify them with as minimum number of "uncoverings" as possible.
  (It's okay if it's not optimum, just identifying shapes would be great).</p>
  
  <p>Obviously, set of known shapes might change (but it will be known by the time of implementing and it will stay constant, so it's possible to tune up code for a particular set of tiles or develop some search strategies), but it won't be large (~5-6) and grid is quite small too (~15x15). </p>
  
  <p>Thanks!</p>