La toute nouvelle "belle" séquence OEIS, A328020 , vient d'être publiée il y a quelques minutes.

Nombre de pavages distincts d'un carré n X n avec des n-polyominos libres.

Cette séquence compte les pavages jusqu'aux symétries du carré. La séquence comporte six termes, mais j'aimerais voir si les gens ici peuvent la prolonger davantage.

Exemple

Car n=4il y a 22 grilles de ce type, comme le montre cette image de l'OEIS. Crédit: Jeff Bowermaster, illustration de A328020 (4).

Défi

Comme ce défi précédent , le but de ce défi est de calculer autant de termes que possible dans cette séquence, qui commence 1, 1, 2, 22, 515, 56734et où le n-ième terme est le nombre de pavages de la grille n X n avec des n-polyominos.

Exécutez votre code aussi longtemps que vous le souhaitez. Le gagnant de ce défi sera l'utilisateur qui publiera le plus de termes de la séquence, ainsi que son code pour le générer. Si deux utilisateurs affichent le même nombre de termes, celui qui affiche son dernier terme au plus tôt gagne.

Une extension du code @ Grimy obtient N = 8

Cela souligne simplement que @Grimy mérite la prime:

Je pourrais élaguer l'arbre de recherche en étendant le code pour vérifier, après chaque polyomino terminé, que l'espace libre restant n'est pas partitionné en composants de taille non divisible par N.

Sur une machine où le code d'origine prenait 2m11s pour N = 7, cela prend 1m4s, et N = 8 a été calculé en 33h46m. Le résultat est 23437350133.

Voici mon ajout en tant que diff:

--- tilepoly.c  2019-10-11 12:37:49.676351878 +0200
+++ tilepolyprune.c     2019-10-13 04:28:30.518736188 +0200
@@ -51,6 +51,30 @@
     return 1;
 } 

+static int check_component_sizes(u64 occupied, u64 total){
+    u64 queue[N*N];
+    while (total<N*N){
+        u64 count = 1;
+        u64 start = ctz(~occupied);
+        queue[0] = start;
+        occupied |= 1ul << start;
+        for(u64 current=0; current<count; ++current){
+            u64 free_adjacent = adjacency_matrix[queue[current]] & ~occupied;
+            occupied |= free_adjacent;
+            while (free_adjacent){
+                u64 next = ctz(free_adjacent);
+                free_adjacent &= ~(1ul << next);
+                queue[count++] = next;
+            }
+        }
+        if (count % N){
+            return 0;
+        }
+        total += count;
+    }
+    return 1;
+}
+
 static void recurse(u64 mino, u64 cell, u64 occupied, u64 adjacent, u64 forbidden)
 {
     if (cell >= N) {
@@ -61,6 +85,9 @@
             return;
         }

+        if(!check_component_sizes(occupied,N*mino))
+            return;
+
         u64 next = ctz(~occupied);
         board[next] = mino;
         recurse(mino, 1, occupied | 1ul << next, adjacency_matrix[next], 0);

Essayez-le en ligne!

C, 7 termes

Le septième terme est 19846102 . (Les six premiers sont 1, 1, 2, 22, 515, 56734, comme indiqué dans la 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);
}

Essayez-le en ligne! (pour N = 6, car N = 7 expirerait.)

Sur ma machine, N = 6 a pris 0,171 s et N = 7 a pris 2 min 23 s. N = 8 prendrait quelques semaines.