제한이있는 보드 조립

Question

이 문제를 수행하고 있지만 완전히 프롤로그에 익숙하지 않으며 어떻게 수행해야할지 모릅니다.

전자 보드의 9 개 부분은 정사각형 모양을 가지며 각 부분의 동일한 크기와 각 가장자리에는 문자와 플러스 또는 마이너스 기호가 표시되어 있습니다. 부품은 아래 그림과 같이 완전한 보드로 조립되어야 공통 가장자리가 같은 문자와 반대 기호를 갖게됩니다. 프로그램이 쿼리로 '어셈블'을 수행하고 파트를 어셈블하는 방법, 즉 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 

나는 그들이 올바른 경우에도 모르는 내가 해결하기 위해 더 이상 진행하는 방법을 잘 모르겠습니다을 이 문제. CLP와 간이

Answer 1

성능면에서 다음이 @의 거짓 매우 빠른 솔루션에는 경쟁자가 없다.

:- 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]). 

이제 사용할 수 있습니다

그러나, 나는 당신이 수동으로 발견 @false 빠른 할당 전략을 대략적인 제약 해결사를 사용할 수 있도록, 당신이를 공식화 할 수있는 다른 방법을 보여 드리고자합니다 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 개 솔루션

이 배합으로 매우 빠르게 찾을 수 있습니다

당신의 '위치/3` 사실에

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

Answer 2

(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]] 

이 표현은 포지티브 형 A, B, C를 나타내는데 1,2,3,4 사용 d, -1, -2, -3, -4가됩니다.

Answer 3

이것은 @ mat의 아름다운 해결책에 대한 약간의 개선점 일뿐입니다. 아이디어는 라벨링 과정을 재고하는 것입니다. Ps의 모든 요소에 대한

, 따라서 순서에있는 모든 조각이 : 한 조각을 가지고 보드가 회전 여부를 아무 곳이나 배치 즉 (반 절차 적으로) 읽는 maplist(board_piece,Board,Ps)이다.

즉, 각 게재 위치를 자유롭게 사용할 수 있습니다. 약한 주문을 표시하려면 다음 중 하나가 걸릴 수 있습니다 : A1,A3,C1,C3,B2 다음 나머지. 이러한 방식으로 실제 제약 조건은 많이 활용되지 않습니다.

그러나 두 번째 타일이 첫 번째 타일에 직접 인접하지 않는 이유는 없습니다.다음은 이러한 개선 된 순서입니다 : 내가

?- time(board(Bs)), maplist(writeln, Bs). 
% 17,179 inferences, 0.005 CPU in 0.005 seconds (99% CPU, 3363895 Lips) 
[[-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]] 

을 얻고, 지금

 ..., 
    pieces(Ps), 
    TilesOrdered = [B2,A2,A3,B3,C3,C2,C1,B1,A1], 
    tiles_withpieces(TilesOrdered, Ps). 

tiles_withpieces([], []). 
tiles_withpieces([T|Ts], Ps0) :- 
    select(P,Ps0,Ps1), 
    rotation(P, T), 
    tiles_withpieces(Ts, Ps1). 

목표 maplist(maplist(tile), Board),

% 11,010 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 3225961 Lips) 

모든 솔루션을

?- time((setof(Bs,board(Bs),BBs),length(BBs,N))). 
% 236,573 inferences, 0.076 CPU in 0.154 seconds (49% CPU, 3110022 Lips) 
BBs = [...] 
N = 8. 

이전을 열거 할 수없이 (@ 매트의 원래 버전) 첫 번째 해결책에 나섭니다 :

% 28,874,632 inferences, 8.208 CPU in 8.217 seconds (100% CPU, 3518020 Lips) 

모든 솔루션 :

% 91,664,740 inferences, 25.808 CPU in 37.860 seconds (68% CPU, 3551809 Lips)