Tuesday, May 4, 2010

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

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)

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, 25 ways to represent the "horizontally flipped" state of those pieces, and 25 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! · 25 · 25 · 2 = 257760 different ways to place the 6 pieces in the frame.