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

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.

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!

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.