Liczba wyraźnych nachyleń kwadratu n X n z wolnymi n-poliominoami

17

Najnowsza „ładna” sekwencja OEIS, A328020 , została właśnie opublikowana kilka minut temu.

Liczba wyraźnych nachyleń kwadratu n X n z wolnymi n-poliominoami.

Ta sekwencja zlicza przechylenia do symetrii kwadratu. Sekwencja ma sześć terminów, ale chciałbym sprawdzić, czy ludzie tutaj mogą ją jeszcze rozszerzyć.

Przykład

Ponieważ n=4istnieją 22 takie siatki, jak pokazano na tym obrazie z OEIS. Źródło: Jeff Bowermaster, ilustracja A328020 (4).A328020 (4)

Wyzwanie

Podobnie jak w poprzednim wyzwaniu , celem tego wyzwania jest obliczenie jak największej liczby terminów w tej sekwencji, która zaczyna się 1, 1, 2, 22, 515, 56734i gdzie n-ty składnik jest liczbą nachyleń siatki n X n za pomocą n-poliominoów.

Uruchom kod tak długo, jak chcesz. Zwycięzcą tego wyzwania będzie użytkownik, który opublikuje najwięcej terminów sekwencji wraz ze swoim kodem do jej wygenerowania. Jeśli dwóch użytkowników opublikuje tę samą liczbę warunków, wygrywa ten, kto opublikuje swój ostatni termin najwcześniej.

Peter Kagey
źródło
3
Czy to modulo symetrie kwadratu?
Peter Taylor,
@PeterTaylor, zgadza się. Ujednoznaczniłem to w pytaniu.
Peter Kagey,
To naiwny powiedzieć, że n'th wejście zajęłoby number_of_fixed_n_polyominoes ^ ( n -1) operacje Oblicz. Tak więc dla n = 7 zajęłoby to 760 ^ 6 ≈ 2 ^ 57,4 operacji. Prawdopodobnie możesz to znacznie zmniejszyć, ale na początek jest to duża liczba ...
G. Sliepen
@Sliepen, spodziewam się, że możesz to znacznie zmniejszyć, cofając się. W szczególności istnieje wiele stałych wielomianów, których nie można umieścić w rogu, a gdy gdzieś zostanie umieszczony prawidłowy poliomino , ogromnie ogranicza to, co można umieścić obok niego.
Peter Kagey,
@PeterKagey, masz rację. Wydaje mi się, że to pomaga, jeśli biorąc pod uwagę, że już umieściłeś m-poliominoes, wybierasz następną pozycję, aby spróbować umieścić poliomino w najgorszej możliwej pozycji, że możesz go znacznie zmniejszyć.
G. Sliepen

Odpowiedzi:

9

Rozszerzenie kodu @ Grimy otrzymuje N = 8

To tylko podkreśla, że ​​@Grimy zasługuje na nagrodę:

Mogę przycinać drzewo wyszukiwania, rozszerzając kod, aby sprawdzić, po każdym zakończonym poliomino, czy pozostała wolna przestrzeń nie jest podzielona na komponenty o rozmiarze niepodzielnym przez N.

Na komputerze, na którym oryginalny kod zajął 2m11s dla N = 7, zajmuje to 1m4s, a N = 8 obliczono w 33h46m. Wynik to 23437350133.

Oto mój dodatek jako 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);

Wypróbuj online!

Christian Sievers
źródło
To jest bardzo miłe.
Anush,
Teraz potrzebujemy tylko wielowątkowej wersji SIMD :)
Anush,
1
Och, to naprawdę fajne! Właściwie zastanawiałem się nad tą optymalizacją, ale nie sądziłem, że wystarczy osiągnąć N = 8 w rozsądnym czasie, więc nie zawracałem sobie głowy jej implementacją.
Grimmy,
14

C, 7 warunków

Siódma kadencja to 19846102 . (Pierwsze sześć to 1, 1, 2, 22, 515, 56734, jak stwierdzono w pytaniu).

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

Wypróbuj online! (dla N = 6, ponieważ N = 7 przekroczyłoby limit czasu).

Na mojej maszynie N = 6 zajęło 0,171 s, a N = 7 zajęło 2m23 s. N = 8 zajęłoby kilka tygodni.

Ponury
źródło
3
To wspaniale! Daj mi znać, jeśli chcesz dodać go do OEIS - co może spowodować, że sam się zorientujesz - lub jeśli chcesz, żebym go dodał.
Peter Kagey,
@PeterKagey Nie krępuj się dodać (:
Grimmy,
Fascynująca funkcja check_symmetry. Czy mógłbyś podać krótkie wyjaśnienie, ponieważ nie znam tego podejścia?
John Rees,
1
@JohnRees To po prostu sprawdza, czy bieżąca tablica jest leksykograficznie ≤ do wszystkich symetrii. Tak więc w każdym zestawie tablic symetrycznych liczona jest dokładnie jedna: minimum leksykograficzne.
Grimmy,
1
Aby zrobić coś lepszego niż wyliczanie rozwiązań jeden po drugim, wymagany jest pewien rodzaj spotkania w środku. Problem polega na tym, że wydaje się, że nie ma żadnego sposobu na podzielenie rzeczy, które ulegają znacznemu skupieniu. Np. Używając tego samego uporządkowania kanonicznego co ta odpowiedź, umieszczając 3 heksominoe, otrzymuję średnio około 3,7 zestawów heksomino na maskę. Stwierdzam, że takie podejście prawdopodobnie nie zostanie pokonane.
Peter Taylor