Новейшая «хорошая» последовательность OEIS, A328020 , была опубликована несколько минут назад.

Число различных мозаичных элементов квадрата n X n со свободными n-polyominoes.

Эта последовательность подсчитывает наклоны до симметрий квадрата. Последовательность состоит из шести терминов, но я хотел бы посмотреть, могут ли люди здесь расширить это.

пример

Поскольку n=4есть 22 таких сетки, как показано на этом изображении из OEIS. Предоставлено: Джефф Бауэрмастер, Иллюстрация A328020 (4).

Вызов

Как и эта предыдущая задача , цель этой задачи состоит в том, чтобы вычислить как можно больше терминов в этой последовательности, которая начинается, 1, 1, 2, 22, 515, 56734и где n-й член - это число мозаичных элементов сетки n X n с n-polyomino.

Запустите ваш код столько, сколько захотите. Победителем этого конкурса станет пользователь, который отправит большинство терминов последовательности вместе со своим кодом для ее генерации. Если два пользователя публикуют одинаковое количество терминов, выигрывает тот, кто публикует свой последний термин раньше всех.

Расширение кода @ Grimy получает N = 8

Это только подчеркивает, что @Grimy заслуживает награды:

Я мог бы обрезать дерево поиска, расширив код, чтобы после каждого готового polyomino проверять, что оставшееся свободное пространство не разбивается на компоненты размера, не делимого на N.

На машине, где исходный код занял 2m11s для N = 7, это занимает 1m4s, а N = 8 было вычислено за 33h46m. Результат 23437350133.

Вот мое дополнение как 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);

Попробуйте онлайн!

С, 7 сроков

Седьмой срок - 19846102 . (Первые шесть - 1, 1, 2, 22, 515, 56734, как указано в вопросе).

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

Попробуйте онлайн! (для N = 6, так как время N = 7 истекло бы.)

На моей машине N = 6 заняло 0,171 с, а N = 7 заняло 2 м23 с. N = 8 займет несколько недель.