Número de rutas en una cuadrícula de S a M

Un enfoque posible (pero complicado)

Podrías representar movimientos por números complejos:

$1$es moverse a la derecha,$-1$es mover a la izquierda,$i$es subir,$-i$es moverse hacia abajo.

Entonces un camino es una secuencia tal como$1,-i, -1, ...$

Las condiciones para un camino válido tienen entonces equivalencias aritméticas simples.

Para pasar de B a J La suma total de los números debe ser$2-5i$.

Para permanecer en la cuadrícula Para cualquier número natural$n$, la suma$S_n$del primero$n$los números deben satisfacer$4\ge \Re (S_n)\ge -1, 0\ge \Im (S_n)\ge -5.$

Para no visitar ningún cuadrado dos veces Ninguna suma de números sucesivos debe tener suma$0$.

Esto parece adecuado para ser programado si eso es de interés.

En la fuente original, tenga en cuenta que cada paso en el camino era Derecha o Abajo. Con esas reglas, cualquier camino de B a J requiere 2 Derechas y 5 Abajo, en cualquier orden. Hay$\binom{5+2}{2} = 21$tales caminos. Pero para ir de B a G, por ejemplo, necesitaría movimientos hacia la izquierda y hacia abajo. Si permite tanto Izquierda como Derecha, entonces el número de caminos es infinito, ya que puede moverse Derecha Izquierda Derecha Izquierda... todo el tiempo que quiera.

Editar: con la restricción de no visitar una posición más de una vez, la cantidad de rutas permitidas en todas las direcciones es finita pero grande (en comparación con el tamaño del tablero). Por ejemplo, el número de caminos entre las esquinas opuestas de un$2 \times n$la cuadrícula es$2^{n-1}$, ya exponencial.