# The number of paths of the rectangular grid graph 13 x 13 **URL:** \ **Category:** Nice to know\ **Tags:** zdd, counting-paths\ **Created:** [October 3, 2022, 5:51pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819 "2022-10-03T17:51:07Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 3, 2022, 5:51pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/1 "2022-10-03T17:51:07Z")
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 ```prolog ?- 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. ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 4, 2022, 1:37am UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/3 "2022-10-04T01:37:40Z")
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. ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 4, 2022, 10:21pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/5 "2022-10-04T22:21:16Z")
**EDIT 5-Oct-2020** I made a small mistake in my posted sample. To make sure, the correction follows. ```prolog simple_add_links([], X, X, _). simple_add_links([L|Ls], X, X0, S):- add_link(L, X, X1, S), zdd_join(X, X1, X2, S), simple_add_links(Ls, X2, X0, S). % ?- <<(X, +[[a-a, b-b, c-c]], S), % simple_add_links([a-b,a-c,b-c], X, X0, S), psa(X0, 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. ```prolog [ [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** > [@kuniaki.mukai](#): > > I regret to say that I have to read some definite paper on them. 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 ](https://www.amazon.co.jp/gp/product/4627852614/ref=ppx_yo_dt_b_asin_image_o00_s00?ie=UTF8&psc=1&asin=4627852614&revisionId=&format=4&depth=1) ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 8, 2022, 11:36pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/7 "2022-10-08T23:36:45Z")
> [@anon95304481](#): > > Is there a relationship between counting paths and > diophantine equations? Also I guess there is, at least in a broader sense that it is one of targets of algebraic number theory, e.g. counting the number of rational number solutions to given diophantine equations. > [@anon95304481](#): > > Do you know the [generating function](https://en.wikipedia.org/wiki/Generating_function) > for counting paths in a rectangular grid nxm. I remember a comment on Knuth’s generating function of that counting paths in rectangular grid graphs, perhaps in some paper written by Minato’s group. Also I am interested in generating functions in particular to counting on graph theory. In fact, I am reading a couple of books on such topics in Japanese, though it is simply difficult for me to catch up with. But I am enjoying to rediscover the Knuth’s generating function. ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 10, 2024, 12:06pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/9 "2024-01-10T12:06:18Z")
> [@anon95304481](#): > > This paper figured out some generating functions, but not all: > > > **The number of Hamiltonian paths in a rectangular grid** > > Collins & Krompart - 1997 > > [https://www.sciencedirect.com/science/article/pii/0012365X9500330Y](https://www.sciencedirect.com/science/article/pii/0012365X9500330Y) Thanks. I will surely read this. Of course I was familiar with finding generating function on Fibonacci series, but I have still no idea at all how to find generating function on counting paths in the rectangular grid graph. So I am looking forward to reading the paper. As for the rectangular case, I would like to apply one of existing codes by slight modification on pruning to count Hamilton paths. I have been taking time to rewrite library(pac/zdd) to hide state argument from application codes, and I have found that it integrates usual prolog codes and that on zdd programming in surprising seamless way. ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 12, 2024, 4:34am UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/11 "2024-01-12T04:34:11Z")
I have applied my `udg_path_count` to count hamilton paths (which visits each node exactly once) by modifying prune condition only. rect(w,h) consists of (w+1)x(h+1) nodes. I have checked only around rect(1,1) by hand. I am not sure that it is correct. ```prolog ?- hamilton_rect_path_count(rect(1,0), C). C = 1. ?- hamilton_rect_path_count(rect(1,1), C). C = 0. ?- hamilton_rect_path_count(rect(2,1), C). C = 1. ?- hamilton_rect_path_count(rect(3,3), C). C = 0. ?- hamilton_rect_path_count(rect(4,4), C). C = 104. ?- hamilton_rect_path_count(rect(5,5), C). C = 0. ?- hamilton_rect_path_count(rect(6,6), C). C = 111712. ?- time(hamilton_rect_path_count(rect(7,7), C)). % 78,168,751 inferences, 8.614 CPU in 9.611 seconds (90% CPU, 9074568 Lips) C = 0. ?- time(hamilton_rect_path_count(rect(8,8), C)). % 425,788,600 inferences, 36.365 CPU in 37.761 seconds (96% CPU, 11708821 Lips) C = 2688307514. ``` ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 12, 2024, 10:28am UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/13 "2024-01-12T10:28:16Z")
I might have solved different (easy) problem from yours. Find all undirected path which starts at (0, 0) and arrives at (w,h) visiting all grid nodes exactly once. **EDIT** Understanding the problem as: to find all hamiltonian cycles in a (small) rectangular grid graph. To solve the problem, first for each pair of node i, j, build the set path(i,j) of paths from i to j. Then build H(i,j) to be the set of hamiltonian cycles that is disjoint union of paths A and B in path(i,j). Finanlly compute the union of the families H(i,j) running node i, j in the graph. It seems a lite weight exercise on zdd programming. I will find time to write codes after fixing the transition work of my zdd library, which is almost finishing but I am seeing several minor points to polish for the future use of the library, which I would like to use as a handy tool helping graph theoretical combinatorics in SWI-Prolog, like a handy calculator for engineering. ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 13, 2024, 7:06am UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/15 "2024-01-13T07:06:59Z")
> [@anon95304481](#): > > Seems to work, but I cannot reproduce the full table since it is > a little bit slow. I use negation of the existential quantifier (^)/2, > didn’t try universal quantifiers yet. Also I have managed to reproduce the table, but only partially. It’s a rapid prototyping to see that rough idea of mine could work which uses `udg_path_count` of mine. I have no idea to find effective pruning so that the table could be fully reproduced. ```prolog % ?- forall( (between(1,4,I), between(1,4,J)), % ( rect_hamilton(rect(I,J), Cs), % card(Cs, C), % writeln(#(hamilton_cycle_of(rect(I,J)=C))))). %@ #(hamilton_cycle_of(rect(1,1)=1)) %@ #(hamilton_cycle_of(rect(1,2)=1)) %@ #(hamilton_cycle_of(rect(1,3)=1)) %@ #(hamilton_cycle_of(rect(1,4)=1)) %@ #(hamilton_cycle_of(rect(2,1)=1)) %@ #(hamilton_cycle_of(rect(2,2)=0)) %@ #(hamilton_cycle_of(rect(2,3)=2)) %@ #(hamilton_cycle_of(rect(2,4)=0)) %@ #(hamilton_cycle_of(rect(3,1)=1)) %@ #(hamilton_cycle_of(rect(3,2)=2)) %@ #(hamilton_cycle_of(rect(3,3)=6)) %@ #(hamilton_cycle_of(rect(3,4)=14)) %@ #(hamilton_cycle_of(rect(4,1)=1)) %@ #(hamilton_cycle_of(rect(4,2)=0)) %@ #(hamilton_cycle_of(rect(4,3)=14)) %@ #(hamilton_cycle_of(rect(4,4)=0)) %@ true. ``` ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 13, 2024, 8:09pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/18 "2024-01-13T20:09:36Z")
> [@anon95304481](#): > > That would be those paths where > > you would flip `p(0,0)-p(0,1)`. The counts for paths and circles should agree. Thanks for the hint, simple but I missed. The hint really works ! However, case of rect(5,5) (= 6x6 nodes) seems still a barrier against my approach. For me, there is difficulty in joining two paths which make a cycle, and also in checking that a path as a set of links is Hamilton. ```prolog % ?- call_with_time_limit(200, rect_hamilton(rect(5,5), Cs)), card(Cs, C). %@ ERROR: Unhandled exception: Time limit exceeded ``` ```prolog % ?- time(rect_hamilton(rect(3,5), Cs)), card(Cs, C). %@ % 4,457,991 inferences, 0.424 CPU in 0.490 seconds (86% CPU, 10515767 Lips) %@ Cs = 52877, %@ C = 37. % ?- time(rect_hamilton(rect(5,3), Cs)), card(Cs, C). %@ % 1,012,752 inferences, 0.186 CPU in 0.244 seconds (76% CPU, 5442241 Lips) %@ Cs = 9737, %@ C = 37. ``` ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 14, 2024, 6:00am UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/20 "2024-01-14T06:00:38Z")
I could reproduce the table on Hamilton cycles in the grid graph of size 8 x 8. It took about 10 minutes, which is unexpectedly fast. Thank you for your help. > **log for Hamiltonian cycles in the 8 x 8 grid graph** > > ```prolog > % ?- N=7, > % call_with_time_limit(3600, forall( (between(1,N,I), between(I, N,J)), > % ( rect_hamilton(rect(I,J), Cs), > % card(Cs, C), > % writeln(rect(I,J)=C) > % ))). > %@ 2 > %@ 1 > %@ merge completed > %@ rect(1,1)=1 > %@ 4 > %@ 1 > %@ merge completed > %@ rect(1,2)=1 > %@ 8 > %@ 1 > %@ merge completed > %@ rect(1,3)=1 > %@ 16 > %@ 1 > %@ merge completed > %@ rect(1,4)=1 > %@ 32 > %@ 1 > %@ merge completed > %@ rect(1,5)=1 > %@ 64 > %@ 1 > %@ merge completed > %@ rect(1,6)=1 > %@ 128 > %@ 1 > %@ merge completed > %@ rect(1,7)=1 > %@ 12 > %@ 4 > %@ merge completed > %@ rect(2,2)=0 > %@ 38 > %@ 12 > %@ merge completed > %@ rect(2,3)=2 > %@ 125 > %@ 36 > %@ merge completed > %@ rect(2,4)=0 > %@ 414 > %@ 108 > %@ merge completed > %@ rect(2,5)=4 > %@ 1369 > %@ 324 > %@ merge completed > %@ rect(2,6)=0 > %@ 4522 > %@ 972 > %@ merge completed > %@ rect(2,7)=8 > %@ 184 > %@ 70 > %@ merge completed > %@ rect(3,3)=6 > %@ 976 > %@ 419 > %@ merge completed > %@ rect(3,4)=14 > %@ 5382 > %@ 2602 > %@ merge completed > %@ rect(3,5)=37 > %@ 29739 > %@ 16215 > %@ merge completed > %@ rect(3,6)=92 > %@ 163496 > %@ 100940 > %@ merge completed > %@ rect(3,7)=236 > %@ 8512 > %@ 4415 > %@ merge completed > %@ rect(4,4)=0 > %@ 79384 > %@ 50228 > %@ merge completed > %@ rect(4,5)=154 > %@ 752061 > %@ 592607 > %@ merge completed > %@ rect(4,6)=0 > %@ 7110272 > %@ 7036013 > %@ merge completed > %@ rect(4,7)=1696 > %@ 1262816 > %@ 1026663 > %@ merge completed > %@ rect(5,5)=1072 > %@ 20562673 > %@ 22317483 > %@ merge completed > %@ rect(5,6)=5320 > %@ 336067810 > %@ 495862653 > %@ merge completed > %@ rect(5,7)=32675 > %@ 575780564 > %@ 898025343 > %@ merge completed > %@ rect(6,6)=0 > %@ 16230458696 > %@ 37273140391 > %@ merge completed > %@ rect(6,7)=301384 > %@ 789360053252 > %@ 2900450966549 > %@ merge completed > %@ rect(7,7)=4638576 > %@ N = 7. > > ``` ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [January 14, 2024, 4:02pm UTC](https://swi-prolog.discourse.group/t/the-number-of-paths-of-the-rectangular-grid-graph-13-x-13/5819/22 "2024-01-14T16:02:30Z")
> [@anon95304481](#): > > a) Is your hamilton cycles solution checked into GitHub somewhere? It will be included in the next library(pac/zdd). I am currently polishing for the next version, which would be drastically “user friendly” for basic zdd programming on Prolog, though compared with previous one. > [@anon95304481](#): > > b) Do you think you can solve the Asher Peres FORTRAN code. Sorry, I don’t know the code. I thought it is for experts, not for amateur on algorithm like me. Anyway, I will check it later.