No sé cómo resolver esto analíticamente, pero afortunadamente, el problema es lo suficientemente pequeño como para ser abordado por la fuerza bruta. El resultado que obtuve, usando el todopoderoso Mathematica, es 238.
Esto se hizo con el siguiente código:
n = 3;
Bordes = Acoplar [
Tabla [{{i, j} \ [UndirectedEdge] {i + 1, j}, {j,
i} \ [Borde no dirigido] {j, i + 1}}, {i, 1, n – 1}, {j, 1, n}]];
EdgeRestrictions =
Acoplar [Tabla [{{i + k, j} \ [UndirectedEdge] {i + k, j + 1}, {i,
j + k} \ [Borde no dirigido] {i + 1, j + k}}, {i, 1, n – 1}, {j, 1,
n – 1}, {k, 0, 1}], {{1, 2}, {3, 4}}];
CandidateGraphs = Subconjuntos [Bordes];
Robusto [x_]: =
Aplicar [Y, Mapa [Longitud [Intersección [x, #]] <4 &, Restricciones de borde]]
Connected [x_]: = (Length [ConnectedComponents [Graph [x]]] == 1 &&
VertexCount [Graph [x]] == n ^ 2)
ValidGraphs = Seleccione [CandidateGraphs, y [Connected [#], Robust [#]] &];
Longitud [Gráficos válidos]
- ¿De qué sirve estudiar matemáticas si nunca vamos a aplicarlo en el día a día?
- ¿Hay un nudo que cuando se tira aumenta la tensión pero el lazo no se encoge cuando se tiran los dos extremos?
- Conjetura de Goldbach: ¿de cuántas maneras se puede escribir "1000" como la suma de dos números primos?
- ¿Cuál será la respuesta?
- ¿Puede Suiza encajar en el Gran Cañón?
Explicación:
Veo el laberinto como un gráfico con 9 nodos y 12 posibles bordes entre ellos. Aquí puede existir un borde entre cuadrados adyacentes y significa que no hay muro entre ellos.
Bordes es una lista de los 12 bordes posibles.
EdgeRestrictions codifica las diversas restricciones establecidas por su regla “muro en cada subconjunto 2 × 2”. Cada elemento de la lista representa uno de esos subconjuntos, y es en sí mismo una lista de los bordes posibles en este subconjunto.
CandidateGraphs es una lista de todos los gráficos bajo consideración: los 4096 subconjuntos de la lista de bordes.
Robust toma un gráfico y comprueba que cumple con todas las restricciones, es decir, su intersección con cada 2 × 2 no tiene al menos un borde (lo que significa que hay un muro).
Conectado verifica si un gráfico tiene un solo componente conectado (por lo que desde cada celda puede llegar a cada celda).
ValidGraphs selecciona de la lista de todos los candidatos solo aquellos que son robustos y conectados.
Finalmente, se muestra la longitud de esta lista, el número de gráficos válidos. El resultado, como se mencionó, es 238.
Ejecutar el mismo cálculo en laberintos 4 × 4 también es factible. El resultado que obtuve es 175190.