Plant trees in a park - As fast as you can! This challenge is inspired by this app. The test cases are borrowed from that app.



This is a fastest-code challenge, where the objective is to solve the largest test cases in the least amount of time. There are provided some smaller test cases, so that people might test their algorithms faster.



You'll be given a square input grid, of dimensions n-by-n where 9 &lt;= n &lt;= 12. This grid will be divided into n areas, where the cells of each area has a unique identifiers (I'll use lower case letters from a-l in the the text here, but you may choose whatever you like, for instance integers 1-12).

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

aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg


Or, easier to visualize:



Challenge:

You are to place 2*n trees in this park, according to the following rules:


There shall be exactly 2 trees per column, and 2 trees per row
All areas shall have exactly 2 trees.
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 withing 1 minute at @isaacg's computer


Specs: 4 CPUs, i5-4300U CPU @ 1.9 GHz, 7.5G of RAM.

In case your program can't solve the two largest test case in one minute each then the time for the second largest (n=11) will be your score. You'll lose against a solution that solves the largest case.


Test cases:

I might edit this list if submissions seems to be customized to fit these test cases. 

12-by-12:

--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk


11-by-11:

--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii


10-by-10

--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd


9-by-9

--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg
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));