Challenge accepted! How about vanilla Prolog:
?- time(aggregate_all(count, (between(0,3,X),
between(0,3,Y), path((X,Y), [(X,Y)])), C)).
% 952,151 inferences, 0.047 CPU in 0.059 seconds (80% CPU, 20312555 Lips)
C = 552.
Its a variation without any symmetry breaking
of my take on @kuniaki.mukai’s rect(4,4):
% next(+Pair, -Pair)
next((X,Y), (Z,Y)) :- X < 3, Z is X+1.
next((X,Y), (Z,Y)) :- X > 0, Z is X-1.
next((X,Y), (X,Z)) :- Y < 3, Z is Y+1.
next((X,Y), (X,Z)) :- Y > 0, Z is Y-1.
% path(+Pair, +List)
path(_, L) :- length(L, 16), !.
path(P, L) :-
next(P, H), \+ member(H, L),
path(H, [H|L]).
But didn’t try yet for larger grid sizes. Also the above is
without any cutting plane or otherwise memoization.