Anzahl der unterschiedlichen Kacheln eines n x n Quadrats mit freien n-Polyominoen

17

Die neueste "nette" OEIS-Sequenz, A328020 , wurde vor wenigen Minuten veröffentlicht.

Anzahl der unterschiedlichen Kacheln eines n x n Quadrats mit freien n-Polyominoen.

Diese Sequenz zählt Kacheln bis zu Symmetrien des Quadrats. Die Sequenz besteht aus sechs Begriffen, aber ich würde gerne sehen, ob die Leute hier sie noch erweitern können.

Beispiel

Denn n=4es gibt 22 solcher Gitter, wie in diesem Bild aus dem OEIS gezeigt. A328020 (4) Bildnachweis: Jeff Bowermaster, Illustration von A328020 (4).

Herausforderung

Wie bei dieser vorherigen Herausforderung besteht das Ziel dieser Herausforderung darin, so viele Terme wie möglich in dieser Sequenz zu berechnen, die beginnt1, 1, 2, 22, 515, 56734 und bei der der n-te Term die Anzahl der Kacheln des n x n-Gitters mit n-Polyominoen ist.

Führen Sie Ihren Code so lange aus, wie Sie möchten. Der Gewinner dieser Herausforderung ist der Benutzer, der die meisten Begriffe der Sequenz zusammen mit seinem Code zum Generieren veröffentlicht. Wenn zwei Benutzer die gleiche Anzahl von Begriffen veröffentlichen, gewinnt derjenige, der seinen letzten Begriff frühestens veröffentlicht.

Peter Kagey
quelle
3
Das sind also Modulo-Symmetrien des Quadrats?
Peter Taylor
@PeterTaylor, das stimmt. Ich habe dies in der Frage klargestellt.
Peter Kagey
Naiv würde ich sagen, dass der n- te Eintrag eine Anzahl_von_fixierten_n_Polyominoes ^ ( n- 1) -Operationen benötigt, um zu berechnen. Für n = 7 würde das also 760 ^ 6 ≈ 2 ^ 57.4 Operationen erfordern. Sie können das wahrscheinlich viel reduzieren, aber es ist eine große Zahl, um damit zu beginnen ...
G. Sliepen
@Sliepen, ich gehe davon aus, dass du das durch Backtracking um einiges reduzieren kannst. Insbesondere gibt es eine Menge von festen Polynomen , die nicht in der Ecke platziert werden können, und sobald eine gültige polyomino ist irgendwo platziert, zwingt es enorm , was neben ihm platziert werden kann.
Peter Kagey
@ PeterKagey, du hast recht. Ich denke, es hilft, wenn Sie, da Sie bereits m n-Polyominoes platziert haben, die nächste Position wählen, um zu versuchen, ein Polyomino in die schlechtestmögliche Position zu platzieren, damit Sie es viel kürzen können.
G. Sliepen

Antworten:

9

Eine Erweiterung von @ Grimys Code erhält N = 8

Dies unterstreicht nur, dass @Grimy das Kopfgeld verdient:

Ich könnte den Suchbaum beschneiden, indem ich den Code erweitere, um nach jedem fertigen Polyomino zu überprüfen, ob der verbleibende freie Speicherplatz nicht in durch N nicht teilbare Größenkomponenten unterteilt ist.

Auf einer Maschine, auf der der ursprüngliche Code 2 Minuten und 11 Sekunden für N = 7 benötigte, dauert dies 1 Minute und 4 Sekunden, und N = 8 wurde in 33 Stunden und 46 Minuten berechnet. Das Ergebnis ist 23437350133.

Hier ist mein Zusatz als 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);

Probieren Sie es online!

Christian Sievers
quelle
Das ist sehr nett.
Anush
Alles was wir jetzt brauchen ist eine Multithread-Simd-Version :)
Anush
1
Oh das ist echt cool! Ich habe diese Optimierung tatsächlich in Betracht gezogen, aber nicht gedacht, dass es ausreichen würde, um N = 8 in einer vernünftigen Zeit zu erreichen, also habe ich mich nicht darum gekümmert, sie zu implementieren.
Grimmy
14

C, 7 Glieder

Die siebte Amtszeit ist 19846102 . (Die ersten sechs sind 1, 1, 2, 22, 515, 56734, wie in der Frage angegeben).

#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);
}

Probieren Sie es online!(Für N = 6, da N = 7 eine Zeitüberschreitung verursachen würde.)

Auf meinem Computer dauerte N = 6 0,171 s und N = 7 2 m23 s. N = 8 würde einige Wochen dauern.

Grimmig
quelle
3
Das ist wunderbar! Lassen Sie mich wissen, ob Sie es dem OEIS hinzufügen möchten - was dazu führen kann, dass Sie sich selbst doxxen - oder ob ich es hinzufügen soll.
Peter Kagey
@ PeterKagey Bitte zögern Sie nicht, es hinzuzufügen (:
Grimmy
Faszinierende check_symmetry Funktion. Könnten Sie bitte eine kurze Erklärung geben, da ich mit der Vorgehensweise nicht vertraut bin?
John Rees
1
@JohnRees Es wird lediglich geprüft, ob die aktuelle Karte lexikografisch ≤ zu allen Symmetrien ist. Somit wird in jedem Satz symmetrischer Tafeln genau eine gezählt: das lexikografische Minimum.
Grimmy
Um es besser zu machen, als die Lösungen einzeln aufzulisten, ist eine Art Meet-in-the-Middle erforderlich. Das Problem ist, dass es keine Möglichkeit zu geben scheint, Dinge aufzuteilen, die eine signifikante Clusterbildung bewirken. ZB mit der gleichen kanonischen Reihenfolge wie diese Antwort, wenn ich 3 Hexominos platziere, erhalte ich durchschnittlich etwa 3,7 Sätze Hexominos pro Maske. Ich komme zu dem Schluss, dass dieser Ansatz wahrscheinlich nicht zu übertreffen ist.
Peter Taylor