FlowerFinder by William Waite

FlowerFinder is a puzzle with only 6 pieces but a rather large state space. One objective is to place them into the frame in two layers so that in each of the 9 circles, exactly 3 petals are visible.

Each circle can be one of four types, which we will call "top-left", "top-right", "bottom-left", and "bottom-right". We will assign each piece a number from 1 to 6. Each piece is defined as a sequence of three circle types. For example, in the photo, the circles in piece 1, from top to bottom, are of type down-left, up-right, and up-left. Before a piece is placed in the frame, it can (optionally) be flipped horizontally and (optionally) be flipped vertically. We define locations 1,2,3 as the bottom of the frame from left to right, and locations 4,5,6 as the locations in the top of the frame, perpendicular to 1,2,3. Without loss of generality, we can assume that piece 1 is in location 1 or 2, and is not flipped horizontally or vertically. Finally, we require that the petals in each circle in the top row align with the petals in the corresponding circle in the bottom row.

$ clingo 0 flowerfinder.lp
% flowerfinder.lp source

% piece(P) - P is a piece.
% piece(P,A,B,C) - P's circles, in order, are of type A,B, and C.
% piece(P,N,X) - P's Nth circle (1-based) is of type X.
% transform(TransformType,CircleBefore,CircleAfter) - a transformation of
%  TransformType changes a circle of type CircleBefore to one of type
%  CircleAfter
% align(P,N,Q,M) - when all the pieces are in the frame, circle N of piece P
%  aligns with circle M of piece Q.
% fliph(P) - piece P is flipped horizontally before placing it in the frame.
% flipv(P) - piece P is flipped vertically before placing it in the frame.
% fliphed(P,N,X) - after horizontal flipping (if any), the Nth circle of piece P is of type X.
% flipved(P,N,X) - after vertical flipping (if any), the Nth circle of piece P is of type X.
% orientation(P,N,X) - after 90 degree rotation (if any), the Nth circle of piece P is of type X.
% pieceloc(P,L) - piece P is in location L in the frame (1..6).

piece(1..6).
piece(1,downleft,upright,upleft).
piece(2,upright,upleft,upright).
piece(3,downright,upleft,downleft).
piece(4,upright,downleft,upright).
piece(5,downleft,downright,upright).
piece(6,downright,upright,downleft).

piece(P,1,A) :- piece(P,A,B,C).
piece(P,2,B) :- piece(P,A,B,C).
piece(P,3,C) :- piece(P,A,B,C).

transform(fliph,downleft,downright).
transform(fliph,downright,downleft).
transform(fliph,upleft,upright).
transform(fliph,upright,upleft).
transform(flipv,downleft,upleft).
transform(flipv,downright,upright).
transform(flipv,upleft,downleft).
transform(flipv,upright,downright).
transform(rot90,downleft,downright).
transform(rot90,upright,upleft).
transform(rot90,downright,upright).
transform(rot90,upleft,downleft).

align(1,1,4,1).
align(1,2,5,1).
align(1,3,6,1).
align(2,1,4,2).
align(2,2,5,2).
align(2,3,6,2).
align(3,1,4,3).
align(3,2,5,3).
align(3,3,6,3).


% There are as many locations as pieces.
location(P) :- piece(P).

0 { fliph(P) } 1 :- piece(P).
0 { flipv(P) } 1 :- piece(P).
1 { pieceloc(P,L) : location(L) } 1 :- piece(P).

% Without loss of generality, assume piece 1 is in location 1 or 2 (that is,
% on a side or in the middle), and not flipped horizontally or vertically.
:- pieceloc(1, L), L > 2.
:- fliph(1).
:- flipv(1).

% Two different pieces can't be in the same location.
:- pieceloc(P,L),pieceloc(Q,L), P != Q.

% Pieces in locations 4,5,6 are rotated 90 degrees.
rot90(4;5;6).

fliphed(P,N,B) :- piece(P,N,A), transform(fliph,A,B), fliph(P).
fliphed(P,N,A) :- piece(P,N,A), not fliph(P).
flipved(P,4-N,B) :- fliphed(P,N,A), transform(flipv,A,B), flipv(P).
flipved(P,N,A) :- fliphed(P,N,A), not flipv(P).
orientation(P,4-N,B) :- flipved(P,N,A), transform(rot90,A,B), rot90(P).
orientation(P,N,A) :- flipved(P,N,A), not rot90(P).

:- pieceloc(P1,L1), pieceloc(P2,L2), align(L1,C1,L2,C2), orientation(P1,C1,O1), orientation(P2,C2,O2), O1 != O2.


#hide.
#show fliph/1.
#show flipv/1.
#show pieceloc/2.

Answer: 1
fliph(3) fliph(5) fliph(6) flipv(2) flipv(3) pieceloc(1,1) pieceloc(2,2) pieceloc(3,3) pieceloc(4,6) pieceloc(5,4) pieceloc(6,5)
SATISFIABLE

Models      : 1
Time        : 0.020
  Prepare   : 0.010
  Prepro.   : 0.000
  Solving   : 0.010

So the unique solution is to horizontally flip pieces 3, 5, and 6, vertically flip 2 and 3, put the pieces in the specified locations.

How large is the state space? The first piece is in one of two locations, and there are 5! ways to place the remaining pieces, 2⁵ ways to represent the "horizontally flipped" state of those pieces, and 2⁵ ways to represent the "vertically flipped" state of each of those pieces. Finally, the top layer can either be perpendicular to the bottom layer or not. By this reasoning, there are 5! · 2⁵ · 2⁵ · 2 = 257760 different ways to place the 6 pieces in the frame.