prolog – 有约束的董事会大会

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

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

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

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

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

在性能方面,以下是@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].
相关文章
相关标签/搜索