[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Adam Russell
Subject: question on fd_minimize and if fd var bindings are created on disjunctions
Date: Fri, 17 Dec 2021 19:22:57 -0500
User-agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/

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

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 which is to act on the input

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?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]