What would cause Prolog to succeed on a match, but fail when asked to label outputs?

Question

I'm trying to solve a logic puzzle with Prolog, as a learning exercise, and I think I've correctly mapped the problem using the GNU Prolog finite domain solver.

When I run the solve function, Prolog spits back: yes and a list of variables all bounded in the range 0..1 (booleans, as I've so constrained them). The problem is, when I try to add a fd_labeling(Solution) clause, Prolog about faces and spits out: no.

I'm new to this language and I can't seem to find any course of attack to figure out why everything seems to work until I actually ask it to label the answers...

Answer 1

Apparently, you didn't "correctly" map the problem to FD, since you get a "no" when you try to label the variables.

What you do in Constraint Logic Programming is set up a constraint model, where you have variables with a domain (in your case booleans with the domain [0,1]), and a number of constraints between these variables. Each constraint has a propagation rule that tries to achieve consistency for the domains of the variables on which the constraint is posted. Values that are not consistent are removed from the domains. There are several types of consistency, but they have one thing in common: the constraints usually won't by themselves give you a full solution, or even tell you whether there is a solution for the constraint model.

As an example, say you have two variables X and Y, both with domains [1..10], and the constraint X < Y. Then the propagation rule will remove the value 1 from the domain of Y and remove 10 from the domain of X. It will then stop, since the domains are now consistent: for each value in one domain there exists a value in the other domain so that the constraint is fulfilled.

In order to get a solution (where all variables are bound to values), you need to label variables. Each labeling will wake up the constraints attached to the labeled variable, triggering another round of propagation. This will lead to a solution (all variables bound to values, answer: yes) or failure (in each branch of the search tree, some variable ends up with an empty domain, answer: no)

Since each constraint is only aiming for consistency of the domains of the variables on which it is posted, it is possible that an infeasibility that arises from a combination of constraints is not detected during the propagation stage. For example, three variables X,Y,Z with domains [1..2], and pairwise inequality constraints. This seems to have happened with your constraint model.

If you are sure that there must be a solution to the puzzle, then your constraint model contains some infeasibility. Maybe a sharp look at the constraints is already sufficient to spot it.

If you don't see any obvious infeasibility (e.g., some contradicting constraints like the inequality example above), you need to debug your program. If it's possible, don't use a built-in labeling predicate, but write your own. Then you can add some output predicate that allows you to trace what variable was instantiated and what changes in the boolean decision variables this caused or whether it led to a failure.

Answer 2

(@twinterer already gave an explanation, my answer tries to take it from a different angle)

When you enter a query to Prolog what you get back is an answer. Often an answer contains a solution, sometimes it contains several solutions and sometimes it does not contain any solution at all. Quite often these two notions are confused. Let's look at examples with GNU Prolog:

| ?- length(Vs,3), fd_domain_bool(Vs).                                       

Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]

yes

Here, we have an answer that contains 8 solutions. That is:

| ?- length(Vs,3), fd_domain_bool(Vs), fd_labeling(Vs).

Vs = [0,0,0] ? ;

Vs = [0,0,1] ? ;

...

Vs = [1,1,1]

yes

And now another query. That is the example @twinterer referred to.

| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs).

Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]

yes

The answer looks the same as before. However, it does no longer contain a solution.

| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs), fd_labeling(Vs).

no

Ideally in such a case, the toplevel would not say "yes" but "maybe". In fact, CLP(R), one of the very first constraint systems, did this.

Another way to make this a little bit less mysterious is to show the actual constraints involved. SWI does this:

?- length(Vs,3), Vs ins 0..1, all_different(Vs).
Vs = [_G565,_G568,_G571],
_G565 in 0..1,
all_different([_G565,_G568,_G571]),
_G568 in 0..1,
_G571 in 0..1.

?- length(Vs,3), Vs ins 0..1, all_different(Vs), labeling([], Vs).
false.

So SWI shows you all constraints that have to be satisfied to get a concrete solution. Read SWI's answer as: Yes, there is a solution, provided all this fine print is true! Alas, the fine print is false.

And yet another way to solve this problem is to get an implementation of all_different/1 with stronger consistency. But this only works in specific cases.

?- length(Vs,3), Vs ins 0..1, all_distinct(Vs).
false.

In the general case you cannot expect a system to maintain global consistency. Reasons:

• Maintaining consistency can be very expensive. It is often better to delegate such decisions to labeling. In fact, the simple all_different/1 is often faster than all_distinct/1.

• Better consistency algorithms are often very complex.

• In the general case, maintaining global consistency is an undecidable problem.