CLPFD ins operator yields not sufficiently instantiated error

user_14856592 0
Viewed 163

So, my goal is to make a map colourer in Prolog. Here's the map I'm using:

enter image description here

And this are my colouring constraints:

colouring([A,B,C,D,E,F]) :- 
    maplist( #\=(A), [B,C,D,E] ),
    maplist( #\=(B), [C,D,F]),
    C #\= D,
    maplist( #\=(D), [E,F]),
    E #\= F.

Where [A,B,C,D,E,F] is a list of numbers(colors) from 1 to n.

So I want my solver to, given a List of 6 colors and a natural number N, determine the colors and N constraints both ways, in a way that even the most general query could yield results:

regions_ncolors(L,N) :- colouring(L), L ins 1..N, label(L).

Where the most general query is regions_ncolors(L,N).

However, the operator ins doesn't seem to accept a variable N, it instead yields an argument not sufficiently instantiated error. I've tried using this solution instead:

int_cset_(N,Acc,Acc) :- N #= 0.
int_cset_(N,Acc,Cs) :- N_1 #= N-1, int_cset_(N_1,[N|Acc],Cs).
int_cset(N,Cs) :- int_cset_(N,[],Cs).

% most general solver
regions_ncolors(L,N) :- colouring(L), int_cset(N,Cs), subset(L,Cs), label(L).

Where the arguments in int_cset(N,Cs) is a natural number(N) and the counting set Sn = {1,2,...,N}

But this solution is buggy as regions_ncolors(L,N). only returns the same(one) solution for all N, and when I try to add a constraint to N, it goes in an infinite loop.

So what can I do to make the most general query work both ways(for not-instantiated variables)?

Thanks in advance!

Btw, I added a swi-prolog tag in my last post although it was removed by moderation. I don't know if this question is specific to swi-prolog which is why I'm keeping the tag, just in case :)

clpfd prolog
2 Answers

Your colouring is too specific, you encode the topology of your map into it. Not a problem as is, but it defeats of the purpose of then having a "most general query" solution for just any list.

If you want to avoid the problem of having a free variable instead of a list, you could first instantiate the list with length/2. Compare:

?- L ins 1..3.
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [16] throw(error(instantiation_error,_86828))
ERROR:   [10] clpfd:(_86858 ins 1..3) ...

Is that the same problem as you see?

If you first make a list and a corresponding set:

?- length(L, N), L ins 1..N.
L = [],
N = 0 ;
L = [1],
N = 1 ;
L = [_A, _B],
N = 2,
_A in 1..2,
_B in 1..2 ;
L = [_A, _B, _C],
N = 3,
_A in 1..3,
_B in 1..3,
_C in 1..3 .

If you use length/2 like this you will enumerate the possible lists and integer sets completely outside of the CLP(FD) labeling. You can then add more constraints on the variables on the list and if necessary, use labeling.

Does that help you get any further with your problem? I am not sure how it helps for the colouring problem. You would need a different representation of the map topology so that you don't have to manually define it within a predicate like your colouring/1 you have in your question.

user_144119970

There are several issues in your program.

subset/2 is impure

SWI's (by default) built-in predicate subset/2 is not the pure relation you are hoping for. Instead, it expects that both arguments are already sufficiently instantiated. And if not, it takes a guess and sticks to it:

?-            colouring(L), subset(L,[1,2,3,4,5]).
   L = [1,2,3,4,2,1].

?-            colouring(L), subset(L,[1,2,3,4,5]), L = [2|_].
   false.

?- L = [2|_], colouring(L), subset(L,[1,2,3,4,5]), L = [2|_].
   L = [2,1,3,4,1,2].

With a pure definition it is impossible that adding a further goal as L = [2|_] in the third query makes a failing query succeed.

In general it is a good idea to not interfere with labeling/2 except for the order of variables and the options argument. The internal implementation is often much faster than manual instantiations.

Also, your map is far too simple to expose subset/2s weakness. Not sure what the minimal failing graph is, but here is one such example from

R. Janczewski et al. The smallest hard-to-color graph for algorithm DSATUR, Discrete Mathematics 236 (2001) p.164.

colouring_m13([K1,K2,K3,K6,K5,K7,K4]):-
    maplist(#\=(K1), [K2,K3,K4,K7]),
    maplist(#\=(K2), [K3,K5,K6]),
    maplist(#\=(K3), [K4,K5]),
    maplist(#\=(K4), [K5,K7]),
    maplist(#\=(K5), [K6,K7]),
    maplist(#\=(K6), [K7]).

?-            colouring_m13(L), subset(L,[1,2,3,4]).
   false.                   % incomplete

?- L = [3|_], colouring_m13(L), subset(L,[1,2,3,4]).
   L = [3,1,2,2,3,1,4].

int_cset/2 never terminates

... (except for some error cases like int_cset(non_integer, _).). As an example consider:

?- int_cset(1,Cs).
   Cs = [1]
;  loops.

And don't get fooled by the fact that an actual solution was found! It still does not terminate.

@Luis: But how come? I'm getting baffled by this, the same thing is happening on ...

To see this, you need the notion of a failure-slice which helps to identify the responsible part in your program. With some falsework consisting of goals false the responsible part is exposed.

All unnecessary parts have been removed by false. What remains has to be changed somehow.

int_cset_(N,Acc,Acc) :- false, N #= 0.
int_cset_(N,Acc,Cs) :- N1 #= N-1, int_cset_(N1,[N|Acc],Cs), false.

int_cset(N,Cs) :- int_cset_(N,[],Cs), false.

?- int_cset(1, Cs), false.
   loops.

Adding the redundant goal N1 #> 0 will avoid unnecessary non-termination.

This alone will not solve your problem since if N is not given, you will still encounter non-termination due to the following failure slice:

regions_ncolors(L,N) :-
   colouring(L),
   int_cset(N,Cs), false,
   subset(L,Cs),
   label(L).

In int_cset(N,Cs), Cs occurs for the first time and thus cannot influence termination (there is another reason too, its definition would ignore it as well..) and therefore only N has a chance to induce termination.

The actual solution has been already suggested by @TA_intern using length/2 which liberates one of such mode-infested chores.

user_7728680
Related