Número total de trayectorias de bucle cerrado en una cuadrícula de 3 por 3

Question

Reglas para hacer un recorrido de bucle cerrado:

1. El camino debe pasar por todos los puntos.
2. El camino tiene que pasar por cada punto sólo una vez.
3. La trayectoria se forma uniendo sólo puntos consecutivos (definidos a continuación).

Los puntos consecutivos son aquellos puntos que son consecutivos horizontal o verticalmente. Pero hay una cosa más, los puntos más a la izquierda son también consecutivos a los puntos más a la derecha y los puntos más arriba son consecutivos a los puntos más abajo.

Tomemos el ejemplo de una cuadrícula de 3 por 3:

A   B   C

D   E   F

G   H   I

$A$ es consecutivo a $B$ (si vamos a la derecha), $C$ (si vamos a la izquierda), $G$ (si subimos) y $D$ (si bajamos).

Así que cada punto tiene 4 puntos consecutivos si n > 2, y 2 puntos consecutivos si n = 2, donde n es el número de puntos en cada fila y cada columna de una cuadrícula cuadrada.

Un ejemplo de la ruta en lo anterior es $ABCFIHEDGA$

Para el caso de 2 por 2,

A   B

C   D

sólo hay un camino posible, es decir, $ABDCA$ ( $BDCAB$ y $ACDBA$ son los mismos que $ABDCA$ es decir, el orden es circular y no tiene dirección).

¿Cuál es el número total de caminos en la cuadrícula de 3 por 3? Generalízalo para una cuadrícula de n por n.

Answer 1

Hay $48$ tales caminos para $n=3$ . Para $n=4$ el recuento es $1344$ y la secuencia correspondiente no parece aparecer en la OEIS.

Los conté por medio de una búsqueda en profundidad. Aquí están las $96$ caminos que obtienes si cuentas un camino y su reverso como diferentes:

ABCFDEHIG, ABCFEHIGD, ABCFIGHED, ABCFIHEDG, ABCIFDEHG, ABCIFEHGD, ABCIGHEFD, ABCIHEFDG, ABEDFCIHG, ABEDGHIFC, ABEFCIHGD, ABEFDGHIC, ABEHGDFIC, ABEHGICFD, ABEHICFDG, ABEHIGDFC, ABHEDFCIG, ABHEDGIFC, ABHEFCIGD, ABHEFDGIC, ABHGDEFIC, ABHGICFED, ABHICFEDG, ABHIGDEFC, ACBEDFIHG, ACBEFIHGD, ACBEHGIFD, ACBEHIFDG, ACBHEDFIG, ACBHEFIGD, ACBHGIFED, ACBHIFEDG, ACFDEBHIG, ACFDGIHEB, ACFEBHIGD, ACFEDGIHB, ACFIGDEHB, ACFIGHBED, ACFIHBEDG, ACFIHGDEB, ACIFDEBHG, ACIFDGHEB, ACIFEBHGD, ACIFEDGHB, ACIGDFEHB, ACIGHBEFD, ACIHBEFDG, ACIHGDFEB, ADEBCFIHG, ADEBHGIFC, ADEFCBHIG, ADEFCIGHB, ADEFICBHG, ADEFIGHBC, ADEHBCFIG, ADEHGIFCB, ADFCBEHIG, ADFCIGHEB, ADFEBCIHG, ADFEBHGIC, ADFEHBCIG, ADFEHGICB, ADFICBEHG, ADFIGHEBC, ADGHBEFIC, ADGHEFICB, ADGHICFEB, ADGHIFEBC, ADGICFEHB, ADGIFEHBC, ADGIHBEFC, ADGIHEFCB, AGDEBHIFC, AGDEFCIHB, AGDEFIHBC, AGDEHIFCB, AGDFCIHEB, AGDFEBHIC, AGDFEHICB, AGDFIHEBC, AGHBCIFED, AGHBEDFIC, AGHEBCIFD, AGHEDFICB, AGHICBEFD, AGHICFDEB, AGHIFCBED, AGHIFDEBC, AGICBHEFD, AGICFDEHB, AGIFCBHED, AGIFDEHBC, AGIHBCFED, AGIHBEDFC, AGIHEBCFD, AGIHEDFCB

Código de Mathematica:

n = 3;
pts = Tuples[Range[0, n - 1], 2];
adj[x_, y_] := 
adj[x, y] = (Count[x - y, 0] == 1) && MemberQ[{1, n - 1}, Max[Abs[x - y]]];
extensions[p_] := Select[Complement[pts, p], adj[Last[p], #] &];

DFS[p_] := (
   If[Length[p] == n^2 && adj[First[p], Last[p]], Sow[p]; Return];
   Scan[DFS[Append[p, #]] &, extensions[p]]);
paths = Reap[DFS[{{0, 0}}]][[2, 1]];