Количество различных углов n x n квадрата со свободными n-polyominoes

17

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

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

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

пример

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

Вызов

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

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

Питер Кейджи
источник
3
Так это по модулю симметрии квадрата?
Питер Тейлор,
@PeterTaylor, это верно. Я сделал это неоднозначным в этом вопросе.
Питер Кейджи
Наивно я бы сказал, что для n-й записи потребуются операции number_of_fixed_n_polyominoes ^ ( n -1). Таким образом, для n = 7 это заняло бы 760 ^ 6 ≈ 2 ^ 57,4 операций. Вы, вероятно, можете сократить это много, но это большое число, чтобы начать с ...
G. Sliepen
@ Слипен, я ожидаю, что вы можете значительно сократить это, просто вернувшись назад. В частности, есть много постоянных полиномы , которые не могут быть размещены в угле, и когда действительный Полимин будет размещен где - то, это очень ограничивает то , что может быть помещено рядом с ним.
Питер Кейджи
@PeterKagey, ты прав. Я думаю, это поможет, если, учитывая, что вы уже разместили m n-polyominoes, вы выбираете следующую позицию, чтобы попытаться поместить polyomino в наихудшую возможную позицию, что вы можете сильно ее сократить.
Г. Слипен

Ответы:

9

Расширение кода @ 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);

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

Кристиан Сиверс
источник
Это очень мило.
Ануш
Все, что нам сейчас нужно, это многопоточная версия
Anush
1
О, это действительно круто! Я действительно рассматривал эту оптимизацию, но не думал, что ее будет достаточно, чтобы достичь N = 8 за разумное время, поэтому я не стал ее реализовывать.
Grimmy
14

С, 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 займет несколько недель.

Grimmy
источник
3
Это замечательно! Дайте мне знать, если вы хотите добавить его в OEIS - что может привести к тому, что вы сами сделаете это, - или если вы хотите, чтобы я его добавил.
Питер Кейджи
@PeterKagey Пожалуйста , не стесняйтесь , чтобы добавить его (:
Grimmy
Увлекательная функция check_symmetry. Не могли бы вы дать краткое объяснение, так как я не знаком с подходом?
Джон Рис
1
@JohnRees Это просто проверяет, что текущая доска лексикографически ≤ для всех его симметрий. Таким образом, в любом наборе симметричных досок учитывается ровно одно: лексикографический минимум.
Grimmy
Чтобы сделать лучше, чем перечислять решения одно за другим, требуется некоторая встреча в середине. Проблема в том, что, кажется, нет никакого способа разделить вещи, которые получают значительную кластеризацию. Например, используя тот же канонический порядок, что и в этом ответе, размещая 3 гексомино, я получаю в среднем около 3,7 наборов гексомино на маску. Я пришел к выводу, что этот подход вряд ли будет побежден.
Питер Тейлор