Excluding a tuples_in list in prolog

Question

This is the problem in short: 16 children are to be seated in a 4 x 4 array of chairs. The children are 8 girls (numbered 1..8) and 8 boys (numbered 9..16). 1,3,5,8 think boys are yucky 9,10,11,14 think girls are gross these pairs are enemies: [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]

The predicate to find two children are not enemies is defined as:

not_enemy(A, B) :-
    NotA #\= A #\/ NotB #\= B,
    tuples_in([[NotA, NotB]],
              [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]).

The above code was found here

but when I query ?- not_enemy(1,2) the output is true.

I have to use this long code instead:

not_enemy(A, B) :-
          A #=1 #==> B #\= 2,
          A #=4 #==> B #\= 6,
          A #=4 #==> B #\= 7,
          A #=4 #==> B #\= 9,
          A #=9 #==> B #\= 11,
          A #=12 #==> B #\= 14,
          A #=14 #==> B #\= 16.

Could anyone please help to correct the first piece of code? Thanks in Advance.

Answer 1

I would refine your code, just to make it generic

not_enemy(A, B) :-
    maplist(not_enemy(A,B), [[1,2], [4,6], [4,7], [4,9], [9,11], [12,14], [14,16]]).
not_enemy(A,B,[X,Y]) :-
    X #= A #==> Y #\= B.

I cannot find an appropriate way to use tuples_in to solve this problem.

Answer 2

Above use of tuples_in/2 is wrong.

Think of tuples_in as a way of defining "compatibility tables": Then it should be obvious that the combination with (#\=)/2 cannot possibly work for expressing "incompatibility tables".

Why? Because---with an incompatibility table---we don't want to exclude any single incompatible tuple, but all of them at the same time.

When working with finite domains, we can explicitly construct a compatibility table, by taking a Cartesian product as the basis from which the incompatible pairs are eliminated.

Answer 3

I've found another answer, instead of using this

not_enemy(A, B) :-
    NotA #\= A #\/ NotB #\= B,
    tuples_in([[NotA, NotB]],
              [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]).

Just negate tuples_in with #\

not_enemy(A, B) :-
    #\ tuples_in([[A,B]],
                 [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]).

Answer 4

Expanding on the comment I have given above, I want to show you an important feature of the SWI-Prolog toplevel that helps to detect an obvious problem of the wrong formulation.

First, consider the obviously wrong answer of not_enemy/2:

?- not_enemy(1, 2).
true.

However, there is more to it, and you see that after you use:

?- set_prolog_flag(toplevel_residue_vars, true).
true.

Then, the toplevel displays pending residual goals that are normally not shown because the involved variables do not appear in the query:

?- not_enemy(1, 2).
% with pending residual goals
_G454 in 0..1,
_G454#\/_G460#<==>1,
etc.

From this, it is already clear that something is wrong with the formulation: There are pending residual constraints, and CLP(FD) in general does not and cannot guarantee consistency of pending constraints. You have to use one of the enumeration predicates to see if there are any concrete solutions.

In this case, you get wrong results even if you use the enumeration predicates, because the problem is wrongly and awkwardly expressed. However, the pending residual constraints alone already give you a clear indication that you cannot treat the answers as concrete solutions.

The flag toplevel_residue_vars works by implicitly wrapping the query in an important predicate named call_residue_vars/2. This is available in SICStus and SWI to show all residual constraints. Use it to make sure that you are not accidentally creating unsatisfiable constraints somewhere in your formulation.

For such reasons, I strongly recommend you avoid side-effects, so that you can more declaratively reason about your code and use the toplevel to display answers and concrete solutions.