Número de bucles cerrados en una cuadrícula cuadrada.

Question

PREGUNTA: Dado un $m\times n$ cuadrícula de cuadrados, es una fórmula conocida por el número de bucles cerrados que se pueden extraer a lo largo de los perímetros de estas plazas? Para una mejor descripción de lo que quiero decir, consulte el enlace de abajo.

MOTIVACIÓN: he estado considerando el juego de rompecabezas de la "Slitherlink" en el que la solución al rompecabezas se compone de un circuito cerrado dibujados en una plaza de la celosía de la cuadrícula de satisfacer ciertas restricciones. Así, dado un $m\times n$ cuadrícula de cuadrados, me gustaría calcular el número de bucles cerrados que uno puede dibujar en esa red.

¿Alguien sabe de una fórmula que calcula esta, o un algoritmo que uno puede utilizar para determinar este número, en términos de $m,n$? Hay casos especiales que son más fáciles de determinar que otros? ¿Dónde puedo leer más acerca de este problema?

Un equivalente problema: dado un grafo $G$, ¿cómo se puede calcular el número de cíclico subdiagramas que contiene?

Answer 1

EDIT: me gustaría señalar que OEIS menciona más grande de todos los valores conocidos se encuentran por medio de un método de la matriz de transferencia. Por lo tanto, me gustaría creer que el algoritmo que os presentamos a continuación es asintóticamente muy cerca de la mejor algoritmo conocido.

Aquí está una $\mathcal{O}(f(n)^3\log m)$ tiempo de un algoritmo en donde $f(n)=\mathcal{O}(3^n/n)$. La idea es definir un $f(n)\times f(n)$ de la matriz de transición $M$ y calcular el $M^m$. Esto se lleva a $\mathcal{O}(f(n)^3\log m)$ tiempo usando el estándar de la multiplicación de la matriz del algoritmo, pero puede ser acelerado a $\mathcal{O}(f(n)^{2.807}\log m)$ utilizando el algoritmo de Strassen. Hay asintóticamente más rápido de la multiplicación de la matriz de algoritmos para la velocidad de este a $\mathcal{O}(f(n)^{2.373}\log m)$, pero no te molestes con eso.

Tenga en cuenta que esto significa que podemos calcular la respuesta de un $5\times 10^{18}$ red en cuestión de segundos, mientras que la respuesta de una $10\times10$ cuadrícula llevaría para siempre. Bastante divertido, si usted me pregunta :) Esto hace suponer que la multiplicación es una constante de tiempo de la operación, que está lejos de la verdad con tal de números grandes, a menos que sólo quieren saber de los últimos dígitos de la respuesta.

Así que la idea es utilizar una matriz de transición. El estado vamos a considerar es el conjunto de segmentos horizontales que el camino cerrado que se utiliza en un cierto tira. Considere la siguiente imagen.

El estado de este camino cerrado es $110110$ en la segunda columna y $111010$ en el cuarto. Lo que usted necesita hacer es definir una matriz de $M$ donde cada fila y cada columna representa un estado. La entrada en la fila $x$ y la columna de $y$ debe $1$ si se puede ir desde el estado de $y$ estado $x$ e $0$ lo contrario.

El punto de esta técnica es descrita por el siguiente hecho. La entrada en la fila $x$ y la columna de $y$ de $M^i$ es la cantidad de formas de pasar de un estado a$y$ estado $x$ en $i$ columnas. Esto concluye la teoría. El resto de la obra es en la implementación. Tomo nota de algunos muy importantes escollos para esta técnica.

Trampa 1: Usted podría tener los avisos de la púrpura estrellas en la imagen. El punto es que el conjunto de segmentos horizontales que el camino cerrado que se utiliza en un cierto tira no es suficiente información. Algunos segmentos horizontales se les permite ser combinado, mientras que otros no lo son. Esto es para evitar tener dos trazados cerrados separados cuentan como uno. En la imagen que dibujó estrellas entre los segmentos que no están permitidos para ser combinados. Usted necesita encontrar una manera de codificar esta en su estado.

Obstáculo 2: en Realidad el cálculo de $M$ no es fácil. Por ejemplo, tenga en cuenta que no se puede ir de un estado a$1100$ estado $0011$ porque vertical de los segmentos de línea se deben cruzar.

Trampa 3: Para evitar el contagio de dos trazados cerrados separados, usted también necesitará dos estados. Un inicio y un final. Ambos tienen ninguna línea horizontal segmentos, pero necesitan ser distinguidos entre a prevenir el contagio de dos trazados cerrados separados. Para leer la respuesta final, con tan sólo mirar en la entrada de $M^m$ al inicio de la fila y el estado final de la columna.

Answer 2

El número de ciclos con una longitud exacta de $n$, el significado y la altura máxima de 2 es este:

$$ S(n,2) = 1 + \sum_{m=1}^n \sum_{k=1}^m \binom{n-m-k+1}{k}\binom{m}{k} \cdot 2^k $$

Aquí, $m$ representa el número de columnas con 1 plaza en ellos, y $k$ representa el número de grupos de columnas que tiene 1 plaza de ellos. Es muy reminiscencia de multichoose, excepto que hay dos opciones para cada grupo de columnas (cualquiera de las plazas están en la parte inferior, o superior).

Por lo tanto, para el número total de ciclos en un $n \times 2$ junta:

$$ f(n,2) =\sum_{i=1}^n (n-i+1) \cdot S(i,2) $$

$S(n,3)$ es donde las cosas se ponen feas. Básicamente, considerar cada posible configuración de columnas con tres plazas que en ellas, y luego calcular el número de posibles formas de conectar estas columnas sin necesidad de crear otra en el medio. Me gustaría sugerir una fórmula recursiva depende de las plazas visible en uno de los extremos. Deje $g(n,3)(b,b,b)$ el número de ciclos con el ancho exacto $n$, y la segunda parte es binario condiciones en donde o no la $j$-ésimo mayor de la plaza en la columna de la derecha está en el ciclo. La recursividad es algo como esto:

$$ g(n,3)(1,0,0) = g(n-1,3)(1,1,1)+g(n-1,3)(1,1,0) $$

También nos gustaría que desee incluir una cláusula acerca de la $g(n,3)(1,0,1)$, que sorta de lo que depende de los ciclos están permitidos.