# The number of paths of the rectangular grid graph 13 x 13

Running long my imac intell (not M1) with 128GB RAM, I got the number of paths of rectangular grid graph rect(12, 12) which has 13 x 13 = 169 nodes

``````?- call_with_time_limit(360000, time((rect_mate(rect(12,12), X, [gc(all)], S), card(X, C, S)))).
1,178,477,238,520 inferences, 119736.514 CPU in 119878.871 seconds (100% CPU, 9842254 Lips)
X = 13803431,
S = ..,
C = 64528039343270018963357185158482118.
``````

The same method as for rect(11, 11) posted alredy was used. This time, for each node added to the graph, ‘zdd gc’ of mine and prolog `garbadge_collect/0`, aside special pruning
due to the topology of the rectangular graph, were called.

As the activity memory monitor kept showing about 90GB used, rect(12,12) is surely the limit of the current method of mine.

However, watching the activity monitor, new idea for me has come to mind, I will post if it works.

BTW, although I think my zdd library is a toy as it is, I hope it is already a playable toy, which, I am feeling, opens a new area for zdd processing in SWI-Prolog compared with traditional list processing.

Thanks for sharing your progress. How to reach this one?

Extended to n=27 by Hiroaki Iwashita, Nov 18 2013
https://oeis.org/A007764

I guess it used, not 100% sure:

Minato Discrete Structure Manipulation System
https://www.jst.go.jp/erato/minato/index_en.html

Thank you for response with related links, in which the success case of upto n=27 was reported about 10 years ago.

I have to investigate why my method is so inefficient compared with the existing one. Basically, complexity of my naive algorithm is exponential due to processing the power set of links, whereas the problem itself seems to be of polynomial-time complexity. I have to go back to my starting point for the problem.

I found A007764 by googling your result

``````64528039343270018963357185158482118 ,
``````

which seems to be correct, it is listed there.

Or maybe you copy pasted it from there? Just joking!
Unfortunately I dont have a 128 GB box to verify your result.

EDIT 5-Oct-2020
I made a small mistake in my posted sample. To make sure, the correction follows.

``````simple_add_links([], X, X, _).
zdd_join(X, X1, X2, S),

% ?- <<(X, +[[a-a, b-b, c-c]], S),
%@  zid = 32
%@ 	[b-c,(a->b),(a->c)]
%@ 	[a-c,(a->b),(b->c)]	        <<  Found !
%@ 	[a-c,b-b,(a->c)]		<<  Found !
%@ 	[a-b,(a->c),(b->c)]
%@ 	[a-b,c-c,(a->b)]
%@ 	[a-a,b-c,(b->c)]
%@ 	[a-a,b-b,c-c]
%@ -------------------
%@ X = 4,
%@ S = ..,
%@ X0 = 32.
``````

End of edit.

From others, I might look like person who pretends to understand Knuth’s SimPath method and mate-ZDD method by Minato’s group. To be honest, that is true. I regret to say that I have to read some definite paper on them.

Below is a simple example to illustrate the current way of mine to count the paths. It is extremely naive.

Undirected graph G = (N, E) = ({a,b,c}, {a-b, b-c, a-c})
Goal is to count the paths which connects a and c. My codes applys each link in order beginning with the inital mate. My pupose is to explaine how naive thing my codes does. However, now I have noticed that many basic things are necessary to be written, which is tedious for me for now. I hope it is clear for the reader.

``````		 [	[a-a, b-b, c-c]		]
a-b
[	[a-a, b-b, c-c],
[a-b, c-c, a->b]	]
b-c
[	[a-a, b-b, c-c],
[a-b, c-c  a->b],
[a-a, b-c, b->c],
[a-c, a->b, b->c]	]

a-c		[	[a-a, b-b, c-c],
[a-b, c-c  a->b],
[a-a, b-c, b->c],
[a-c, a->b, b->c],    << found !
[a-c, b-b, a->c],        << found !
[b-c, a->b, a->c],
[a-b, b->c, a->c]	]
``````

edit 8:Oct:2022

I have found a possibly definite book published on ZDD, which I have ordered on the net.

Super fast graph enumating algorithmn (In Japanese, perhaps). Edited by Shinichi Minato, 2015

He I am responding, so that you don’t have to edit
Is there a relationship between counting paths and

diophantine equations? At least I guess, because counting
paths is a combinatorial problem, there is possibly
a relationship to generating function with integer

coefficients. Do you know the generating function
for counting paths in a rectangular grid nxm. I saw
something on the web to this end. Maybe this could lead

to a new algorithm? The ultimate generating function
would be maybe an infinite series in two variables `x` and `y`,
`p(x,y)`, so that a monomial `x^n*y^m` would have a coefficient

`anm`, and which would give the count:

``````p(x,y) = sum_ij aij x^i*y^j
``````

Any idea what the generating function could be?