Board Assembly mit Einschränkungen

Question

Ich mache dieses Problem, aber ich bin völlig neu in Prolog und ich habe keine Ahnung, wie es geht.

Neun Teile einer elektronischen Platine haben eine quadratische Form, die gleiche Größe und jeder Rand jedes Teils ist mit einem Buchstaben und einem Plus- oder Minuszeichen gekennzeichnet. Die Teile müssen zu einer vollständigen Platine zusammengebaut werden, wie in der Abbildung unten gezeigt, so dass die gemeinsamen Kanten den gleichen Buchstaben und die entgegengesetzten Zeichen haben. Schreiben Sie einen Planer in Prolog, so dass das Programm "assemble" als die Abfrage ausführt und ausgibt, wie die Teile zusammengesetzt werden, d. H. Die Positionen und Positionen der Teile bestimmen wr.t. die aktuellen Positionen so, dass sie zusammenpassen, um das komplette Brett zu machen.

Ich habe versucht, es zu lösen, und ich habe die folgenden Klauseln geschrieben:

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 

Ich weiß nicht einmal, ob sie richtig sind, und ich bin nicht sicher, wie weiter zu verfahren ist zu lösen dieses Problem.

Answer 1

In Bezug auf Leistung, die folgende ist kein Anwärter auf @ falsch ist sehr schnelle Lösung.

Allerdings würde Ich mag Ihnen zeigen, einen anderen Weg, dies zu formulieren, so dass Sie die Constraint-Solver verwenden können, die schnellere Allokationsstrategie anzunähern, die manuell gefunden @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]). 

Sie jetzt verwenden können, die "First Fail" -Strategie von CLP (FD) und versuche zuerst die am meisten eingeschränkten Elemente. Mit dieser Formulierung, die Zeit benötigt, um alle 8 Lösungen zu finden ist:

?- 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]. 

Außerdem würde Ich mag die folgenden Anwärter für die Geschwindigkeit Wettbewerb anbieten zu können, die mich mit einer umfangreichen Teilbewertung des ursprünglichen Programms erhalten:

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

Die 8-Lösungen werden sehr schnell mit dieser Formulierung gefunden:

?- 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

Trivial mit 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]). 

Beispiel Abfrage und sein Ergebnis:

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

Diese Darstellung verwendet 1,2,3,4 zu bezeichnen positive a, b, c, d, und -1, -2, -3, -4 für die negativen.

Answer 3

Dies ist nur eine kleine Verbesserung der schönen @ mat-Lösung. Die Idee ist, den Etikettierungsprozess zu überdenken. Das ist maplist(board_piece,Board,Ps) in dem es heißt (semi-prozedural):

Für alle Elemente in Ps, damit für alle Stücke in dieser Reihenfolge: Nehmen Sie ein Stück und an einer anderen Stelle auf dem Brett gedreht oder nicht.

Dies bedeutet, dass jede Platzierung in voller Freiheit erfolgen kann. Um Ihnen eine schwache Reihenfolge zu zeigen, könnte man nehmen: A1,A3,C1,C3,B2 und dann den Rest. Auf diese Weise werden die tatsächlichen Beschränkungen nicht sehr ausgenutzt.

Es scheint jedoch keinen guten Grund zu geben, dass die zweite Kachel nicht in unmittelbarer Nähe zur ersten liegt.Hier ist so ein verbesserter Auftrag:

 ..., 
    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). 

Jetzt bekomme ich

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

und ohne das Ziel maplist(maplist(tile), Board),

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

und alle Lösungen

?- 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. 

vorher aufzuzuzählen (@ Mat Originalversion) die erste Lösung hat:

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

und alle Lösungen:

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