What can lead to the success of Prolog in coincidence, but with an error when requesting to display tags?

Question

I am trying to solve a logical puzzle using Prolog, as a training exercise, and I think I correctly matched the problem using the GNU Prolog final domain resolver.

When I run the solution function, Prolog drops back: yes, and the list of variables, all limited in the range 0..1 (booleans, since I limited them so). The problem is that when I try to add the fd_labeling (Solution) clause, the Prolog is about faces and spits out: no.

I am new to this language and I cannot find any course of attack to understand why everything seems to work until I ask him to outline the answers ...

Answer 1

Apparently, you are not "correctly" matching the problem with FD, since you get "no" when trying to label variables.

What you do in Constraint Logic Programming, a constraint model is created where you have variables with a domain (in your case, logical with a domain [0,1]) and a number of restrictions between these variables. Each constraint has a distribution rule that attempts to achieve consistency for the variable domains on which the constraint is located. Values ​​that are incompatible are removed from the domains. There are several types of consistency, but they have one thing in common: constraints usually do not in themselves give you a complete solution or even say if a solution exists for a constraint model.

As an example, let's say that you have two variables X and Y, both with domains [1..10], and with a restriction of X <Y. Then the distribution rule will remove the value 1 from domain Y and delete 10 from domain X. Then it will stop because the domains are now compatible: for each value in one domain there is a value in another domain so that the restriction is met.

To get a solution (where all the variables are bound to values), you need to designate the variables. Each label awakens the constraints associated with the tagged variable, causing 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 with an empty domain, answer: no)

Since each constraint is intended only for the consistency of the variable regions on which it is located, it is possible that the impossibility arising from the combination of constraints is not detected at the propagation stage. For example, three variables X, Y, Z with domains [1..2] and pairwise inequality restrictions. This seems to have happened with your constraint model.

If you are sure that solving the puzzle should be a solution, then your constraint model contains some impracticability. Perhaps a sharp look at the limitations is already enough to define it.

If you do not see obvious impracticability (for example, some conflicting limitations, such as the inequality example above), you need to debug your program. If possible, do not use the built-in label predicate, but write your own. Then you can add some output predicate that allows you to keep track of which variable was created and which changes in the logical decision variables caused this or caused a failure.

Answer 2

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

When you enter a request in Prolog, you will return to answer . Often the answer contains a solution , sometimes it contains several solutions, and sometimes it does not contain any solution at all. Quite often, these two concepts are confused. Consider the GNU Prolog examples:

| ?- length(Vs,3), fd_domain_bool(Vs). Vs = [_#0(0..1),_#19(0..1),_#38(0..1)] yes 

Here we have an answer containing 8 solutions. I.e:

 | ?- 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 request. This is the @twinterer example in question.

 | ?- 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 no longer contains a solution.

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

Ideally, in this case, the top layer would not say yes, but possible. In fact, CLP (R), one of the very first constraint systems, did this.

Another way to make this a little less cryptic is to show the actual limitations. 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, the SWI shows all the constraints that must be met in order to get a specific solution. Read the SWI answer as: Yes, there is a solution if all of these small prints are correct! Alas, the small print is incorrect.

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

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

In general, you cannot expect a system to maintain global consistency. Causes:

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

• Improved consistency algorithms are often very complex.

• In general, maintaining global coherence is an insoluble problem.