Plant trees on a golf course! This challenge is inspired by this app.



This is a much easier version of this challenge. This challenge is code-golf, while the other one is fastest-code.



You'll be given a square input grid, of dimensions 6-by-6 which is divided into 6 areas, where the cells of each area have a unique identifier (I'll use lower case letters from a-f in the the text here, but you may choose whatever you like, for instance integers 1-6).

The input may look like this (optional input format):

aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff


Or, easier to visualize:



Challenge:

You are to place 6 trees in this park, according to the following rules:


There shall be exactly 1 tree per column, and 1 tree per row
All areas shall have exactly 1 tree.
No trees can be adjacent to another tree, vertically, horizontally or diagonally


The solution to the layout above is:



Note: There is only one solution to each puzzle

Additional rules:


The input and output formats are optional


The output might for instance be a list of indices, a grid with 1/0 indicating if there's a tree in that position, or a modified version of the input where the trees are indicated

The execution time must be deterministic
The program must finish within 1 minute on a reasonable modern laptop
Brownie points if you don't brute force!


Test cases:

aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff
---
aAbbbb
aabbbB
aaCcbb
acccDb
Ecccdb
eeeFff
----------
aabccc
aacccc
aaddce
aeeeee
aeeefe
eeeeee
---
aaBccc
aacccC
aadDce
Aeeeee
aeeeFe
eEeeee
----------
aaaabb
aacbbb
aadddb
addeef
ddddee
dddeee
---
aaaaBb
aaCbbb
Aadddb
addeeF
dDddee
dddEee
----------
abbbcd
abebcd
addddd
dddddd
effdff
eeffff
---
abBbcd
abebCd
Addddd
dddDdd
effdfF
eEffff


Same test cases on a format that's a bit easier to parse:

Test case 1:
[1,1,2,2,2,2;1,1,2,2,2,2;1,1,3,3,2,2;1,3,3,3,4,2;5,3,3,3,4,2;5,5,5,6,6,6]
Test case 2:
[1,1,2,3,3,3;1,1,3,3,3,3;1,1,4,4,3,5;1,5,5,5,5,5;1,5,5,5,6,5;5,5,5,5,5,5]
Test case 3:
[1,1,1,1,2,2;1,1,3,2,2,2;1,1,4,4,4,2;1,4,4,5,5,6;4,4,4,4,5,5;4,4,4,5,5,5]
Test case 4:
[1,2,2,2,3,4;1,2,5,2,3,4;1,4,4,4,4,4;4,4,4,4,4,4;5,6,6,4,6,6;5,5,6,6,6,6]
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.