Prolog置换颜色组合误差的正确量

Question

我遇到了为这个拼图程序打印适量解决方案的问题.它打印正确的拼图,但不是所需的正确解决方案.

以下是每种情况的作用:

拼图1 - 你有五种颜色:2蓝色,2绿色和1黄色没有相同的颜色可能彼此相邻.

拼图2 - 你有六种颜色:1个红色,1个蓝色和4个黑色连续不超过2个黑色.

拼图3 -

你有八种颜色:3个绿色,2个白色,2个红色和1个黑色.白色从不在A和H中.位置D和H都有相同的颜色.A和G中的颜色必须是不同的颜色.红色永远不会出现在F和G中.绿色从不在B和C中.在每个红色的左边,都有一个绿色.

% a program that find solutions for each of the following colored ball problems with  different sets of constraints.

% to run, type either
% sit1, sit2 or sit3.

% select an element for use in permutation test
%
% If the element is the head of the list, then it is in the list, and the tail is left
selectE(Element, [Element|Tail], Tail).        
% If the two lists have the same head, check for more elements in the rest of the lists
selectE(Element, [Head|Tail1], [Head|Tail2]) :-
        selectE(Element, Tail1, Tail2).

% generate permutations
%
% The empty list is a permutation of itself
permutationQ([],[]).
% List1 is a permutation of List2 if each element occurs in both lists 
%    the same number of times
permutationQ(List, [Head|Tail]) :- selectE(Head, List, Rest),
                                  permutationQ(Rest, Tail).
%

% There are 5 colors - 2 blues, 2 greens, 1 yellow
% 
sit1 :- permutationQ([green,green,blue,blue,yellow],[A,B,C,D,E]),
    \+ A=B, \+ B=C, \+ C=D, \+ D=E,    
    printout([A,B,C,D,E]).   % print any solution you find

% print solutions of sit1
printout([A,B,C,D,E]) :-
    nl,
    write('The order of colors from top to bottom is: '), nl,
    write(A),nl,
        write(B),nl,
        write(C),nl,
    write(D),nl,
    write(E),nl.

% There are 6 colors - 1 red, 1 blue, 4 blacks,
% 
sit2 :- permutationQ([black,black,black,black,red,blue],[A,B,C,D,E,F]),  
    ((A==red -> D==blue);
         (A==blue -> D==red);
         (B==red -> E==blue);  
         (B==blue -> E==red); 
         (C==red -> F==blue);   
         (C==blue -> F==red); 
         (D==red -> C==blue);   
         (D==blue -> C==red)),
    printout2([A,B,C,D,E,F]).   % print any solution you find

% print solutions of sit2
printout2([A,B,C,D,E,F]) :-
    nl,
    write('The order of colors from top to bottom is: '), nl,
    write(A),nl,
        write(B),nl,
        write(C),nl,
    write(D),nl,
    write(E),nl,
    write(F),nl.

% There are 8 colors - 3 greens, 2 whites, 2 reds, 1 black 
sit3 :- permutationQ([black,white,white,red,red,green,green,green],[A,B,C,D,E,F,G,H]),
    % The colors in B and C are not green. 
    \+ B=green, 
    \+ C=green, 
    % The colors in E and F are not green because the colors in F and G are not red. 
    \+ E=green,
    \+ F=green,
    % Since red can't be in H, green can't be in G.
    \+ G=green,
    % The colors in D and H are the same color. 
    D=H, 
    % The colors in A and G are of different colors. 
    \+ A=G, 
    % The color in F and G are not red. 
    \+ F=red, 
    \+ G=red, 
    % Red can't be in A because there isn't any other position on the left for the green.
    \+ A=red,
    % The colors in C and D are not red because the colors in B and C are not green. 
    \+ C=red,
    \+ D=red,
    % Whites are neither A nor H. 
    \+ A=white, 
    \+ H=white,
        % White is not on D because white can't be on H.
    \+ D=white, 
    printout3([A,B,C,D,E,F,G,H]).   % print any solution you find

% print solutions of sit3
printout3([A,B,C,D,E,F,G,H]) :-
    nl,
    write('The order of colors from top to bottom is: '), nl,
    write(A),nl,
        write(B),nl,
        write(C),nl,
    write(D),nl,
    write(E),nl,
    write(F),nl,
    write(G),nl,
    write(H),nl.

Answer 1

您的裁员来源取决于您的使用方式permutationQ/2.要看到这一点,请考虑目标

| ?- permutationQ([red,red],P).
P = [red,red] ? ;
P = [red,red] ? ;
no

您期待一个答案/解决方案,但您将获得一个解决方案和一个冗余解决方案.背后的原因是,permutationQ/2只是描述了所有可能的排列,无论它们的实际内容如何.看到这个:

| ?- permutationQ([X,Y],P).
P = [X,Y] ? ;
P = [Y,X] ? ;
no

解决这个问题最便宜的方法是setof(t, Goal, _)绕过每个permutationQ/1目标,从而消除多余的解决方案:

| ?- setof(t,permutationQ([red,red],P),_).
P = [red,red] ? ;
no

一般来说,考虑使用(=)/2和dif/2代替(==)/2和(\+)/2.此外,clpfd最适合解决组合问题.