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.
12

I don’t find your results here:

m\n 2 3 4 5 6 7 8
2 1 1 1 1 1 1 1
3 1 0 2 0 4 0 8
4 1 2 6 14 37 92 236
5 1 0 14 0 154 0 1696
6 1 4 37 154 1072 5320 32675
7 1 0 92 0 5320 0 301384
8 1 8 236 1696 32675 301384 4638576

number of Hamiltonian cycles on m X n grid of points
https://oeis.org/A321172

Edit 12.01.2024
Markus Triskas CLP(B) offers two forms QSAT. One form is the
operator (^)/2 for arbitrary existential propositional quantification.
And then using atoms for universal propositional quantification.

I now managed to formulate that all components are connected
in the resulting hamiltonian paths, so that there is only one hamiltonian
path, in that I formulated a counter witness condition, the witness

being a node in some component, not connecting this component
to the corner (1,1). The code contains a diffusion constraint for
the vertex witness, besides the hamilton constraint for the edges.

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. The result so far:

?- count(4,4,C).
C = 6.

?- sat_show(4,4).
Solution 1
+-+ +-+ 
| | | | 
+ + + + 
| | | | 
+ +-+ + 
|     | 
+-+-+-+ 
        
Solution 2
+-+ +-+ 
| | | | 
+ +-+ + 
|     | 
+ +-+ + 
| | | | 
+-+ +-+ 
        
Solution 3
+-+-+-+ 
|     | 
+ +-+ + 
| | | | 
+ + + + 
| | | | 
+-+ +-+ 
        
Solution 4
+-+-+-+ 
|     | 
+ +-+-+ 
| |     
+ +-+-+ 
|     | 
+-+-+-+ 
        
Solution 5
+-+-+-+ 
|     | 
+-+ +-+ 
  | |   
+-+ +-+ 
|     | 
+-+-+-+ 
        
Solution 6
+-+-+-+ 
|     | 
+-+-+ + 
    | | 
+-+-+ + 
|     | 
+-+-+-+ 
        
true.

Source code:

undir3.p.log (4,5 KB)

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.

14

Markus Triska describes the universally quantified propositional
variables feature for his SWI-Prolog CLP(B) as follows:

CLP(B): Constraint Logic Programming over Boolean Variables
Atoms denote parametric values that are universally quantified.
All universal quantifiers appear implicitly in front of the entire expression.
https://www.swi-prolog.org/pldoc/man?section=clpb

I tried the same, now its a little bit faster:

/* with negation of existentially quantified (^)/2 */
?- time(count(4,4,C)).
% 21,258,691 inferences, 2.125 CPU in 2.130 seconds (100% CPU, 10004090 Lips)

/* with universally quantified */
?- time(count(4,4,C)).
% 12,531,683 inferences, 1.250 CPU in 1.250 seconds (100% CPU, 10025346 Lips)

But its extremly memory hungry, I need to go to 4 GB for (5,4):

?- set_prolog_flag(stack_limit, 4_294_967_296).
true.

?- count(5,4,C).
C = 14.

And it also takes quite some time. But its interesting to see that
QSAT allows a formulation, where the modelling step produces a proper
boolean formula from the QSAT language. Maybe another QSAT solver,

than Markus Triskas CLP(B) can do the same faster? One might also
ask, what is exactly behind Minatos or @kuniaki.mukai approach to solve
such problems? What would a ZDD code logically demostrate?

Or is there a counting approach which would avoid QSAT, and we could go
with some SAT formulation, maybe with a specialized #QSAT counting, if
such a thing exists, that would take into account universal quantifiers?

Source code:

undir4.p.log (4,7 KB)

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.