Jumlah kemiringan berbeda dari n X n persegi dengan n-poliomino gratis

17

Urutan OEIS "bagus" terbaru , A328020 , baru saja diterbitkan beberapa menit yang lalu.

Jumlah kemiringan berbeda dari n X n persegi dengan n-poliomino gratis.

Urutan ini menghitung kemiringan hingga simetri persegi. Urutannya memiliki enam istilah, tetapi saya ingin melihat apakah orang-orang di sini dapat memperpanjangnya.

Contoh

Karena n=4ada 22 kotak seperti itu, seperti yang ditunjukkan dalam gambar ini dari OEIS. Kredit: Jeff Bowermaster, Ilustrasi A328020 (4).A328020 (4)

Tantangan

Seperti tantangan sebelumnya , tujuan dari tantangan ini adalah untuk menghitung sebanyak mungkin istilah dalam urutan ini, yang dimulai 1, 1, 2, 22, 515, 56734dan di mana istilah ke-n adalah jumlah kemiringan kotak n X n dengan n-polyomino.

Jalankan kode Anda selama yang Anda inginkan. Pemenang dari tantangan ini adalah pengguna yang memposting sebagian besar syarat urutan, bersama dengan kode mereka untuk menghasilkannya. Jika dua pengguna memposting jumlah istilah yang sama, maka siapa pun yang memposting istilah terakhir mereka yang paling awal akan menang.

Peter Kagey
sumber
3
Jadi ini simetri modulo dari bujur sangkar?
Peter Taylor
@ PeterTaylor, itu benar. Saya sudah merancukan ini dalam pertanyaan.
Peter Kagey
Secara naif saya akan mengatakan bahwa entri ke- n akan mengambil operasi number_of_fixed_n_polyominoes ^ ( n -1) untuk menghitung. Jadi untuk n = 7, itu akan mengambil 760 ^ 6 ≈ 2 ^ 57,4 operasi. Anda mungkin dapat mengurangi itu banyak, tetapi ini adalah angka yang besar untuk memulai dengan ...
G. Sliepen
@ Slepen, saya berharap Anda dapat mengurangi itu dengan cukup banyak hanya dengan mundur. Secara khusus, ada banyak dari polinomial tetap yang tidak dapat ditempatkan di sudut, dan sekali polyomino valid adalah ditempatkan di suatu tempat, itu sangat membatasi apa yang dapat ditempatkan di sebelahnya.
Peter Kagey
@ PeterKagey, Anda benar. Saya kira itu membantu jika, mengingat bahwa Anda telah menempatkan m-polyomino, Anda memilih posisi berikutnya untuk mencoba menempatkan polyomino di posisi yang paling buruk, sehingga Anda dapat mengurangi banyak.
G. Sliepen

Jawaban:

9

Perpanjangan ke kode @ Grimy mendapat N = 8

Ini hanya menggarisbawahi bahwa @Grimy layak mendapatkan hadiah:

Saya dapat memangkas pohon pencarian dengan memperluas kode untuk memeriksa, setelah setiap selesai polyomino, bahwa ruang kosong yang tersisa tidak dipartisi menjadi komponen ukuran yang tidak dapat dibagi oleh N.

Pada mesin di mana kode asli mengambil 2m11s untuk N = 7, ini membutuhkan 1m4s, dan N = 8 dihitung dalam 33h46m. Hasilnya adalah 23437350133.

Inilah tambahan saya sebagai 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);

Cobalah online!

Sievers Kristen
sumber
Ini sangat bagus.
Anush
Yang kita butuhkan sekarang adalah versi simd multithreaded :)
Anush
1
Oh, itu sangat keren! Saya sebenarnya mempertimbangkan optimasi ini, tetapi tidak berpikir itu akan cukup untuk mencapai N = 8 dalam waktu yang masuk akal, jadi saya tidak repot-repot mengimplementasikannya.
Grimmy
14

C, 7 term

Istilah ketujuh adalah 19846102 . (Enam yang pertama adalah 1, 1, 2, 22, 515, 56734, sebagaimana dinyatakan dalam pertanyaan).

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

Cobalah online! (untuk N = 6, karena N = 7 akan habis.)

Di mesin saya, N = 6 mengambil 0,171s, dan N = 7 mengambil 2m23s. N = 8 akan memakan waktu beberapa minggu.

Grimmy
sumber
3
Ini luar biasa! Beri tahu saya jika Anda ingin menambahkannya ke OEIS — yang mungkin menyebabkan Anda melakukan xxx sendiri — atau jika Anda ingin saya menambahkannya.
Peter Kagey
@PeterKagey Silakan menambahkannya (:
Grimmy
Fungsi check_symmetry yang menarik. Bisakah Anda memberikan penjelasan singkat karena saya tidak terbiasa dengan pendekatan itu?
John Rees
1
@ JohnRees Ini hanya menguji bahwa papan saat ini adalah leksikografis ≤ untuk semua simetri. Jadi dalam setiap set papan simetris, tepat satu dihitung: minimum leksikografis.
Grimmy
Untuk melakukan lebih baik daripada menghitung satu per satu solusi, diperlukan semacam pertemuan. Masalahnya adalah bahwa tampaknya tidak ada cara untuk memecah hal-hal yang mendapat pengelompokan yang signifikan. Misalnya menggunakan pemesanan kanonik yang sama dengan jawaban ini, menempatkan 3 hexomino Saya mendapatkan rata-rata sekitar 3,7 set hexominos per topeng. Saya menyimpulkan bahwa pendekatan ini tidak mungkin dikalahkan.
Peter Taylor