Mutual Exclusivity in CLP (FD)

Question

I am writing a Prolog program using clp(fd) and it is difficult for me to implement one of my desired limitations.

The output is a list of integers (the length depends on the input to another part of the program), where there are certain pairs of predefined numbers that are mutually exclusive, and one number from each pair should be at the output.

Example:

The output is a list of integers, each of which is from 1 to 10. The output must contain either 3 or 4, but not both.

---

So far I have the following which restricts it so that 3 and 4 cannot be both in the output file, however it does not guarantee that one of them at the exit.

 mutual2([A], ME1):- (A in 3 #==> ME1) #/\ (#\ A in 4 #<== ME1). mutual2([A, B| Tail], ME1):- (A in 3 #==> ME1) #/\ (#\ A in 4 #<== ME1), (B in 3 #==> ME1) #/\ (#\ B in 4 #<== ME1), mutual2([B|Tail], ME1). 

EDIT:
So:

 [A,B] ins 2..6, A #< B, mutual2([1,2,B,A,5],M), label([A,B]). 

gives:

 A = 2, B = 3, M = 1 ; A = 2, B = 4, M = 0 ; A = 2, B = 5, M in 0..1 ; A = 3, B = 5, M = 1 ; A = 4, B = 5, M = 0 ; 

But I do not want A=2, B=5, M in 0..1 be a valid output, since neither A nor B are 3 or 4 equal.

Answer 1

I would probably use a combination of CLP (FD) and DCG, since we are dealing with sequences.

Here's an implementation that recognizes sequences containing exactly one 3 or one 4:

 :- use_module(library(clpfd)). one_of_3_4 --> no_3_4, [3], no_3_4. one_of_3_4 --> no_3_4, [4], no_3_4. no_3_4 --> []. no_3_4 --> [X], { X in 1..2 \/ 5..9 }. 

This gives something like this:

 2 ?- phrase(one_of_3_4, L), label(L). L = [3] ; L = [3, 1] ; L = [3, 2] ; L = [3, 5] ; L = [3, 6] ; L = [3, 7] ; L = [3, 8] ; L = [3, 9] ; L = [1, 3] ; L = [2, 3] ; L = [5, 3] ; L = [6, 3] ; L = [7, 3] ; L = [8, 3] ; L = [9, 3] ; ... 

This is not a complete solution to the original problem, but should give an idea of ​​how to approach it in a transparent way.

<h / "> If you do not want to use DCG, here is another approach that first indicates a list of single digits other than 3 or 4, then inserts 3 or 4 anywhere in the list (SWI Prolog):

 :- use_module(library(clpfd)). one_of_3_4(L) :- length(L1, _), L1 ins 1..2 \/ 5..9, ( select(3, L, L1) ; select(4, L, L1) ). 

Then it can be called as follows:

 2 ?- one_of_34(L), label(L). L = [3] ; L = [4] ; L = [3, 1] ; L = [3, 2] ; L = [3, 5] ; L = [3, 6] ; L = [3, 7] ; L = [3, 8] ; L = [3, 9] ; L = [1, 3] ; L = [2, 3] ; L = [5, 3] ; L = [6, 3] ; L = [7, 3] ; L = [8, 3] ; L = [9, 3] ; L = [4, 1] ; L = [4, 2] ; L = [4, 5] ; L = [4, 6] ; L = [4, 7] ; L = [4, 8] ; L = [4, 9] ; L = [1, 4] ; L = [2, 4] ; L = [5, 4] ; L = [6, 4] ; L = [7, 4] ; L = [8, 4] ; L = [9, 4] ; ... 

<h / "> In response to the comments on this answer, you can create a non-member predicate that applies specifically to the CLP (FD) script:

 not_member(_, []). not_member(X, [Y|T]) :- X #\= Y, not_member(X, T). 

Or, in short, you can shorten not_member/2 with maplist/2 as:

 not_member(X, L) :- maplist(#\=(X), L). 

Using not_member/2 , this will work as expected:

 mutual(Output, A, B):- member(A, Output), not_member(B, Output). mutual(Output, A, B) :- member(B, Output), not_member(A, Output). 

And the query gives all the results:

 ?- [A,B] ins 2..5, A #< B, mutual([A,B,5],3,4), label([A,B]). A = 3, B = 5 ; A = 2, B = 3 ; A = 4, B = 5 ; A = 2, B = 4 ; false.