Plant trees in a park - As fast as you can!
JavaScript (ES6), 271 bytes

Takes input as an array of arrays of characters. Returns an array of bitmasks (integers) describing the position of the trees on each row, where the least significant bit is the leftmost position.

f=(a,p=0,r=[S=y=0],w=a.length)=&gt;a.some((R,y)=&gt;a.some((_,x)=&gt;r[y]&gt;&gt;x&amp;1&amp;&amp;(o[k=R[x]]=-~o[k])&gt;2),o=[])?0:y&lt;w?[...Array(1&lt;&lt;w)].some((_,n)=&gt;(k=n^(x=n&amp;-n))&lt;=x*2|k&amp;-k^k|n&amp;(p|p/2|p*2)||r.some((A,i)=&gt;r.some((B,j)=&gt;A&amp;B&amp;n&amp;&amp;i&lt;y&amp;j&lt;i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&amp;&amp;S:S=[...r]


Formatted and commented

f = (                                           // given:
  a,                                            //   - a = input matrix
  p = 0,                                        //   - p = previous bitmask
  r = [                                         //   - r = array of tree bitmasks
        S = y = 0 ],                            //   - S = solution / y = current row
  w = a.length                                  //   - w = width of matrix
) =&gt;                                            //
  a.some((R, y) =&gt; a.some((_, x) =&gt;             // if there's at least one area with more
    r[y] &gt;&gt; x &amp; 1 &amp;&amp; (o[k = R[x]] = -~o[k]) &gt; 2 // than two trees:
  ), o = []) ?                                  //
    0                                           //   abort right away
  :                                             // else:
    y &lt; w ?                                     //   if we haven't reached the last row:
      [...Array(1 &lt;&lt; w)].some((_, n) =&gt;         //     for each possible bitmask n:
        (k = n ^ (x = n &amp; -n)) &lt;= x * 2 |       //       if the bitmask does not consist of
        k &amp; - k ^ k |                           //       exactly two non-consecutive bits,
        n &amp; (p | p / 2 | p * 2) ||              //       or is colliding with the previous
        r.some((A, i) =&gt; r.some((B, j) =&gt;       //       bitmask, or generates more than two
          A &amp; B &amp; n &amp;&amp; i &lt; y &amp; j &lt; i            //       trees per column:
        )) ?                                    //
          0                                     //         yield 0
        :                                       //       else:
          (                                     //
            w = r[y],                           //         save the previous bitmask
            f(a, r[y++] = n, r),                //         recursive call with the new one
            r[--y] = w,                         //         restore the previous bitmask
            S                                   //         yield S
          )                                     //
      ) &amp;&amp; S                                    //     end of some(): return false or S
    :                                           //   else:
      S = [...r]                                //     this is a solution: save a copy in S


Test cases

This snippet includes an additional function to display the results in a more readable format. It is too slow to solve the last test case.

Expected runtime: ~5 seconds.



f=(a,p=0,r=[S=y=0],w=a.length)=&gt;a.some((R,y)=&gt;a.some((_,x)=&gt;r[y]&gt;&gt;x&amp;1&amp;&amp;(o[k=R[x]]=-~o[k])&gt;2),o=[])?0:y&lt;w?[...Array(1&lt;&lt;w)].some((_,n)=&gt;(k=n^(x=n&amp;-n))&lt;=x*2|k&amp;-k^k|n&amp;(p|p/2|p*2)||r.some((A,i)=&gt;r.some((B,j)=&gt;A&amp;B&amp;n&amp;&amp;i&lt;y&amp;j&lt;i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&amp;&amp;S:S=[...r]

format = (a, w) =&gt; a.map(n =&gt; [...('0'.repeat(w) + n.toString(2)).slice(-w)].reverse().join('')).join('\n')

console.log(format(f([
  [..."aabbbbbcc"],
  [..."adddbbbcc"],
  [..."adeeecccc"],
  [..."adddefgcc"],
  [..."hhhdifggg"],
  [..."hdddifffg"],
  [..."hhhiifffg"],
  [..."hihiifffg"],
  [..."iiiiiiggg"]
]), 9));

console.log(format(f([
  [..."aaabbbccc"],
  [..."aaaabbccc"],
  [..."aaaddbcce"],
  [..."ffddddcce"],
  [..."ffffddeee"],
  [..."fgffdheee"],
  [..."fggfhhhee"],
  [..."iggggheee"],
  [..."iiigggggg"]
]), 9));

console.log(format(f([
  [..."aaaaabccdd"],
  [..."aeaabbbccd"],
  [..."aeaabfbgcd"],
  [..."eeeaafggcd"],
  [..."eeeaafghcd"],
  [..."eeeiifghcd"],
  [..."ieiiigghcd"],
  [..."iiijighhcd"],
  [..."jjjjighhcd"],
  [..."jjjggghhdd"]
]), 10));