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 problem can be solved quite easily with a linear programming solver, such as the one at http://www.zweigmedia.com/RealWorld/simplex.html. Let p and q be the number of Ps and Qs produced each week using only raw materials, and let p' and q' be the number of Ps and Qs produced each week using partially-assembled raw materials.

Maximize z = 150p + 125p'+ 145q + 116q' subject to 
18.5p + 16.5q + 15.5p' + 13q' <= 2400
p + p' <= 100
q + q' <= 100

Optimal Solution: z = 20581.1; p = 40.5405, p' = 0, q = 100, q' = 0

So the most Pasquale can make is $20581.10/week. He can do this by avoiding the partially-assembled raw materials entirely, making as many Qs as the market will accept (100), and spending the remainder of his time on Ps (40.5405).

Click here to view the solution

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 .

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)
  

  % constraint(Type,N,I,Len) - the Ith group in row/col N must be Len blocks long
  % row(Y). Y is a valid row number.
  % col(X). X is a valid column number.
  % color(X,Y). From a column constraint, we infer that (X,Y) is colored in
  % rowcolor(X,Y). From a row constraint, we infer that (X,Y) is colored in
  % rowrun(Y,I,X). The Ith run in row Y starts at cell (X,Y).
  % colrun(X,I,Y). The Ith run in col X starts at cell (X,Y).
  
  % This following lines simplifies data entry directly into clingo by allowing
  % constraints to be entered as a group.  This could easily be elminated with
  % some pre-processing in, say, Perl.
  %
  % constraints(col/row,I,A,B,C,...) - The lengths of blocks of filled-in
  %    cells in column/row I are A,B,C,...
  constraint(Type,N,1,A) :- constraints(Type,N,A).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,5,E) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,5,E) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,5,E) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,6,F) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,6,F) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,7,G) :- constraints(Type,N,A,B,C,D,E,F,G).
  
  
  row(1..ymax).
  col(1..xmax).
  ymax(ymax).
  xmax(xmax).
  % For each constraint, choose a starting cell for the run.
  1 { rowrun(Y,I,X) : col(X) : col(X+Len-1) } 1 :- constraint(row,Y,I,Len).
  1 { colrun(X,I,Y) : row(Y) : row(Y+Len-1) } 1 :- constraint(col,X,I,Len).
  
  % Must leave at least one space between two adjacent run.
  :- rowrun(N,I,Start1), rowrun(N,J,Start2), constraint(row,N,I,Len), I < J, Start2 < Start1 + Len + 1.
  :- colrun(N,I,Start1), colrun(N,J,Start2), constraint(col,N,I,Len), I < J, Start2 < Start1 + Len + 1.
  
  % Infer the color of the cells in each run
  color(X,Start..Start+Len-1) :- colrun(X,I,Start), constraint(col,X,I,Len), row(X).
  rowcolor(Start..Start+Len-1,Y) :- rowrun(Y,I,Start), constraint(row,Y,I,Len), col(Y).
  
  % The inferred color from the row runs must be the same as those from the column runs.
  :- color(X,Y), not rowcolor(X,Y), row(X), col(Y).
  :- not color(X,Y), rowcolor(X,Y), row(X), col(Y).
  
  #hide.
  #show color/2.
  #show xmax/1.
  #show ymax/1.
  #show constraint/4.
  

• 10x10.lp (lists the constraints in the above 10x10 puzzle)
  

  #const ymax=10. #const xmax=10. #const maxruns=4.
  % constraints(col/row,I,A,B,C,...) - The lengths of blocks of filled-in
  % cells in column/row I are A,B,C,...
  
  constraints(col,1,1,2,3).
  constraints(col,2,1,2).
  constraints(col,3,2,5).
  constraints(col,4,4).
  constraints(col,5,6).
  constraints(col,6,6).
  constraints(col,7,1,3).
  constraints(col,8,8).
  constraints(col,9,1).
  constraints(col,10,2,3).
  constraints(row,1,3).
  constraints(row,2,1).
  constraints(row,3,3).
  constraints(row,4,1,1).
  constraints(row,5,1,1,2,1).
  constraints(row,6,1,6,1).
  constraints(row,7,4,1,1).
  constraints(row,8,1,6,1).
  constraints(row,9,8).
  constraints(row,10,2,4).
  

• display (Perl program to display the solution in human-readable form and check its validity against the original constraints)
  

  #!/usr/bin/perl
  
  use strict;
  use warnings;
  while (<>) {
    if (/color/) {
      my $xmax = 0;
      my $ymax = 0;
      my @color;
      my %constraint;
      while(/constraint[(](row|col),(\d+),(\d+),(\d+)/g) {
        $constraint{$1}[$2][$3-1] = $4;
      }
  
      while(/color[(](\d+),(\d+)/g) {
        $color[$1][$2] = 'b';
      }
      while(/ymax[(](\d+)/g) {
        $ymax = $1;
      }
      while(/xmax[(](\d+)/g) {
        $xmax = $1;
      }
      my $check = checksol(\@color, \%constraint, $xmax, $ymax);
      print if $check ne "OK"; # when debugging, show the raw data
      foreach my $y (1..$ymax) {
        foreach my $x (1..$xmax) {
          print $color[$x][$y] && $color[$x][$y] eq 'b' ? 'X' : '.', " ";
          print "  " if $x % 5 == 0 && $x > 0 && $x < $xmax;
        }
        print "\n";
        print "\n" if $y % 5 == 0 && $y > 0 && $y < $ymax;
      }
      print "$check\n";
    }
    else {
      print;
    }
  }
  
  
  
  sub checksol {
    my ($color, $constraint, $xmax, $ymax) = @_;
  
    foreach my $y (1..$ymax) {
      next unless $constraint->{'row'}[$y];
      my $row;
      foreach my $x (1..$xmax) {
        $row .= $color->[$x][$y] || " ";
      }
      my @counts = map length, $row =~ /(b+)/g;
      return "ERROR: row $y: @counts should be @{ $constraint->{'row'}[$y] }"
        if "@counts" ne "@{ $constraint->{'row'}[$y] }";
    }
    foreach my $x (1..$xmax) {
      next unless $constraint->{'col'}[$x];
      my $col;
      foreach my $y (1..$ymax) {
        $col .= $color->[$x][$y] || " ";
      }
      my @counts = map length, $col =~ /(b+)/g;
      return "ERROR: column $x: @counts should be @{ $constraint->{'col'}[$x] }"
        if "@counts" ne "@{ $constraint->{'col'}[$x] }";
    }
    return "OK";
  }
  

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
Answer: 1
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).

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

% piece(P). P is a piece.
% piece(T,P,X,Y). piece P is at (X,Y) at the end of turn T
% turn(T). T is a turn.
% reachable(T,P,X,Y). It's possible for piece P to be at (X,Y) at the end of turn T
% move(T,P). piece P moves on turn T.
% move(T,P,X,Y). Piece P moves to (X,Y) on turn T.
% direction(D). D is a direction

turn(0..maxturns).
direction(up;down;left;right).
piece(P) :- init(P,X,Y).
piece(T,P) :- piece(T,P,X,Y).
piece(0,P,X,Y) :- init(P,X,Y).

% Four different types of sub-moves
% 1. slide down
reachable(T+1,P,X,YQ+1) :-
  reachable(T+1,P,X,Y),
  piece(T,X,YQ), not piece(T,P,X,YQ),
  [ piece(T,X,Z) : YQ < Z : Z < Y : coordinate(Z) ] 0,
  coordinate(X;Y;YQ;YR),
  turn(T;T+1),
  piece(P),
  YQ+1 < Y.

% 2. slide up
reachable(T+1,P,X,YQ-1) :-
  reachable(T+1,P,X,Y),
  piece(T,X,YQ), not piece(T,P,X,YQ),
  [ piece(T,X,Z) : Y < Z : Z < YQ : coordinate(Z) ] 0,
  coordinate(X;Y;YQ;YR),
  turn(T;T+1),
  piece(P),
  Y < YQ-1.

% 3. slide right
reachable(T+1,P,XQ-1,Y) :-
  reachable(T+1,P,X,Y),
  piece(T,XQ,Y), not piece(T,P,XQ,Y),
  [ piece(T,Z,Y) : X < Z : Z < XQ : coordinate(Z) ] 0,
  coordinate(X;Y;XQ;XR),
  piece(P;R),
  turn(T;T+1),
  X < XQ-1.

% 4. slide left
reachable(T+1,P,XQ+1,Y) :-
  reachable(T+1,P,X,Y),
  piece(T,XQ,Y), not piece(T,P,XQ,Y),
  [ piece(T,Z,Y) : XQ < Z : Z < X : coordinate(Z) ] 0,
  coordinate(X;Y;XQ;XR),
  piece(P),
  turn(T;T+1),
  XQ+1 < X.

move(T,P) :- move(T,P,X,Y).

piece(T,X,Y) :- piece(T,P,X,Y).

% One move must be selected at each turn.
1 { move(T,P,X,Y) : piece(P) : coordinate(X;Y) } 1 :-
  turn(T),
  T > 0.

% A move must be to a reachable location.
:- move(T,P,X,Y), not reachable(T,P,X,Y).

% Can't leave a piece in the same place
:- move(T+1,P,X,Y), piece(T,P,X,Y), turn(T;T+1).

% Ships disappear when they reach the goal.
shipdisappears(T,P) :- move(T,P,X,Y), ship(P), goal(X,Y).

% If a piece is moved to (X,Y), and it's not a ship that disappears on
% that move, then it ends up at (X,Y) a the end of that turn.
piece(T,P,X,Y) :- move(T,P,X,Y), not shipdisappears(T,P).

% Anything that didn't move on a particular turn is in the same place
% at the beginning of the next turn.
piece(T+1,P,X,Y) :-
  not move(T+1,P),
  piece(T,P,X,Y),
  piece(P),
  coordinate(X;Y),
  turn(T;T+1).

% A piece can stay in the same location to the next turn.
reachable(T+1,P,X,Y) :- piece(T,P,X,Y), turn(T;T+1).

% The puzzle is solved when every ship has disappeared (by reaching
% the goal cell)
notsolved(T) :- piece(T,P), ship(P).
solved :- not notsolved(T), turn(T).

:- not solved.

#hide.
#show move/4.

There is also a file to specify the initial location of the pieces for a particular puzzle (advsolitaire1.lp).

coordinate(-3..3).
ship(x).
goal(0,0).
init(x,-1,3).
init(1,1,1).
init(2,-1,0).
init(3,2,-1).
init(4,-1,-3).
init(5,0,-3).

Running the solver:

$ clingo -c maxturns=2 advsolitaire1.lp lunar.lp
Answer: 1
move(1,4,0,-2) move(2,x,0,0)
SATISFIABLE

According to the solver, the puzzle can be solved in two moves, as follows:

1. move piece 4 to (0,-2)
   
2. move piece x to (0,0).
   

In our coordinate system, the goal is in the center of the grid at (0,0), so the first move locates piece 4 two squares below the goal, and the second move takes the ship home. I challenge anyone to solve "advanced solitaire #30" in the minimum number of moves (18) without using a computer.

Hinomaru: Japanese Flag Puzzle by Pavel Curtis

Hinomaru is a beautiful puzzle in which "the goal is to put the 12 two-sided domino-shaped pieces into the tray such that the patterns on the face-up sides form a picture of Hinomaru, the Japanese national flag (i.e., a large, solid red disk in the middle of a white field.)".

It looks temptingly simple: "It's a red disk made out of only 12 pieces, how hard can it be?". But in fact it can be maddeningly difficult to solve by hand. Several of my friends have spent many fruitless hours on this puzzle. It lures you in with its deceptive simplicity, and keeps you going by making it seem that you're always just one piece away from a solution.

However, the answer set solver clingo makes short work of this puzzle. It took about 30 minutes to program the solution: hinomaru.lp.

% Hinomaru puzzle by Pavel Curtis (http://www.keltis.us/puzzles)
%
% The puzzle consists of 12 2x1 dominoes and a 6x4 board on which to place
% them.  We will assign the upper-left square of the board the coordinates
% (1,1).  Each domino has two sides, or "faces" as we will call them. Though
% there are 24 total sides, there only 11 distinct faces. The puzzle comes
% with a sheet that identifies each piece with a letter A through L; we will
% adopt that convention here. It quickly becomes apparent that each face has
% only a few possible valid locations. Solving the puzzle is then a matter
% of choosing a face and valid location for each piece such that each square
% of the board is occupied by exactly one piece.

%
% We use the following two predicates to describe the puzzle:
%
% faceloc(Face, Location) - Location is a valid location for Face. A location
%   represented by a 4-digit number that specifies the coordinates of the two
%   squares occupied by the domino.  For example, a Location of 5464, means
%   that the domino would occupy the squares (5,4) and (6,4).
%
% pieceface(Piece, Face) - Face is one of the two faces of Piece. For example,
%   the two faces of the "I" piece are referred to here as "H0" and "BLANK".

% List the valid locations for each face.
faceloc("A0",   1121;5464).
faceloc("A1",   2122;2434;4151;5354).
faceloc("B1",   1222;5363).
faceloc("BLANK",1112;1213;1314;6162;6263;6364).
faceloc("C0",   2324;2131;4454;5152).
faceloc("C1",   2223;3444;3141;5253).
faceloc("FILL", 3233;3242;3343;4243).
faceloc("G1",   2333;3132;4252;4344).
faceloc("H0",   1424;5161).
faceloc("H1",   2232;3334;4142;4353).
faceloc("L0",   1323;5262).

% List the two faces for each piece.
pieceface("A", "A0";"A1").
pieceface("B", "A0";"B1").
pieceface("C", "C0";"C1").
pieceface("D", "C0";"BLANK").
pieceface("E", "C1";"BLANK").
pieceface("F", "A1";"FILL").
pieceface("G", "A1";"G1").
pieceface("H", "H0";"H1").
pieceface("I", "H0";"BLANK").
pieceface("J", "B1";"FILL").
pieceface("K", "FILL";"G1").
pieceface("L", "L0";"BLANK").
piece(Piece) :- pieceface(Piece, Face).

% For each piece, select one face, and a valid location for that face.
1 {
  piecefaceloc(Piece, Face, Loc)
  : pieceface(Piece, Face)
  : faceloc(Face, Loc)
} 1 :- piece(Piece).

% Each piece uses two squares.
usedsquare(Piece, Loc/100;Loc #mod 100) :-
    piecefaceloc(Piece, Face, Loc),
    faceloc(Face, Loc),
    pieceface(Piece, Face).

% A single square cannot be occupied by two different pieces.
:- usedsquare(Piece1, Square), usedsquare(Piece2, Square), Piece1 != Piece2.

p(Piece, Loc) :- piecefaceloc(Piece, Face, Loc).

#hide.
#show p/2.

It is based on the observation that there are only a few locations — usually four, but as few as two and as many as six — where each piece can contribute to the final image. If we place every piece in one of its possible locations, then we will have solved the puzzle.

Running the solver:

$ clingo hinomaru.lp
Answer: 1
p("D",6263) p("H",5161) p("F",2122) p("K",2333) p("E",5253) p("G",4344)
p("J",3242) p("C",3141) p("A",2434) p("B",5464) p("I",1112) p("L",1314)
SATISFIABLE

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

In this solution, piece "A" occupies squares (2,4) and (3,4), piece "B" occupies squares (5,4) and (6,4), and so forth. I decided not to make solver output which side of each piece faces up, because (a) it's obvious when putting the piece in its location that only one side works in that location, and (b) there are no standard names for the faces (though the puzzle's designer did provide names for the pieces).

Is the solution really unique up to rearranging face-up pieces? That is, given one solution, is it possible to get another solution by using the other face of one or more pieces? Change the line

p(Piece, Loc) :- piecefaceloc(Piece, Face, Loc).

to

p(Piece, Face) :- piecefaceloc(Piece, Face, Loc).

And re-run:

clingo hinomaru.lp  --project 0
Answer: 1

SATISFIABLE
...

There's only one answer set, so the solution is indeed unique.

How many different ways are there to arrange those faces to create a solution? Change the code back and run:

$ clingo --project hinomaru.lp 0
...
Models      : 96
...

While we're at it, in how many different ways could the 12 pieces be arranged on the board, regardless of whether they form a disc or not? First we'll count the number of different ways in which a 6x4 board can be tiled with indistinguishable dominoes which are blank on both sides. I'm sure there's a better way to do this, but an easy — though computationally inefficient — approach is to use clingo.

Here's dominoes.lp:

#const xmax=6.
#const ymax=6.
#const ndominos=xmax * ymax / 2.
possibleplacement(X,Y,X+1,Y) :- X=1..xmax-1,Y=1..ymax.
possibleplacement(X,Y,X,Y+1) :- X=1..xmax,Y=1..ymax-1.
square(X,Y) :- X=1..xmax,Y=1..ymax.
% Select the valid placements.
ndominos { placement(X1,Y1,X2,Y2) : possibleplacement(X1,Y1,X2,Y2) } ndominos.
% Each placement uses two squares.
coveredsquare(X1,Y1) :- placement(X1,Y1,X2,Y2).
coveredsquare(X2,Y2) :- placement(X1,Y1,X2,Y2).
% There must be no uncovered squares.
:- square(X,Y), not coveredsquare(X,Y).
#hide.  #show placement/4.

Running the solver:

$ clingo dominoes.lp 0
...
Models      : 281
...

Okay, so for each of those 281 ways to tile the board with dominoes, we can replace the dominoes with puzzle pieces in 12! ways, and we can choose which sides are face up in 2¹² ways. Now 281 · 12! · 2¹² is about 5.5 · 10¹⁴, so good luck trying to solve Hinomaru by placing pieces randomly!