Board Assembly with constraints

Question

I am doing this problem but I am completely new to Prolog and I have no idea how to do it.

Nine parts of an electronic board have square shape, the same size and each edge of every part is marked with a letter and a plus or minus sign. The parts are to be assembled into a complete board as shown in the figure below such that the common edges have the same letter and opposite signs. Write a planner in Prolog such that the program takes 'assemble' as the query and outputs how to assemble the parts, i.e. determine the locations and positions of the parts w.r.t. the current positions so that they fit together to make the complete board.

I have tried solving it and I have written the following clauses:

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

I don't know even if they are correct and I am not sure how to proceed further to solve this problem.

Answer 1

In terms of performance, the following is no contender to @false's very fast solution.

However, I would like to show you a different way to formulate this, so that you can use the constraint solver to approximate the faster allocation strategy that @false found manually:

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

You can now use the "first fail" strategy of CLP(FD) and try the most constrained elements first. With this formulation, the time needed to find all 8 solutions is:

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

In addition, I would like to offer the following contender for the speed contest, which I obtained with an extensive partial evaluation of the original program:

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

The 8 solutions are found very rapidly with this formulation:

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

Example query and its result:

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

This representation uses 1,2,3,4 to denote positive a,b,c,d, and -1,-2,-3,-4 for the negative ones.

Answer 3

This is only a tiny improvement to @mat's beautiful solution. The idea is to reconsider the labeling process. That is maplist(board_piece,Board,Ps) which reads (semi-procedurally):

For all elements in Ps, thus for all pieces in that order: Take one piece and place it anywhere on the board rotated or not.

This means that each placement can be done in full liberty. To show you a weak order, one might take: A1,A3,C1,C3,B2 and then the rest. In this manner, the actual constraints are not much exploited.

However, there seems to be no good reason that the second tile is not placed in direct proximity to the first. Here is such an improved order:

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

Now, I get

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

and without the goal maplist(maplist(tile), Board),

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

and to enumerate all solutions

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

previously (@mat's original version) the first solution took:

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

and all solutions:

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