1. Introduction

Tri-puzzle, produced by Lagoon Games, is an interesting little puzzle in the spirit of packing problems popularized by Golomb (1994) but with an additional twist. It consists of sixteen triangular pieces that fit snugly into a triangular tray. Each of the pieces is marked with three colored spots, one on each side (see image).

The pieces must be packed in such a way that all adjacent spots within the tray are color matched. Also, spots on the outer edges of the tray must be color matched with the respective edge pieces within the tray. Lessons learned in the formulation of rectangular and cubic packing puzzles (see, for example, Chlond, 2005) will help in modeling this puzzle but we run into a new and unexpected difficulty when attempting to generalize our solution to larger puzzles. A fiendish use of linear algebra allows us to surmount this obstacle.

2. Formulation

When the tray is successfully packed each of the 16 tiangular pieces is in one of 16 possible positions and in one of three possible orientations. We number these positions 1 through 16 starting at the top (the corner with the embedded coin) and counting down the tray and from left to right. Ten of the positions involve a triangle with an apex pointing upwards and in these cases we will number the spots 1 - top-left, 2 - top-right and 3 - bottom. The other six positions involve a piece with an apex pointing downwards and in these cases we number the spots 1 - top, 2 - bottom-left and 3 - bottom-right. We also number the pieces 1 through 16 and go on to define variables, ranges and data tables as follows:

  n = 16 - number of pieces and positions

 m = 3 - number of spots per traingle and number of orientations of triangle.

 c = 6 - number of different colors used

 T = 1..n, P = 1..n, O = 1..m, S = 1..m

 x_i,j,k = 1 if piece i in position j with orientation k , 0 otherwise

 y_j,m = color of spot j in position m where 1 through 6 represent the colors red, green, white, blue, black, yellow respectively.

 p_i,k,m = color of spot j for triangle k in orientation m

The aim of the puzzle is merely to obtain a safisfactory packing and hence we may select any arbitrary objective function. The first sets of constraints are relatively straightforward and will ensure that the tray is fully packed but not necessarily with the required color matchings in place.

Each position is occupied by one triangle in one orientation.

Each triangle is in one position and one orientation.

Next, we need to ensure that the spot colors in the finished tray are consistent with piece positions and orientations. This may be achieved as follows.

We now need to enforce all the necessary color matches. For the puzzle configuration depicted above this may be done, quite simply, by creating an explicit constraint for each required match. For example, y_1,1 = 2 enforces one of the outer matches and y_1,3 = y_3,1 enforces an inner match. There are 30 of these color constraints in all and an exhaustive list is in the OPL model here. The associated data file describing each piece in each orientation is here. In order to assemble the puzzle based on the output of this model it is convenient to examine the the contents of the Y matrix. For example, the first row of Y reads [2,6,3] indicating that the required colors in position 1 are green, yellow and white, hence we require piece 10 in orientation 1 in position 1 of the tray.

Whilst the above model is sufficient for the configuration under investigation and indeed for different color combinations for this particular tray size, to create a satisfactory general formulation we need to fully separate model and data. In the OPL model above the constraints that enforce color matchings are built into the model. This presents no problem if we wish to investigate configurations of this particular size only. However, if we wish to generalize the formulation to cope with larger tray sizes and the appropriate number of pieces to fill these trays, a little more thought is required.

We need to automate the generation of color matching constraints rather than stating each one explicitly. Careful examination of the list in the OPL model above reveals a pattern in the subscripted indices. Each of the three blocks of inner color matching constraints are to be generated within nested loops over the ranges i = 1..n-1, j = 1..i where n is the side length of the tray (in our case n = 4). For each of these blocks the subscripts may be described by quadratic functions of the loop counters i and j. It is not easy to see the exact form of these quadratic functions but they may be derived as follows.

First, we define column vector x as the coefficients of the required function where x₁ is the coefficient of i and x₂, x₃, x₄, x₅ are the coefficients of j, i², j², ij respectively and x₆ is the constant. Next, we define matrix A with columns for i, j, i², j², ij and the constant and for the ranges i = 1..3, j = 1..i as follows:

Finally, define column vector b as the list of subscript values we wish our quadratic function to generate. In the case of the left hand side subscripts of the first block of inner matches this is:

We are now in a position to write down and solve the following system of equations:

For the above b vector the solution is x = [-2,2,1,0,0,0]. Replacing b with the required subscripts of the right hand side of the first block of inner constraints and re-solving we obtain x = [0,2,1,0,0,0]. This first block of inner constraints may now be written more succinctly in OPL as:

forall(i in 1..n-1,j in 1..i) y[-2*i+2*j+i*i,3] == y[2*j+i*i,1];

This process may be repeated to obtain functions for all the color matching constraints. An OPL model that incorporates this idea is here and the associated data file is here.

The OPL constraint commands derived in this way may look unwieldy but they have the advantage that they work unedited for any value of n. We have, effectively, separated model from data. In order to use the model to solve puzzles involving larger tray sizes it is necessary only to provide an amended data file. Thus we may use our model to solve a variety of similar puzzles and also as an aid in the design and development of similar puzzles of different sizes and color configurations.

References

Chlond, M.J. (2005), "Box-packing Puzzles," INFORMS Transactions on Education, Vol. 5, No 3,

Golomb, S.W. (1994), Polyominoes:Puzzles, Patterns, Problems and Packings, Princeton University Press, ISBN 0-691-02444-8.

	To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
	To reference this paper, please use:  Chlond, M. J., (2005), "Tri-Puzzle: A Three-Cornered Conundrum," INFORMS Transactions on Education, Vol. 6, No 1,  http://ite.pubs.informs.org/Vol6No1/Chlond/