Abstract
Two puzzles are presented and discussed with a view to using them as classroom drill exercises in Integer Program Modeling. Mathematical formulations are presented for each puzzle and working models are offered as a resource for instructors.
The use of mathematical notation in the formulation of linear and integer program models is a key skill in the repertoire of an OR practitioner and standard text books provide many examples with which to instill this into students. These may occasionally be supplemented with problems taken from recreational mathematics that require similar intellectual effort and hone the same skills but also provide a little light relief from the more serious questions favored by the text books. Two puzzles, namely Su Doku and The Log Pile, are presented here for this purpose.
The puzzles are modeled using XpressMosel rather than Excel. When problems requiring multiple subscripts, as in these cases, are modeled effectively, the activity of converting mathematical formulations into working models using languages such as Mosel and AMPL represents a straightforward exercise. This is not always the case when building spreadsheet versions. Indeed, in many cases, a spreadsheet implementation provides an equal or perhaps even greater challenge than that provided by the actual formulation.This problem becomes especially acute as the number of subscripts required by the model increases.
The Log Pile is the more difficult of the two puzzles, both to solve by conventional means and as a modeling exercise. The formulation requires a familiarity with the use of binary variables to enforce logical conditions. Some advice in this respect may be found in Chlond and Toase.
Su Doku is a number puzzle of uncertain origin. It is played on a 9 x 9 grid divided into an array of 3 x 3 grids and a puzzle typically begins with integers assigned to an arbitrary number of cells.
The aim is to fill in all the empty cells such that each row, each column and each 3 x 3 grid contains all the integers from 1 through 9. Note the similarity to Euler's Latin Squares (see Gulberg).
Su Doku has been a regular daily feature in The Times since November 2004 and their website,, provides some further background. The website by Wayne Gould has available a computer program to generate random puzzles and gives tips and advice on solving these by inspection. Interestingly, the claim is made that the Su Doku is not mathematical.
For the purpose of formulation it is convenient to view the puzzle as three rows of three
grids where each grid consists of three rows of three cells. We may then define binary variables
x_{i,j,k,m,n}= 1 if cell {i,j} of grid {m,n} = k, 0 otherwise. We
also define subscript ranges I=1..3 (cell rows), J=1..3 (cell columns), K=1..9 (
integers), M=1..3 (grid rows) and N=1..3 (grid columns).
The conditions required by the puzzle are modeled as follows.
Each cell contains a single integer.
Each integer appears once only in each grid.
Each integer appears once only in each row.
Each integer appears once only in each column.
The obvious way to enforce the fixed cells is, in each case, to set the repective decision
variable to 1. For example x_{1,1,5,1,1} = 1 forces the top left cell to assume
the value 5. A typical puzzle contains between 20 and 30 given cell values and to input each
in this way is unnecessarily tedious. A more convenient method is to input the puzzle as a
square matrix as follows with given values in the appropriate cells and zeros elsewhere.
Using P as input the following Mosel code will compute the coordinates of the ones
in X and set the values accordingly.
forall(i in crow,j in ccol,m in grow,n in gcol) do
a := 3*(m1)+i
b := 3*(n1)+j
t := P(a,b)
if(t >= 1) then
kc(i,j,t,m,n) := X(i,j,t,m,n) = 1
endif
enddo
Since the aim of the puzzle is merely to fulfil these conditions we may select any appropriate
objective function to complete the formulation.
An XpressMosel model to solve the puzzle is here.
The Log Pile is a piece assembly puzzle available at . It consists of 10 pieces, each piece being a rectangular block
with one side divided into five slots. Each slot has either a protruding peg, a hole, or neither. When the
puzzle is purchased it is packed into a box such that pegs and holes neatly coincide. This requires
that five pieces are laid horizontally side by side with the holes/pegs face upwards and the remaining
five pieces laid vertically side by side over the top with holes/pegs face downwards (see figure below).
The objective is to empty the pieces from the box and, quite simply, to repack them.
In order to describe the puzzle pieces we assign the value 1 to a slot that contains a peg,
1 to a slot that contains a hole, and 0 to a slot that contains neither a peg nor a whole.
The complete puzzle may be summarised thus.
Note that each piece may occupy a position in the finished puzzle in one of two orientations so that, for
example, piece number one may appear in the final solution as either or {1,0,1,0,0} or {0,0,1,0,1}. To reflect
this property of the pieces we make use of a 3d matrix P where p_{i,j,s} =
value of slot s of piece i in orientation j.
Subscript ranges defined are I=1..10 (pieces), J=1..2 (orientations), K=1..10 (positions),
S=1..5 (slots) and decision variables are as follows.
x_{i,j,k} = 1 if piece i in orientation j at position k, 0 otherwise
y_{j,s} = value of slot s in position j
The constraints required to ensure compliance with the puzzle conditions are:
Each piece is in one position and one orientation.
Each position has one piece in one orientation.
If we define cell {m,n} as the intersection of a horizontal piece and a vertical piece then the value of
each of these cells must sum to zero.
Cell values are consistent with piece positions.
As above, the aim of the puzzle is to find a feasible solution and we may select any appropriate
objective function to complete the formulation.
An XpressMosel model to solve the puzzle is here.
Chlond, M.J. and Toase C.M., (2003), IP Modeling and the Logical Puzzles of Raymond Smullyan,
INFORMS Transactions on Education, Vol. 3, No 3,
Gullberg, J., (1997), Mathematics: From the Birth of Numbers, W.W. Norton & Company Ltd

To
reference this paper, please use:
Chlond, M. J. (2005), "Classroom Exercises in IP Modeling: Su Doku and The Log Pile," INFORMS Transactions on Education, Vol. 5, No 2,
http://ite.pubs.informs.org/Vol5No2/Chlond/

