CNF/DNF are built in ZDD with almost zero cost

Nice to know
61

I think tabling/memoing is a mistake. With tabling/memoing you get this
performance on your machine, is this correct? Is this an old machine?

/* SWI-Prolog ??? */
?- time(rect_path_count(rect(4,4), C)).
% 3,773,368 inferences, 0.888 CPU in 0.960 seconds (93% CPU, 4248135 Lips)
C = 8512.

Without tabling/memoing I get a much speedier solution. And it doesn’t
use any big memory, its all backtracking. But looking at the number of
inferences I guess I have a faster machine than yours:

/* SWI-Prolog 9.3.11 */
?- time(aggregate_all(count, path((0,0), [(0,0)]), X)).
% 3,700,116 inferences, 0.219 CPU in 0.222 seconds (98% CPU, 16914816 Lips)
X = 8512.

But you already see from the number of inferences that your tabling/
memoing only halfs the number of inferences. Thats not an extreme
algorithmic advantage given the effort you have put into

hashtables and zdd. My source code is extremly simple:

path((4,4), _) :- !.
path(P, L) :-
   next(P, H), \+ member(H, L),
   path(H, [H|L]).

next((X,Y), (Z,Y)) :- X < 4, Z is X+1.
next((X,Y), (Z,Y)) :- X > 0, Z is X-1.
next((X,Y), (X,Z)) :- Y < 4, Z is Y+1.
next((X,Y), (X,Z)) :- Y > 0, Z is Y-1.