Hiding states from queries on ZDD behind backtrackable global variables

General
1

I have reviewed codes zdd.pl on ZDD in Pack pac for easy
writing queries on ZDD. Although I could not add any new features, I hope ZDD library in pac could be usable for those who would play something around ZDD. Instead of giving tutorial
I chosen only a few of queries from many ones commented in the codes. They could be reproducible on latest pac 1.8.2 like this as usual, assuming it is installed.

Query Preparation 
?- use_module(library(pac)).
true.

?- use_module(zdd(zdd)).
true.

?- module(zmod).
true.

zmod:  ?- zdd  X << pow([1,2,3]), C << card(X), psa(X).
 zid = 4
	[]
	[3]
	[2]
	[2,3]
	[1]
	[1,3]
	[1,2]
	[1,2,3]
-------------------
X = 4,
C = 8.

I am far from zdd expert, and still all what I know about ZDD is
that it is a system handling families of sets (FOS) of given total ordered set of atoms. Basic set theoretical operations on them are well known and clear for all. Although the zdd library implemented here is currently a work by an amateur, FOS seems interesting data type also for Prolog, he would like to continue to work on little by little further.

BTW, I found that families of lists of given atoms without order
also interesting. Queries below include computing functions and permutationons using such lists.

Have a fun.

Sample queries on families of sets and lists 
?- zdd X << pow([a,b]), Y << pow([c,d]), Z << X+Y, U << card(Z).
 X = 3,
 Y = 5,
 Z = U, U = 7.

?- zdd X << pow([a,b]), Y << pow([c,d]), Z << :arith(X+Y).
 X = 3,
 Y = 5,
 Z = 8.

?- zdd X << pow([a,b]), Y << pow([c,d]), { Z is X+Y }.
 X = 3,
 Y = 5,
 Z = 8.

?- numlist(1, 16, L), (zdd X << pow(L), card(X, C)).
 L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
 X = 17,
 C = 65536.

?- N = 100, M = 100,  numlist(1, N, Ns), numlist(1, M, Ms),
	time(( zdd all_fun(Ns, Ms, F), card(F, C))).

 % 33,627,275 inferences, 2.652 CPU in 2.874 seconds (92% CPU, 12678161 Lips)
 N = M, M = 100,
 Ns = Ms, Ms = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
 F = 505101,
 C = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 .

?- time(( zdd F << all_fun(:numlist(1, 100), :numlist(1, 100)), card(F, C))).
 % 33,627,566 inferences, 3.144 CPU in 3.366 seconds (93% CPU, 10694590 Lips)
 F = 505101,
 C = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 .

?- zdd Is << all_mono([1,2],[a,b,c]), psa(Is).
  zid = 15
 	[1-c,2-b]
 	[1-c,2-a]
 	[1-b,2-c]
 	[1-b,2-a]
 	[1-a,2-c]
 	[1-a,2-b]
 -------------------
 Is = 15.


?- zdd F << all_epi([a,b,c],[1,2]), psa(F).
  zid = 16
 	[a-2,b-2,c-1]
 	[a-2,b-1,c-2]
 	[a-2,b-1,c-1]
 	[a-1,b-2,c-2]
 	[a-1,b-2,c-1]
 	[a-1,b-1,c-2]
 -------------------
 F = 16.

?- time((zdd Ps << all_perm(:numlist(1, 15)), C << card(Ps))).
 % 84,009,018 inferences, 31.345 CPU in 31.648 seconds (99% CPU, 2680145 Lips)
 Ps = 1105921,
 C = 1307674368000.
3

About one year ago, the zdd module of the pac tried to compute the number of paths in the undirected rectangular grid graph with N x N nodes, and in fact it computed for N between 1 and 13.

As I noticed the log for N = 13 was lost, to make sure it was real, I ran the codes to get the below. It took about 36 hours on my iMac with 128GB memory ! The codes has not been touched for one year
because of lack of idea for improving further.

% ?- call_with_time_limit(360000, time((rect_mate(rect(12,12), X, [gc(all)], S), card(X, C, S)))).
%@ % 1,197,556,286,416 inferences, 128320.749 CPU in 128621.409 seconds (100% CPU, 9332523 Lips)
%@ X = 13803431,
%@ S = ..,
%@ C = 64528039343270018963357185158482118.

I heard the Minato’s expert team ten year ago already reported in
article for N = 20 or so, which sounds incredible for me.

If someone might get interested to try the problem in SWI-Prolog it would be my pleasure to help him as far as I could.

Personally as a prologer, I feel a little bit shamed without a clear reason of such big difference compared with their Python or C or Java codes, though I am not sure which one. So far I have not investigated reasons for such big difference. I only think my idea and codes is not good and may be too naive yet.

4

There was a chinese page, maybe computed with bambus sticks?
Just joking, a program line_countingv4.0 was involved.

10 41044208702632496804 (0.7s)
11 1568758030464750013214100 (2.2s)
12 182413291514248049241470885236 (7.8s)
13 64528039343270018963357185158482118 (28s)
14 69450664761521361664274701548907358996488 (106s)
15 227449714676812739631826459327989863387613323440 (7min)
16 2266745568862672746374567396713098934866324885408319028 (28min)
17 68745445609149931587631563132489232824587945968099457285419306 (2h)

https://web.archive.org/web/20150911034408/https://tieba.baidu.com/f?kz=395424512

In the above I have added the reported computing time in parenthesis.
But I didn’t find a SLOAN for NW to SE DAGs, only for NW to SW Hamilton:

Number of Hamiltonian paths from NW to SW corners in an n X n grid.
https://oeis.org/A000532

The SLOAN entry is also where I got the chinese page link from.

5

It is unbelievably fast. Is it really ? I read a comment
in some article that Knuth also found a generating function
for the counting problem. I don’t know details about the function. In stead computing such function, my codes enumerates really all paths and then counts the number of paths.

The number counted by my codes is not the number of Hamiltonian paths but that of cycle free paths.