Número de caminos en una cuadrícula

propuesto por josejuan

Dada una cuadrícula de NxN nodos, ¿cuantos caminos diferentes hay (sin pasar dos veces por el mismo nodos) al ir de una esquina a su opuesta diagonal?

Enunciado
Dada una cuadrícula de NxN nodos, ¿cuantos caminos diferentes hay (sin pasar dos veces por el mismo nodo) al ir de una esquina a su opuesta diagonal?

Por ejemplo, para una cuadrícula de 4 nodos (2x2):



Para una cuadrícula de 9 nodos (3x3):



Se trata entonces de escribir una función:

	ContarCaminos( Entero "nº nodos" ) -> Entero "nº de caminos"

	// Por ejemplo:
	ContarCaminos( 2 ) := 2
	ContarCaminos( 3 ) := 12
	ContarCaminos( 4 ) := 184
	ContarCaminos( 5 ) := 8512
	ContarCaminos( 6 ) := 1262816
	


Sugiero PRIMERO que escribas el algoritmo más rápido que puedas, ¡NO BUSQUES INFORMACION!


Explicación del problema vía Gaussianos

Números conocidos A007764

Posibles estrategias en Wolfram

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

6 Soluciones

Dar mi solución

1voto
Número de caminos en una cuadrícula en C#
por

josejuan

hace 6 años

Al contrario que en Haskell (que en estructuras inmutables es trivial) paralelizar mutable es difícil, no he encontrado una forma eficiente de mantener el uso de las CPU al 100% durante todo el proceso (hay subcaminos mucho más complejos que otros). De todos modos, se confirma que la estrategia de eliminación de lazos cerrados mejora (para n=7 en un 50%) la directa (eg. sólo fronteras).

1voto
Número de caminos en una cuadrícula en Haskell
por

josejuan

hace 6 años

Una forma más elegante y usando como estrategia adicional el evitar caminos muertos (aquellos en que el camino se estrangula a sí mismo) es ésta, pero es menos eficiente porque (creo) hay más accesos al Array y como es funcional (inmutable) se pierde bastante tiempo; a la larga (para N grande) debería ser más eficiente. Algo mejor, será implementarlo imperativamente (aunque se complica la paralelización).

0votos
Número de caminos en una cuadrícula en Haskell
por

josejuan

hace 6 años

Lo divertido de este problema (para mí), es que no tiene solución eficiente y es divertido ver de que formas podemos arañar algo de eficiencia. La mejor forma (que conozca) es usando árboles de decisión ZDD (en el enunciado se referencia). Pero lo suyo es hacerlo "al vuelo". Las tres estrategias que yo he usado aquí es la que ya ha usado durbon, empezar con un avance (y multiplicar el nº por dos) y paralelizar.

Dar mi solución