Plant trees on a golf course!
C, 223 182 bytes

O[15],U;main(y,v)char**v;{if(y&gt;7)for(;y--&gt;2;printf("%06o\n",O[y]));else for(int*r,x=1,X=8;X&lt;14;U&amp;x|*r|O[10-y]*9&amp;x*9?0:(U^=O[9-y]=*r=x,*r=main(y+1,v),U^=x),x*=8)r=O+v[1][y*7-++X]-88;}


Takes input as an argument in the format given in the question. Writes output to stdout as a grid of 0s with 1s where the trees go.

./TreesMin 'aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff'


Sample output:

010000
000001
001000
000010
100000
000100


Breakdown

O[15],                                  // Tree positions &amp; region usage
U;                                      // Column usage (bitmask)
main(y,v)char**v;{                      // Recursive main function
  if(y&gt;7)                               // Finished grid?
    for(;y--&gt;2;printf("%06o\n",O[y]));  //  Print it (rows are padded octal)
  else                                  // Not finished:
    for(int*r,x=1,X=8;X&lt;14;             //  Loop over columns
      U&amp;x|*r|O[10-y]*9&amp;x*9              //   Current cell violates rules?
        ?0                              //    Do nothing
        :(U^=O[9-y]=*r=x,               //   Else: mark cell
          *r=main(y+1,v),               //    Recurse
          U^=x)                         //    Unmark cell
      ,x*=8)                            //   Advance to next column
      r=O+v[1][y*7-++X]-88;             //   Region pointer for current iteration
}


It's an adaptation of my answer to the fastest-code version of this question. Doesn't have as much short-circuiting, but it's plenty fast enough for 6x6 grids.