question on fd_minimize and if fd var bindings are created on disjunctions

Adam Russell <[email protected]> Fri, 17 Dec 2021 19:22:57 -0500
Newsgroups gmane.comp.gnu.prolog.general
Message-ID <[email protected]>
In one of the 2021 Advent of Code puzzles the requirement is to find the
lowest cost traversal of a maze. The actual problem statement is at 
https://adventofcode.com/2021/day/15

Rather than just, say, implement A* I thought I'd try something a little 
different. My thought was to represent the indices of the grid as fd 
vars and the movements within the grid as constraints. The code to do 
this is http://paste.debian.net/hidden/70acfece/ which is to act on the 
input http://paste.debian.net/hidden/ce112fda/

This works for this 10x10 test input. I get the answer 40 which is the 
minimal cost path. Trying it out on a larger input and gprolog crashes. 
Since I have access to a system with considerable memory I figured I 
could just increase CSTRSZ to some large limit, but gprolog will not 
accept too large a value for CSTRSZ without just crashing at the start. 
Is there an internal hard coded limit to how high this may be set?

I figured since this approach seems to work OK, besides the limit on 
CSTRSZ I would just re-implement the constraints using SWI-Prolog's 
clpfd since SWI seems happier about allowing the user to set arbitrarily 
high memory allocation sizes. I did that but then found SWI would not 
yield a correct answer!

I posted a question on this to the SWI forums and one possible 
explanation given there is that for this part of the code which 
restricts the possible movements through the maze

             (M #= A rem LS,  M #\= 1, B #= A - 1); %LEFT
	    (M #= A rem LS,  M #> 0,  B #= A + 1); %RIGHT
	    (A #> LS,	     B #= A - LS);	   %UP
	    (A #=< MaxN,     B #= A + LS)	   %DOWN

that gprolog is (correctly! in my opinion) creating an fd var binding
for each part of the disjunction but SWI's clpfd is not.

I suppose that would explain why gprolog yields an optimally minimal 
answer but blasts through the CSTRSZ limitations, and SWI does not yield 
a minimal answer at all.

That all seems plausible, but is that in fact true? Or is there 
something else at work here?