Prolog's search capability can be employed to solve the puzzle. A solution contains three tuples, each consisting of a value for the boy and for the girl property:
solve(Boy1,Girl1, Boy2,Girl2, Boy3,Girl3) :-
The values for one property can be bound right away to avoid searching for all permutations of a solution:
Boy1 = red, Boy2 = green, Boy3 = blue,
As mentioned above, comma represents a logical AND in Prolog. Technically, = is a match, not an assignment; however, the only way to satisfy the first match is to bind Boy1 to the value red , no other values can be tried.
As for the girls, it is not known how the possible values are distributed among the girls in the tuples, but it is clearly required, that the variables take on the values which were stated as facts for the property girl :
girl(Girl1), girl(Girl2), girl(Girl3),
Furthermore, the three values must be mutually different:
Girl1 \= Girl2, Girl1 \= Girl3, Girl2 \= Girl3,
Now the stage is set for checking the constraints. One of the tuples must satisfy the constraint called a above:
( a(Boy1, Girl1); a(Boy2, Girl2); a(Boy3, Girl3) ),
Semicolon denotes a logical OR; if one of the three pairs of variables contains the appropriate values, the predicate a above will be true and therefore the OR combination will be true.
Comma denotes AND and, as usual, takes precedence over OR. This is why the constraint check is enclosed in parentheses.
It is tempting to check the constraint b in the same fashion:
( b(Boy1, Girl1); b(Boy2, Girl2); b(Boy3, Girl3) ), /* don't use */
However, this clause is already true if only one of the pairs contains different values. As written, the constraint enters three crosses into the matrix at once; however, we definitely must check one at a time. Here are different constraints for one exclusion at a time:
c(red, X) :- X \= red; d(green, X) :- X \= green; e(blue, X) :- X \= blue;
Each one of these can be checked as before:
( c(Boy1, Girl1); c(Boy2, Girl2); c(Boy3, Girl3) ),
c will fail unless the first argument is red . This is only the case for one of the three tuples and therefore for one of the three calls in the clause — there would be room for optimization because the initial code of solve ensures that Boy1 is red .
The clause as a whole guarantees that the boy in red does not dance with the girl in red . It takes two more clauses to establish the other two exclusions:
( d(Boy1, Girl1); d(Boy2, Girl2); d(Boy3, Girl3) ), ( e(Boy1, Girl1); e(Boy2, Girl2); e(Boy3, Girl3) ).
No more constraints, the solve predicate is complete. If it is part of the knowledge base Prolog can solve the puzzle:
?- solve(Boy1,Girl1, Boy2,Girl2, Boy3,Girl3). Boy1 = Girl3 = red, Girl1 = Boy2 = green, Girl2 = Boy3 = blue ? ; no ?-
A semicolon is input so that Prolog has to search for further solutions. There are none.