Number of tilings on a triangular board with triangular tiles Background

Consider the shape \$T(n)\$ consisting of a triangular array of \$\frac{n(n+1)}{2}\$ unit regular hexagons:



John Conway proved that \$n = 12k + 0,2,9,11\$ if and only if \$T(n)\$ can be tiled (i.e. exactly covered without overlapping) with \$T(2)\$. At the same time, he also proved that no coloring argument could prove the fact. (Yes, this is yet another Conway challenge.)

Challenge

Let's define \$a_n\$ as the number of distinct tilings of \$T(n)\$ by \$T(2)\$. Compute as many terms of \$a_n\$ as possible in 10 minutes.

Reflection and/or rotation of a tiling is considered distinct from itself, unless the two are identical.

The program that prints the largest number of terms wins. In case of tie, the one that prints the last term in shorter time wins.

I have a Windows 10 machine with Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz and 32GB RAM, with Ubuntu 18.04 installed in WSL. Please include the instructions to run your code and where it works (Windows or Linux).

Output format (with test cases)

The submission should print the results infinitely for each \$n\$ starting from 0. Each line should include the values of \$n\$ and \$a_n\$. Here is first 21 lines of the expected output:

0 1
1 0
2 1
3 0
4 0
5 0
6 0
7 0
8 0
9 2
10 0
11 8
12 12
13 0
14 72
15 0
16 0
17 0
18 0
19 0
20 0
21 185328
22 0
23 4736520
24 21617456
25 0
26 912370744
27 0
28 0
29 0
30 0
31 0
32 0


Test cases for \$n \le 20\$ are generated using a naive Python 3 program. \$a_{21}\$ through \$a_{32}\$ (meaningful highest being \$a_{26}\$) were found using Arnauld's JS submission.

Notably, neither the full sequence 1, 0, 1, 0, 0, 0, ... nor the stripped-down one 1, 1, 2, 8, 12, 72, ... is on OEIS yet. As I don't have an OEIS account, I will let anyone interested to post this sequence (both versions) to OEIS (please leave a comment before you do). The sequence of nonzero indices is A072065. Edit: The sequence is on A334875, thanks to Lyxal.

Leaderboard


Rust with rustc -O by Anders Kaseorg, Score 44 at 45s
C++ with g++ -O3 by l4m2, Score 35 at 7min
Javascript with node by Arnauld, Score 32 at 1.8s


Pending


(none)
JavaScript (Node.js), N =  22 25  32 in ~2 seconds
A recursive search using bit masks and a cache to keep track of patterns whose result is already known.
It doesn't make much sense to try go further in Node. Using a binary matrix is significantly slower and BigInts are even slower. It should rather be ported to a language natively supporting 64-bit integers.
'use strict';

let ts = new Date;

for(let n = 0; n &lt;= 32; n++) {
  console.log(
    n.toString().padStart(2) + ' ' +
    solve(n).toString().padStart(10) + ' ' +
    '(' + ((new Date - ts) / 1000).toFixed(2) + ')'
  );
}

function solve(n) {
  // trivial cases
  if(![0, 2, 9, 11].includes(n % 12)) {
    return 0;
  }
  if(n == 0) {
    return 1;
  }

  // We work on a triangle stored as an array of bit masks:
  //   8 7 6 5 4 3 2 1 0 | 
  //  -------------------+---  With this format, the tribones
  //   . . . . . . . . A | 0   are turned into the following
  //   . . . . . . . A A | 1   trominos:
  //   . . . . . . B B C | 2   
  //   . . . . . D B C C | 3    X O    and    . X
  //   . . . . D D E E F | 4    O .           O O
  //   . . . G H H E F F | 5   
  //   . . G G H I I J J | 6   where 'X' is the arbitrary anchor
  //   . K L L M I N J O | 7   point used in this code
  //   K K L M M N N O O | 8
  let a = Array(n).fill(0),
      cache = a.map(_ =&gt; new Object);

  // recursive search, starting at (x, y) = (0, 0)
  return (function search(x, y) {
    // if we've reached the last row, make sure it's complete
    if(y == n - 1) {
      if(a[y] == (1 &lt;&lt; n) - 1) {
        return 1;
      }
      return 0;
    }

    // if we are beyond the last column, go on with the next row
    if(x &lt; 0) {
      y++;

      // either return the result from the cache right away
      if(cache[y][a[y]] !== undefined) {
        return cache[y][a[y]];
      }
      // or do a full search
      return cache[y][a[y]] = search(y, y);
    }

    // if (x, y) is already set, advance to the next column
    if(a[y] &gt;&gt; x &amp; 1) {
      return search(x - 1, y);
    }

    let res = 0;
 
    // try to insert X O
    //               O .
    if(x &amp;&amp; !(a[y] &gt;&gt; x - 1 &amp; 1)) {
      a[y] ^= 3 &lt;&lt; x - 1;
      a[y + 1] ^= 1 &lt;&lt; x;
      res += search(x - 2, y);
      a[y] ^= 3 &lt;&lt; x - 1;
      a[y + 1] ^= 1 &lt;&lt; x;
    }

    // try to insert . X
    //               O O
    if(!(a[y + 1] &gt;&gt; x + 1 &amp; 1)) {
      a[y] ^= 1 &lt;&lt; x;
      a[y + 1] ^= 3 &lt;&lt; x;
      res += search(x - 1, y);
      a[y] ^= 1 &lt;&lt; x;
      a[y + 1] ^= 3 &lt;&lt; x;
    }

    return res;
  })(0, 0);
}

Try it online!
Output
 0          1 (0.00)
 1          0 (0.00)
 2          1 (0.00)
 3          0 (0.00)
 4          0 (0.00)
 5          0 (0.00)
 6          0 (0.00)
 7          0 (0.00)
 8          0 (0.00)
 9          2 (0.00)
10          0 (0.00)
11          8 (0.00)
12         12 (0.01)
13          0 (0.01)
14         72 (0.01)
15          0 (0.01)
16          0 (0.01)
17          0 (0.01)
18          0 (0.01)
19          0 (0.01)
20          0 (0.01)
21     185328 (0.05)
22          0 (0.05)
23    4736520 (0.24)
24   21617456 (0.60)
25          0 (0.60)
26  912370744 (2.18)
27          0 (2.18)
28          0 (2.18)
29          0 (2.18)
30          0 (2.18)
31          0 (2.18)
32          0 (2.18)