Domicules: tilings of the 2n × 2n board (A239273)

const { drawTilings } = require('./site/notes.js');
const { svgs, total } = drawTilings({ rowCount: 8, colCount: 8, pieces: 'domicule', spread: 4 });

figure(svgs, `4 of the ${total} domicule tilings of the 8 × 8 board.`);

const { calculateLog2Bound } = require('./js/solvers/domicule-rectangle-modular.js');

table(
  ['board', 'log2 of the bound', 'log2 of a(n)', 'primes for the CRT', 'check primes'],
  await Promise.all([2, 4, 6, 8, 10].map(async n => {
    const side = 2 * n;
    const bound = calculateLog2Bound(side, side);
    const actual = (await nb.context.countDomicule({ rowCount: side, colCount: side })).toString(2).length - 1;

    return [`${side}×${side}`, bound.toFixed(1), String(actual), String(Math.ceil((bound + 1) / 30)), '1'];
  })),
);

const { listPrimes, countModulo, combineResidues } = require('./js/solvers/domicule-rectangle-modular.js');
const primes = listPrimes(3);
const residues = primes.map(p => countModulo(8, 8, p));
const combined = combineResidues(residues.slice(0, 2), primes.slice(0, 2));
const exact = await nb.context.countDomicule({ rowCount: 8, colCount: 8 });

primes.forEach((p, i) => print(`a(4) mod ${p} = ${residues[i]}`));
print(`CRT of the first two: ${combined}`);
print(`check: ${combined} mod ${primes[2]} = ${combined % BigInt(primes[2])}, residue ${residues[2]}`);
print(`exact a(4) = ${exact}`);

if (combined !== exact || combined % BigInt(primes[2]) !== BigInt(residues[2])) {
  throw new Error('the CRT does not reproduce a(4)');
}

a(4) mod 2147483647 = 1234970112
a(4) mod 2147483629 = 1234997454
a(4) mod 2147483587 = 1235061252
CRT of the first two: 3263262629905
check: 3263262629905 mod 2147483587 = 1235061252, residue 1235061252
exact a(4) = 3263262629905

table(
  ['board', 'states per cell (dominoes)', 'states per cell (domicules)', 'numbering table (domicules)'],
  [8, 12, 14, 16, 18, 20].map(side => [
    `${side}×${side}`,
    (2 ** side).toLocaleString('en-US'),
    (2 ** (side + 2)).toLocaleString('en-US'),
    ((side * side + 1) * 2 ** (side + 2)).toLocaleString('en-US'),
  ]),
);

const { sampleDomiculeTiling } = require('./js/renderer');
const { createRandom } = require('./js/renderer/cftp');
const random = createRandom(2024);
const board = { rowCount: 4, colCount: 4 };
const samples = 280 * 100;
const counts = new Map();

for (let i = 0; i < samples; i++) {
  const key = JSON.stringify(sampleDomiculeTiling(board, random, 200));
  counts.set(key, (counts.get(key) || 0) + 1);
}

const expected = samples / 280;
const chiSquared = [...counts.values()].reduce((sum, observed) => sum + (observed - expected) ** 2 / expected, (280 - counts.size) * expected);
print(`distinct tilings seen: ${counts.size} of 280`);
print(`chi-squared: ${chiSquared.toFixed(1)} (limit 357.8)`);

if (counts.size !== 280 || chiSquared > 357.8) {
  throw new Error('the chain fails the uniformity test');
}

distinct tilings seen: 280 of 280
chi-squared: 286.9 (limit 357.8)

const reference = require('./js/solvers/domicule-rectangle-bigint.js');
const known = require('./js/core/cases').testCasesOf('domicule-rectangle-bigint');
const bFile = { 10: '974206002957112698855240779762528002509423239819130603938953917534367085458193363176670427' };

const rows = [];

for (let n = 0; n <= 10; n++) {
  const side = 2 * n;
  const board = { rowCount: side, colCount: side };
  const count = n <= 8 ? reference.calculateTotalTilingCombinations(board) : await nb.context.countDomicule(board);
  const published = known.find(t => t.rowCount === side && t.colCount === side);
  const expected = published?.expectedResult ?? bFile[n] ?? null;
  const status = expected === null ? 'not in OEIS yet' : expected !== String(count) ? 'DIFFERS FROM OEIS' : published ? 'matches OEIS' : 'matches the OEIS b-file';

  if (expected !== null && expected !== String(count)) {
    throw new Error(`a(${n}) differs from OEIS`);
  }

  rows.push([n, `${side}×${side}`, String(count), String(count).length, n <= 8 ? 'BigInt' : 'modular', status]);
}

table(['n', 'board', 'a(n)', 'digits', 'solver', 'status'], rows);

const { calculateTotalTilingCombinations } = require('./js/solvers/domicule-rectangle-bigint.js');
const sides = [1, 2, 3, 4, 5, 6, 7, 8];

table(
  ['h \\ w', ...sides.map(String)],
  sides.map(h => [String(h), ...sides.map(w => String(calculateTotalTilingCombinations({ rowCount: h, colCount: w })))]),
);

const { formatTime } = nb.context;

table(
  ['board', 'modular, Rust', 'modular, Python', 'modular, JavaScript', 'BigInt, Rust', 'BigInt, Python', 'BigInt, JavaScript'],
  nb.context.domiculeBenchmark.map(r => [
    `${r.rowCount}×${r.colCount}`,
    ...[r.languages.rs, r.languages.py, r.modular, r.bigintLanguages.rs, r.bigintLanguages.py, r.bigint].map(formatTime),
  ]),
);
print(`Run: ${nb.context.benchmarkRun}`);

Run: benchmarks/results/ee071e57836d-node26.11.1-python3.14.5-rust1.99.1

print(['A239264', 'A239273'].map(a => require('fs').readFileSync(require('path').join(nb.context.root, `oeis/${a}/${a}.gp`), 'utf-8').trim()).join('\n\n'));

\\ Domicule tilings of an h X w board (OEIS A239264) = perfect matchings of the king's graph.
\\ Broken-profile dynamic programming in row-major order: bit i of a state tells whether
\\ the cell i places ahead is covered; a free cell is matched right, down-left, down or down-right.
T(h, w) = {
  my(S = 2^(w+2), v = vector(S), u);
  if (h*w == 0, return(1));
  v[1] = 1;
  for (p = 0, h*w-1,
    my(r = p\w, c = p%w, d = []);
    if (c+1 < w, d = concat(d, 1));
    if (r+1 < h,
      if (c > 0, d = concat(d, w-1));
      d = concat(d, w);
      if (c+1 < w, d = concat(d, w+1)));
    u = vector(S);
    for (s = 0, S-1,
      my(x = v[s+1]);
      if (x,
        if (bitand(s, 1),
          u[(s>>1) + 1] += x,
          for (i = 1, #d, if (!bittest(s, d[i]), my(t = (s + 2^d[i])>>1); u[t+1] += x)))));
    v = u);
  v[1]
};

\\ Domicule tilings of a 2n X 2n board (OEIS A239273), with T(h, w) of A239264.gp read first.
a(n) = T(2*n, 2*n);