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

Nice to know
,
1

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.

2

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

3

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.

4

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.

5

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

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.

		 [	[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

7

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.

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.

9

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.

11

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.

 ?- 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.
13

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.

15

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.

% ?- 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.
17

I don’t think you need to program something. Maybe you would need
to program that every vertex is visited. But full hamilton cycles on a rectangular
grid have the invariant that the top left corner alwas looks like this:

+-+ ..
|
+ ..
.
.

So both edges (0,0) - (0,1) and (0,0) - (1,0) are included the hamilton circle.

Now you have already:

It seems to me you can use the above. Just call it with p(0,0)-p(0,1). A non self-
crossing path that visits all vertices, will not include the edge p(0,0)-p(0,1), otherwise
it would be self-crossing. Maybe there are some border cases for small H and W,

don’t know exactly. But I guess it will count open hamilton paths that are not closed
circles. And because of the above mentioned invariant for rectangular grids about the
top left corner it will also count hamilton circles. That would be those paths where

you would flip p(0,0)-p(0,1). The counts for paths and circles should agree.

18

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.

% ?-  call_with_time_limit(200, rect_hamilton(rect(5,5), Cs)), card(Cs, C).
%@ ERROR: Unhandled exception: Time limit exceeded

% ?-  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.
20

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 
% ?- 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.
22

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.

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.