¿Cuál es el número mínimo de piezas de lego necesarias para completar un laberinto NxN y también cuál es el número total de configuraciones correspondientes?

Question

Sólo debe haber un camino entre dos celdas vacías y cualquier celda vacía debe ser accesible desde cualquier otra celda vacía.

(en todos los ejemplos siguientes, "x" indica la posición del lego y "0" la celda vacía)

Por ejemplo, para N=2, el número mínimo de lego necesario es uno

0 0
0 x

o

0 0
x 0

o

0 x
0 0

o

x 0
0 0

Así que para N=2, la respuesta es un mínimo de 1 lego y 4 configuraciones.

Para N=3, algunas de las configuraciones son

0 0 0
0 x 0
0 0 x

o

0 0 0
0 x x
0 0 0

o

0 0 0
x 0 x
0 0 0

hay 7 más de tales configuraciones en total(nótese que las reflexiones y rotaciones de las 3 anteriores pueden generar las 7 configuraciones restantes). Así que para N=3 la respuesta es un mínimo de 2 legos y 10 configuraciones.

¿Cuál es la respuesta de N=13?

Mi pensamiento inicial fue encontrar si hay algún patrón en las series, las series para configuraciones generadas para N=1 a 5 son 0,4,10,32,22 pero buscando en OEIS no me dio nada útil, por otro lado las series para mínimo 0,1,2,4,6 son demasiado comunes.

Editar - Se trata de un problema informático. El planteador del problema no espera un $O(1)$ fórmula. Un enfoque algorítmico mejor o igual a $O(N^6)$ debería ser suficiente.

Answer 1

No tengo una respuesta para todos $N$ pero tengo una respuesta óptima demostrable siempre que $N$ es uno más que una potencia de dos, y algunos límites superior e inferior que están bastante cerca.

Consideremos el grafo cuyos vértices son las celdas, donde dos celdas están unidas por una arista si son ortogonalmente adyacentes. Al rellenar una celda con un bloque de Lego se elimina un vértice y todas las aristas que inciden en ese vértice. El objetivo es eliminar suficientes vértices y aristas para que el grafo que quede sea un árbol. Inicialmente, el número de vértices y aristas viene dado por $$ |V|=N^2,\qquad |E|=2N(N-1), $$ por lo que inicialmente la diferencia entre $|E|$ y $|V|$ es $N^2-2N$ . Además, la colocación de cada bloque disminuirá $|V|$ en exactamente uno, y disminuir $|E|$ por un máximo de $4$ por lo que disminuirá $|E|-|V|$ por un máximo de $3$ . Para que un grafo sea un árbol, la diferencia $|E|-|V|$ debe ser exactamente $-1$ . Por lo tanto, el número de bloques debe ser como mínimo de $$ \frac{N^2-2N-(-1)}{3}=\frac{(N-1)^2}{3} $$ Para conseguirlo, cada bloque colocado tendría que disminuir $|E|-|V|$ por $3$ lo que significa que cada bloque debe estar en el interior de la cuadrícula y no adyacente a ningún otro bloque. Sin embargo, siempre debe haber al menos un bloque en el exterior, ya que de lo contrario se produciría un ciclo alrededor del perímetro. Por lo tanto, hemos demostrado que $$ \text{# blocks}\ge \left\lceil \frac{(N-1)^2+1}{3}\right \rceil $$ Además, siempre que $N$ es uno más que una potencia de dos, digamos $N=2^k+1$ para algunos $k\in \mathbb N$ entonces puede tener éxito utilizando exactamente $\left\lceil \frac{(N-1)^2+1}{3}\right \rceil$ bloques, utilizando esta estrategia. Numera las filas y columnas de $1$ a $N$ . Un cuadrado en la fila $r$ y columna $c$ se rellenará siempre que

• $2\le r\le N-1$ ,

• $2\le c\le N-1$ y

• La mayor potencia de $2$ dividiendo $r-1$ es igual a la mayor potencia de dos dividiendo $c-1$ .

Esto explica todos los bloques menos uno. A continuación, hay que colocar un bloque más en el borde, por ejemplo en $(r,c)=(1,2)$ . He aquí una ilustración de esta construcción cuando $N=17=2^4+1$ .

. X . . . . . . . . . . . . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . X . . . . . . . X . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . . . . . X . . . . . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . X . . . . . . . X . . . .
. X . X . X . X . X . X . X . X .
. . X . . . X . . . X . . . X . .
. X . X . X . X . X . X . X . X .
. . . . . . . . . . . . . . . . .

Por último, podemos demostrar que $$ \text{# blocks}\le \lfloor N^3/3\rfloor $$ generalizando la construcción siguiente. En concreto, se toman franjas diagonales de bloques espaciados regularmente a intervalos de tres, y luego se mueven algunos bloques para que las regiones entre las franjas puedan acceder unas a otras. Ilustración $N = 10$ :

. . . . . . . . . .
X . X X . X X . X X
. . X . . X . . X .
. X . . X . . X . .
X . . X . . X . . X
. . X . . X . . X .
. X . . X . . X . .
X . . X . . X . . X
X . X X . X X . X .
. . . . . . . . . .