董事会大会有约束

Question

我正在解决这个问题,但我是Prolog的新手,我不知道该怎么做.

电子板的九个部分具有方形形状,相同的尺寸,每个部分的每个边缘都标有字母和加号或减号.零件应组装成一个完整的板,如下图所示,使公共边具有相同的字母和相反的符号.在Prolog中编写一个计划程序,以便程序将"汇编"作为查询并输出如何组装零件,即确定当前位置的零件的位置和位置,以便它们组合在一起以形成完整的板.

我试过解决它,我写了以下条款:

complement(a,aNeg).
complement(b,bNeg).
complement(c,cNeg).
complement(d,dNeg).
complement(aNeg,a).
complement(bNeg,b).
complement(cNeg,c).
complement(dNeg,d).
% Configuration of boards, (board,left,top,right,bottom)
conf(b1,aNeg,bNeg,c,d).
conf(b2,bNeg,a,d,cNeg).
conf(b3,dNeg,cNeg,b,d).
conf(b4,b,dNeg,cNeg,d).
conf(b5,d,b,cNeg,aNeg).
conf(b6,b,aNeg,dNeg,c).
conf(b7,aNeg,bNeg,c,b).
conf(b8,b,aNeg,cNeg,a).
conf(b9,cNeg,bNeg,a,d).

position(b1,J,A).
position(b2,K,B).
position(b3,L,C).
position(b4,M,D).
position(b5,N,E).
position(b6,O,F).
position(b7,P,G).
position(b8,Q,H).
position(b9,R,I).

assemble([A,B,C,E,D,F,G,H,I,J,K,L,M,N,O,P,Q,R]) :- 
    Variables=[(A,J),(B,K),(C,L),(D,M),(E,N),(F,O),(G,P),(H,Q),(I,R)],
    all_different(Variables),
    A in 1..3, B in 1..3, C in 1..3, D in 1..3, E in 1..3,
    F in 1..3, G in 1..3, H in 1..3, I in 1..3, J in 1..3,
    K in 1..3, L in 1..3, M in 1..3, N in 1..3, O in 1..3,
    P in 1..3, Q in 1..3, R in 1..3,
    % this is where I am stuck, what to write next

我不知道即使它们是正确的,我也不知道如何进一步解决这个问题.

Answer 1

CLP(FD)微不足道:

:- use_module(library(clpfd)).

board(Board) :-
    Board = [[A1,A2,A3],
             [B1,B2,B3],
             [C1,C2,C3]],
    maplist(top_bottom, [A1,A2,A3], [B1,B2,B3]),
    maplist(top_bottom, [B1,B2,B3], [C1,C2,C3]),
    maplist(left_right, [A1,B1,C1], [A2,B2,C2]),
    maplist(left_right, [A2,B2,C2], [A3,B3,C3]),
    pieces(Ps),
    maplist(board_piece(Board), Ps).

top_bottom([_,_,X,_], [Y,_,_,_]) :- X #= -Y.

left_right([_,X,_,_], [_,_,_,Y]) :- X #= -Y.

pieces(Ps) :-
    Ps = [[-2,3,4,-1], [1,4,-3,-4], [-3,2,4,-4],
          [-4,-3,4,2], [2,-3,-1,4], [-1,-4,3,2],
          [-2,3,2,-1], [-1,-3,1,2], [-2,1,4,-3]].

board_piece(Board, Piece) :-
    member(Row, Board),
    member(Piece0, Row),
    rotation(Piece0, Piece).

rotation([A,B,C,D], [A,B,C,D]).
rotation([A,B,C,D], [B,C,D,A]).
rotation([A,B,C,D], [C,D,A,B]).
rotation([A,B,C,D], [D,A,B,C]).

示例查询及其结果:

?- time(board(Bs)), maplist(writeln, Bs).
11,728,757 inferences, 0.817 CPU in 0.817 seconds
[[-3, -4, 1, 4], [-1, -2, 3, 4], [4, -4, -3, 2]]
[[-1, 4, 2, -3], [-3, 4, 2, -4], [3, 2, -1, -4]]
[[-2, 1, 4, -3], [-2, 3, 2, -1], [1, 2, -1, -3]]

该表示使用1,2,3,4表示正a​​,b,c,d和-1,-2,-3,-4表示负数.

Answer 2

就性能而言，以下内容无法与 @false 的非常快速的解决方案相竞争。

但是，我想向您展示一种不同的方式来表达这一点，以便您可以使用约束求解器来近似 @false 手动找到的更快的分配策略：

:- use_module(library(clpfd)).

board(Board) :-
    Board = [[A1,A2,A3],
             [B1,B2,B3],
             [C1,C2,C3]],
    maplist(top_bottom, [A1,A2,A3], [B1,B2,B3]),
    maplist(top_bottom, [B1,B2,B3], [C1,C2,C3]),
    maplist(left_right, [A1,B1,C1], [A2,B2,C2]),
    maplist(left_right, [A2,B2,C2], [A3,B3,C3]),
    pieces(Ps0),
    foldl(piece_with_id, Ps0, Pss, 0, _),
    append(Pss, Ps),
    append(Board, Bs0),
    maplist(tile_with_var, Bs0, Bs, Vs),
    all_distinct(Vs),
    tuples_in(Bs, Ps).

tile_with_var(Tile, [V|Tile], V).

top_bottom([_,_,X,_], [Y,_,_,_]) :- X #= -Y.

left_right([_,X,_,_], [_,_,_,Y]) :- X #= -Y.

pieces(Ps) :-
    Ps = [[-2,3,4,-1], [1,4,-3,-4], [-3,2,4,-4],
          [-4,-3,4,2], [2,-3,-1,4], [-1,-4,3,2],
          [-2,3,2,-1], [-1,-3,1,2], [-2,1,4,-3]].

piece_with_id(P0, Ps, N0, N) :-
    findall(P, (rotation(P0,P1),P=[N0|P1]), Ps),
    N #= N0 + 1.

rotation([A,B,C,D], [A,B,C,D]).
rotation([A,B,C,D], [B,C,D,A]).
rotation([A,B,C,D], [C,D,A,B]).
rotation([A,B,C,D], [D,A,B,C]).

您现在可以使用 CLP(FD) 的“先失败”策略并首先尝试最受约束的元素。根据这个公式，找到所有 8 个解所需的时间为：

?- time(findall(t, (board(B), term_variables(B, Vs), labeling([ff],Vs)), Ts)).
2,613,325 inferences, 0.208 CPU in 0.208 seconds
Ts = [t, t, t, t, t, t, t, t].

此外，我想提供以下速度竞赛的竞争者，这是我通过对原始程序进行广泛的部分评估而获得的：

solution([[[-4,-3,2,4],[2,-1,-4,3],[2,-1,-3,1]],[[-2,3,4,-1],[4,2,-4,-3],[3,2,-1,-2]],[[-4,1,4,-3],[4,2,-3,-1],[1,4,-3,-2]]]).
solution([[[-3,-4,1,4],[-1,-2,3,4],[4,-4,-3,2]],[[-1,4,2,-3],[-3,4,2,-4],[3,2,-1,-4]],[[-2,1,4,-3],[-2,3,2,-1],[1,2,-1,-3]]]).
solution([[[-3,-2,1,4],[-3,-1,4,2],[4,-3,-4,1]],[[-1,-2,3,2],[-4,-3,4,2],[4,-1,-2,3]],[[-3,1,2,-1],[-4,3,2,-1],[2,4,-4,-3]]]).
solution([[[-3,1,2,-1],[-2,3,2,-1],[2,4,-4,-3]],[[-2,1,4,-3],[-2,3,4,-1],[4,2,-4,-3]],[[-4,3,2,-1],[-4,1,4,-3],[4,2,-3,-1]]]).
solution([[[-3,-1,4,2],[4,-3,-4,1],[2,-1,-4,3]],[[-4,-3,4,2],[4,-1,-2,3],[4,-3,-2,1]],[[-4,-3,2,4],[2,-1,-2,3],[2,-1,-3,1]]]).
solution([[[-1,-3,1,2],[2,-1,-2,3],[4,-3,-2,1]],[[-1,-4,3,2],[2,-4,-3,4],[2,-3,-1,4]],[[-3,2,4,-4],[3,4,-1,-2],[1,4,-3,-4]]]).
solution([[[-1,-4,3,2],[-3,-2,1,4],[-1,-3,1,2]],[[-3,-4,1,4],[-1,-2,3,4],[-1,-2,3,2]],[[-1,4,2,-3],[-3,4,2,-4],[-3,2,4,-4]]]).
solution([[[4,-4,-3,2],[2,-4,-3,4],[2,-3,-1,4]],[[3,2,-1,-2],[3,4,-1,-2],[1,4,-3,-4]],[[1,2,-1,-3],[1,4,-3,-2],[3,2,-1,-4]]]).

使用此公式可以非常快速地找到 8 个解决方案：

?- time(findall(t, solution(B), Ts)).
19 inferences, 0.000 CPU in 0.000 seconds
Ts = [t, t, t, t, t, t, t, t].