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

17

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).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.

Peter Kagey
la source
3
Il s'agit donc de symétries modulo du carré?
Peter Taylor
@PeterTaylor, c'est vrai. J'ai mis l'ambiguïté dans la question.
Peter Kagey
Naïvement , je dirais que l'entrée n'th prendrait number_of_fixed_n_polyominoes ^ ( n opérations -1) pour calculer. Donc pour n = 7, cela prendrait 760 ^ 6 ≈ 2 ^ 57,4 opérations. Vous pouvez probablement réduire cela beaucoup, mais c'est un grand nombre pour commencer ...
G. Sliepen
@Sliepen, je pense que vous pouvez réduire cela de beaucoup en reculant. En particulier, il y a beaucoup de polynômes fixes qui ne peuvent pas être placés dans le coin, et une fois qu'un polyomino valide est placé quelque part, il contraint énormément ce qui peut être placé à côté de lui.
Peter Kagey
@PeterKagey, vous avez raison. Je suppose que cela aide si, étant donné que vous avez déjà placé m n-polyominos, vous choisissez la position suivante pour essayer de placer un polyomino dans la pire position possible, que vous pouvez le réduire beaucoup.
G. Sliepen

Réponses:

9

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!

Christian Sievers
la source
C'est très gentil.
Anush
Tout ce dont nous avons besoin maintenant est une version simd multithread :)
Anush
1
Oh c'est vraiment cool! En fait, j'ai envisagé cette optimisation, mais je ne pensais pas que ce serait suffisant pour atteindre N = 8 dans un délai raisonnable, donc je n'ai pas pris la peine de l'implémenter.
Grimmy
14

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.

Grimmy
la source
3
C'est magnifique! Faites-moi savoir si vous souhaitez l'ajouter à l'OEIS - ce qui pourrait vous amener à faire du doxxing - ou si vous souhaitez que je l'ajoute.
Peter Kagey
@PeterKagey N'hésitez pas à l'ajouter (:
Grimmy
Fonction fascinante de check_symmetry. Pourriez-vous s'il vous plaît donner une brève explication car je ne connais pas l'approche?
John Rees
1
@JohnRees Il teste simplement que la carte actuelle est lexicographiquement ≤ à toutes ses symétries. Ainsi dans tout ensemble de planches symétriques, exactement une est comptée: le minimum lexicographique.
Grimmy
Pour faire mieux que d'énumérer les solutions une par une, une sorte de rencontre entre les deux est nécessaire. Le problème est qu'il ne semble pas y avoir de moyen de diviser les choses qui obtient un regroupement significatif. Par exemple, en utilisant le même ordre canonique que cette réponse, en plaçant 3 hexominos, j'obtiens en moyenne environ 3,7 ensembles d'hexominos par masque. Je conclus que cette approche n'est pas susceptible d'être battue.
Peter Taylor