如何用Prolog解决'6书'难题？

Question

我刚看到（source）上math.SE这样一个问题：

六种不同的书籍（A，B，C，d，E，F）相同大小的层叠作为 图：

我们知道以下事实：

1. A和d都没有接触。
2. E是两本既垂直又水平的书。
3. C正好碰到两本书。
4. A和F触摸。
5. E和F触摸沿其盖（长边）

多少书他们的位置知道？

我以为我可以用Prolog的解决这个问题：

% Those are the books: 
book(a). 
book(b). 
book(c). 
book(d). 
book(e). 
book(f). 

% This is how 'touching' works: 
touching(X,Y):- touching(Y,X). % touching is symmetric 
touching(p1,p2). 
touching(p2,p3). 
touching(p3,p4). 
touching(p3,p5). 
touching(p3,p6). 
touching(p4,p5). 
touching(p5,p6). 

% List all possible positions: 
position(a):- p1,p2,p3,p4,p5,p6. 
position(b):- p1,p2,p3,p4,p5,p6. 
position(c):- p1,p2,p3,p4,p5,p6. 
position(d):- p1,p2,p3,p4,p5,p6. 
position(e):- p1,p2,p3,p4,p5,p6. 
position(f):- p1,p2,p3,p4,p5,p6. 

% Every position has one book 
getBook(p1) :- a,b,c,d,e,f. 
getBook(p2) :- a,b,c,d,e,f. 
getBook(p3) :- a,b,c,d,e,f. 
getBook(p4) :- a,b,c,d,e,f. 
getBook(p5) :- a,b,c,d,e,f. 
getBook(p6) :- a,b,c,d,e,f. 

% Add your facts: 
not(touching(position(a),position(d))). 
position(e):- p5,p2. 
% C touches exactly two books: eventually something like aggregate_all(count, touching(e,X), Count):-2. 
position(c):- p2, p4,p6. 
touching(position(a),position(f)). 
touching(position(e),position(f)). 

但是当我尝试position(a)我得到：

?- consult(books). 
Warning: /home/moose/Downloads/LaTeX-examples/documents/Programmierparadigmen/scripts/prolog/books.pl:37: 
    Clauses of position/1 are not together in the source-file 
Warning: /home/moose/Downloads/LaTeX-examples/documents/Programmierparadigmen/scripts/prolog/books.pl:40: 
    Clauses of touching/2 are not together in the source-file 
% books compiled 0.00 sec, 32 clauses 
true. 

?- position(a). 
ERROR: position/1: Undefined procedure: p1/0 
    Exception: (7) p1 ? 

• 问题1：为什么我会得到一个异常，以及如何我是否修复它？
• 问题2：是否有一种方法来描述更接近于文本的序言中的事实3？
• 问题3：如何打印所有组合？

Answer 1

这是关键。您需要使用符合某些约束的逻辑变量找到排列的[1,2,3,4,5,6]，标记为[A,B,C,D,E,F]。约束条件是书本触摸和书本水平或垂直对齐。我们拥有的事实是

vert(1). 
vert(2). 
vert(3). 

horz(4). 
horz(5). 
horz(6). 

和书之间的一些关系，

touch(3, 4). 
touch(3, 5). 
touch(3, 6). 

touch_long(1, 2). 
touch_long(2, 3). 
touch_long(4, 5). 
touch_long(5, 6). 

touching(X, Y) :- 
    touch(X, Y) ; touch(Y, X); touching_long(X, Y). 

touching_long(X, Y) :- 
    touch_long(X, Y) ; touch_long(Y, X). 

蛮力的方式（足够这样一个小问题）就是生成排列并检查约束。这在Prolog编程中被称为生成和测试方法。

% books(A, B, C, D, E, F) unifies its variables with the 
% integers 1 through 6 to meet the constraints. 
books(A, B, C, D, E, F) :- 
    permutation([1, 2, 3, 4, 5, 6], [A, B, C, D, E, F]), 

    % 1. A and D are not touching. 
    \+ touching(A, D), 

    % 2. E is between two books which are both vertical or both horizontal. 
    % We can take a shortcut by exploiting the asymmetry in touch_long. 
    touch_long(_, E), 
    touch_long(E, _), 

    % 3. C touches exactly two books. That means that the set of all books 
    % touching C has cardinality 2. 
    setof(X, touching(X, C), TouchingC), 
    length(TouchingC, 2), 

    % 4. A and F touch. 
    touching(A, F), 

    % 5. E and F touch along their cover (long side). 
    touching_long(E, F). 

您现在可以运行books(A,B,C,D,E,F)生成合法的排列：

?- books(A,B,C,D,E,F). 
A = 3, 
B = 2, 
C = 4, 
D = 1, 
E = 5, 
F = 6 ; 
A = 3, 
B = 2, 
C = 6, 
D = 1, 
E = 5, 
F = 4 

等解决原来的问题可以通过观察输出来实现;写一个完全自动的解决方案到原来的程序留下来作为一个练习（这有点乏味）。

Answer 2

编辑修正了一个错误（关于“E和F触摸沿着它们的覆盖（长边）”的规则）使用D而不是F）。使用Eclipse CLP Prolog的

约束编程解决方案：

:- lib(gfd). 

model(Books) :- 
    [A, B, C, D, E, F] = Books, 

    Books :: 1..6, 
    alldifferent(Books), 

    % A and D are not touching. 
    abs(A - D) #\= 1, (A #= 3) => (D #< 4), (D #= 3) => (A #< 4), 

    % E is between two books which are both vertical or both horizontal. 
    E :: [2, 5], 

    % C touches exactly two books. 
    C :: [2, 4, 6], 

    % A and F touch. 
    (abs(A - F) #= 1) or (A #= 3 and F #> 4) or (F #= 3 and A #> 4), 

    % E and F touch along their cover (long side) 
    abs(E - F) #= 1, (E #> 3) => (F #> 3), (E #< 4) => (F #< 4). 

find(Books) :- 
    findall(Books, (model(Books), labeling(Books)), Sols), 
    table(Books, Sols). 

运行：

[eclipse]: find([A, B, C, D, E, F]). 

A = A{[3 .. 6]} 
B = B{[2, 4 .. 6]} 
C = C{[2, 4, 6]} 
D = 1 
E = E{[2, 5]} 
F = F{[3, 4, 6]} 

所以，唯一的书d已经知道位置 - 1