# Taking the Fun Out of Puzzles & Games

## 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
% 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.

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

## Wednesday, April 21, 2010

### Pasquale's Problem

Pasquale is a self-employed machinist who sells two products: P and Q. The market will accept up to 100 Ps and 100 Qs per week. P sells for \$200 and Q sells for \$195. The raw materials for each part cost \$50. It takes him 18.5 minutes to build a P and 16.5 minutes to build a Q. Pasquale's supplier also sells partially-assembled raw materials for P and Q. The partially-assembled raw materials save him 3 minutes per P and 3.5 minutes per Q, but they also cost more: an additional \$25 per P and \$29 per Q. Given that Pasquale works at most 40 hours per week, what is Pasquale's maximum weekly profit? For simplicity, assume that the quantity of Ps and Qs he produces each week can be specified by a rational number.

Calculators are allowed, but solving this without a computer is quite a challenge.

Here's a hint (rot13): Ubj zhpu jbhyq Cnfdhnyr or noyr gb znxr vs ur qvqa'g unir gur bcgvba bs hfvat cnegvnyyl-nffrzoyrq enj zngrevnyf?

This puzzle was inspired by a paper by Balakrishnan [1].

[1] Balakrishnan, Jaydeep. The theory of constraints and the make-or-buy decision. Journal of Supply Chain Management, January 1, 2005 .

## Wednesday, April 14, 2010

### Nonograms / Paint by Numbers / Griddlers

Nonograms / Paint by Numbers / Griddlers are "picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups." [1]

Simon Tatham's Portable Puzzle Collection has an excellent implementation of these puzzles, under the name "Pattern". They run under Windows, OS X, Linux, and as a Java applet in a browser.

As usual, the powerful answer set solver clingo makes short work of these puzzles. The source files are:
• nonogram.lp (clingo input file describing the nonogram puzzle type)
• 10x10.lp (lists the constraints in the above 10x10 puzzle)
• display (Perl program to display the solution in human-readable form and check its validity against the original constraints)
In this model of the puzzle, the objective is to find the cell in which each unbroken line of filled-in squares ("run") starts, subject to the following constraints:
• Two runs in the same row or column must be separated by at least one cell of whitespace
• From the starting cells and lengths of the runs in a row or column, we can infer which cells in that row or column must be filled in. The set of cells filled in by the row runs must be the same as the set of cells filled in by the column runs.
Here's the output of solving the above 10x10 puzzle:
```\$ clingo nonogram.lp 10x10.lp | perl display
X X X . .   . . . . .
. . X . .   . . . . .
. . . . .   . . X X X
. . . . .   . . X . X
X . X . X   X . X . .

X . X X X   X X X . X
. . X X X   X . X . X
X . X X X   X X X . X
X X X X X   X X X . .
X X . . X   X X X . .
OK
SATISFIABLE

Models      : 1+
Time        : 0.020
Prepare   : 0.010
Prepro.   : 0.010
Solving   : 0.000
```
Here's the output from solving a 30x30 puzzle, along with an image of the initial puzzle state and the corresponding Simon Tatham's Portable Puzzle Collection save file.

[1] Wikipedia, Nonogram, (as of Apr. 14, 2010, 08:56 GMT).

## Monday, April 12, 2010

### Lunar Lockout

Lunar Lockout is similar to a standard sliding puzzle, but with more degrees of freedom. Here's a way to solve Lunar Lockout puzzles using the answer set solver clingo. We'll demonstrate the approach on "Advanced Solitaire Puzzle 1" from the link above.

This solution uses a main file to specify how the pieces move (lunar.lp). There is also a file to specify the initial location of the pieces for a particular puzzle (advsolitaire1.lp).

Running the solver:
```\$ clingo -c maxturns=2 advsolitaire1.lp lunar.lp