Número de inclinaciones distintas de un cuadrado n X n con n-polyominoes libres

17

La secuencia OEIS "agradable" más nueva , A328020 , se acaba de publicar hace unos minutos.

Número de inclinaciones distintas de un n X n cuadrado con n-polyominoes libres.

Esta secuencia cuenta las inclinaciones hasta las simetrías del cuadrado. La secuencia tiene seis términos, pero me gustaría ver si la gente aquí puede extenderla más.

Ejemplo

Para n=4hay 22 tales rejillas, como se muestra en esta imagen de la OEIS. Crédito: Jeff Bowermaster, Ilustración de A328020 (4).A328020 (4)

Desafío

Al igual que este desafío anterior , el objetivo de este desafío es calcular tantos términos como sea posible en esta secuencia, que comienza 1, 1, 2, 22, 515, 56734y donde el enésimo término es el número de inclinaciones de la cuadrícula n X n con n-poliominós.

Ejecute su código durante el tiempo que desee. El ganador de este desafío será el usuario que publique la mayor cantidad de términos de la secuencia, junto con su código para generarlo. Si dos usuarios publican el mismo número de términos, gana el que publique su último término más temprano.

Peter Kagey
fuente
3
Entonces, ¿esta es la simetría del módulo del cuadrado?
Peter Taylor
@PeterTaylor, eso es correcto. He desambiguado esto en la pregunta.
Peter Kagey
Ingenuamente, diría que la enésima entrada requeriría operaciones number_of_fixed_n_polyominoes ^ ( n -1) para calcular. Entonces, para n = 7, eso requeriría 760 ^ 6 ≈ 2 ^ 57.4 operaciones. Probablemente puedas reducir eso mucho, pero es un gran número para empezar ...
G. Sliepen
@Sliepen, espero que puedas reducir eso bastante solo retrocediendo. En particular, hay muchos polinomios fijos que no se pueden colocar en la esquina, y una vez que se coloca un poliomino válido en algún lugar, limita enormemente lo que se puede colocar al lado.
Peter Kagey
@ PeterKagey, tienes razón. Supongo que ayuda si, dado que ya has colocado m n-polyominoes, eliges la siguiente posición para tratar de colocar un poliomino en la peor posición posible, que puedes cortarlo mucho.
G. Sliepen

Respuestas:

9

Una extensión del código de @ Grimy obtiene N = 8

Esto solo subraya que @Grimy merece la recompensa:

Podría podar el árbol de búsqueda extendiendo el código para verificar, después de cada poliomino terminado, que el espacio libre restante no está dividido en componentes de tamaño no divisible por N.

En una máquina donde el código original tomó 2m11s para N = 7, esto toma 1m4s, y N = 8 se calculó en 33h46m. El resultado es 23437350133.

Aquí está mi adición como una diferencia:

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

Pruébalo en línea!

Christian Sievers
fuente
Esto esta muy bien.
Anush
Todo lo que necesitamos ahora es una versión simd multiproceso :)
Anush
1
¡Oh, eso es genial! De hecho, consideré esta optimización, pero no pensé que sería suficiente para alcanzar N = 8 en un tiempo razonable, por lo que no me molesté en implementarla.
Grimmy
14

C, 7 términos

El séptimo término es 19846102 . (Los primeros seis son 1, 1, 2, 22, 515, 56734, como se indica en la pregunta).

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

Pruébalo en línea! (para N = 6, ya que N = 7 caducaría).

En mi máquina, N = 6 tomó 0.171s, y N = 7 tomó 2m23s. N = 8 tomaría algunas semanas.

Mugriento
fuente
3
¡Esto es maravilloso! Avíseme si desea agregarlo al OEIS, lo que podría provocar que usted mismo se moleste, o si desea que lo agregue.
Peter Kagey
@PeterKagey Por favor, siéntase libre de agregarlo (:
Grimmy
Fascinante función check_symmetry. ¿Podría dar una breve explicación ya que no estoy familiarizado con el enfoque?
John Rees
1
@ JohnRees Simplemente prueba que el tablero actual es lexicográficamente ≤ a todas sus simetrías. Así, en cualquier conjunto de tableros simétricos, se cuenta exactamente uno: el mínimo lexicográfico.
Grimmy
Para hacerlo mejor que enumerar las soluciones una por una, se requiere algún tipo de reunión en el medio. El problema es que no parece haber ninguna forma de dividir las cosas que se agrupan significativamente. Por ejemplo, usando el mismo orden canónico que esta respuesta, colocando 3 hexominoes obtengo un promedio de aproximadamente 3.7 juegos de hexominos por máscara. Concluyo que este enfoque no es probable que sea mejor.
Peter Taylor