C, 7 terms
The seventh term is 19846102. (The first six are 1, 1, 2, 22, 515, 56734, as stated in the question).
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#define N 7
#define ctz __builtin_ctzl
typedef uint64_t u64;
static u64 board[N*N] = { 0 };
static u64 adjacency_matrix[N*N] = { 0 };
static u64 count = 0;
static u64 check_symmetry()
{
static const u64 symmetries[7][3] = {
{ 0, +N, +1 },
{ N-1, -1, +N },
{ N-1, +N, -1 },
{ N*N-1, -1, -N },
{ N*N-1, -N, -1 },
{ N*N-N, +1, -N },
{ N*N-N, -N, +1 },
};
int order[N];
for (u64 i = 0; i < 7; ++i) {
u64 start = symmetries[i][0];
u64 dcol = symmetries[i][1];
u64 drow = symmetries[i][2];
memset(order, 0xFF, N*sizeof(int));
for (u64 row = 0, col = 0; col < N || (col = 0, ++row < N); ++col) {
u64 base = board[col + N*row];
u64 symmetry = board[start + dcol*col + drow*row];
u64 lex = 0;
while (order[lex] != symmetry && order[lex] != -1)
++lex;
order[lex] = symmetry;
if (lex < base)
return 0;
if (base < lex)
break;
}
}
return 1;
}
static void recurse(u64 mino, u64 cell, u64 occupied, u64 adjacent, u64 forbidden)
{
if (cell >= N) {
++mino;
if (mino == N) {
count += check_symmetry();
return;
}
u64 next = ctz(~occupied);
board[next] = mino;
recurse(mino, 1, occupied | 1ul << next, adjacency_matrix[next], 0);
return;
}
adjacent &= ~occupied & ~forbidden;
while (adjacent) {
u64 next = ctz(adjacent);
adjacent &= ~(1ul << next);
forbidden |= 1ul << next;
board[next] = mino;
recurse(mino, cell + 1, occupied | 1ul << next, adjacent | adjacency_matrix[next], forbidden);
}
}
int main(void)
{
for (u64 i = 0; i < N*N; ++i) {
if (i % N)
adjacency_matrix[i] |= 1ul << (i - 1);
if (i / N)
adjacency_matrix[i] |= 1ul << (i - N);
if (i % N != N - 1)
adjacency_matrix[i] |= 1ul << (i + 1);
if (i / N != N - 1)
adjacency_matrix[i] |= 1ul << (i + N);
}
recurse(0, 2, 3, 4 | 3 << N, 0);
printf("%ld\n", count);
}
Try it online! (for N=6, since N=7 would time out.)
On my machine, N=6 took 0.171s, and N=7 took 2m23s. N=8 would take a few weeks.
3So this is modulo symmetries of the square? – Peter Taylor – 2019-10-08T08:59:08.510
@PeterTaylor, that's right. I've disambiguated this in the question. – Peter Kagey – 2019-10-08T17:34:21.410
Naively I would say that the n'th entry would take number_of_fixed_n_polyominoes^(n-1) operations to calculate. So for n = 7, that would take 760^6 ≈ 2^57.4 operations. You can probably cut that down a lot, but it's a big number to start with...
– G. Sliepen – 2019-10-08T17:49:54.247@Sliepen, I expect that you can cut down that by quite a lot just by backtracking. In particular, there are a lot of fixed polynomials that can't be placed in the corner, and once a valid polyomino is placed somewhere, it hugely constrains what can be placed next to it. – Peter Kagey – 2019-10-08T17:58:15.783
@PeterKagey, you're right. I guess it helps if, given that you already have placed m n-polyominoes, you choose the next position to try to place a polyomino in the worst possible position, that you can cut it down a lot. – G. Sliepen – 2019-10-08T18:22:19.857