Volume 5, Number 2, January 2005

 

Classroom Exercises in IP Modeling:
Su Doku and The Log Pile
 
 
Martin J.Chlond
Lancashire Business School
University of Central Lancashire
Preston PR1 2HE, UK
 
 
 
 

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.

1. Introduction

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 Xpress-Mosel 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.

2. Su Doku

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.

sudoku.gif

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.

2.1 Formulation

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 xi,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 x1,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*(m-1)+i
    		  b := 3*(n-1)+j
    		  t := P(a,b)
   
		  if(t >= 1) then
		    kc(i,j,t,m,n) := X(i,j,t,m,n) = 1
		  end-if
		
		end-do
		

Since the aim of the puzzle is merely to fulfil these conditions we may select any appropriate objective function to complete the formulation.

An Xpress-Mosel model to solve the puzzle is here.

2. The Log Pile

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

logpile.jpg

The objective is to empty the pieces from the box and, quite simply, to re-pack them.

2.1 Formulation

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.
pieces.gif

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 3-d matrix P where pi,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.

xi,j,k = 1 if piece i in orientation j at position k, 0 otherwise
yj,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 Xpress-Mosel model to solve the puzzle is here.

References

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/