Problem
This puzzle is an interesting pastime. Print out the 3x3 puzzle squares shown in Figure 1 on a color printer. Cut out the nine squares to place the 9 pieces on the table. The puzzle is simple: Arrange the pieces into a 3x3 square in such a way that the pieces matches up so that each “puz” front is matched up with the corresponding “zle” horizontally and vertically with the next piece. Good luck! Depending on the puzzle and how they are arranged, it’s quite a challenge. Great for a rainy day if your “Stop the Rain” spell doesn’t work! This puzzle is known as the “witch puzzle” because the pieces of some commercial games contain bitmaps of colored witches.
How would you solve such a problem? By “trialanderror”! No? After a while you’ll get used of the figures and how they are related to each other, so you may find a solution – or not and you give up! This “trialanderror” method has two important disadvantages: (1) you do not know how long it will take, until you find a solution, and (2) if you get other puzzles with different bitmaps, you need to begin the process of “getting into it” again. We would like to have a systematical method to solve all such kind of problems. This is only possible, if we make mental efforts and extract the essential from the problem, this is what we mean by “modeling”. We formulate a mathematical model!
The first approach could be to write a computer program, that enumerates all possible arrangements of the blocks (pieces). There are (in a 3x3 puzzle) 9! = 362880 possibilities to place the blocks at a particular position within the 3x3 square. Furthermore, each block can be turned in 4 rotations at each position, which are 4^{9} = 262144 ways. Hence, we have 9! ⋅ 4^{9} = 95′126′814′720 possible arrangement for this puzzle. If a computer could test 10^{9} arrangements per second, then a program would take 95 secs to enumerate all possibilities. In a 4x4 puzzle, however, the same program would take more than 1 billion of years to enumerate all arrangements, which are:
.
Of course, we do not need to check all arrangements. We can begin with a sample and hope that a solution is found quickly. Furthermore, enumerating the possibilities in a “intelligent” way avoids to check all of them.
It is also possible to use mathematical modeling techniques to find a way to solve this problem. And here we show how!
Modeling Steps
We begin to name explicitly all kind of known things in relation with this puzzle. At first this seems to be a trivial and boring task. However, it is absolutely necessary to order the ideas and to connect them using a certain formal and precise “language”. First we have 9 different blocks (pieces) and we begin to assign the numbers 1 to 9 to them (see Figure 2). We mark the numbers in the rightbottom corner of each block. It is not of importance how the are distributed over the blocks, the important thing is that each block is labeled with a different number.
The next step is to identify the 9 position within the resulting 3x3 square. We do this by a set of rows and columns (i ∈{1,…, 3} and j ∈{1,…, 3}), ordering them from left to right and from top to bottom. Then each position is a (i,j) combination with 1 ≤ i,j ≤ 3.
Next we define the 4 possible rotations. Suppose all blocks in Figure 2 are defined to have rotation 0^{o}. We can turn them counterclockwise by 90^{o}, by 180^{o}, and by 270^{o}, to get the four different possibilities of matchings. Let us define them with a set d ∈{1,…, 4}. For block number 1, Figure 3 shows the four different rotations. Remember, the rotation is counterclockwise.
Next we identify the different bitmaps on the blocks. Each block contains – at each side – one half of a figure. We assign them a number to identify them. There are 8 different halfs, in such a way that they can be completed to 4 different figures. The assignment of the number can be seen in Figure 4.
The assignment of the 8 numbers to the bitmaps is done in a way that the sum of the two complementary partial figures is always 9, for example, Bitmap 1 and Bitmap 8 (the first once), can be completed to a figure, and their sum is 9. This can be verified for all 4 figures. The reason for choosing the number in this way will be clarified below.
So far we did nothing else than identifying the elements, numbering and classifying them; boring activities, which seems to have nothing to do with “creative mathematics”! But we prepared the elements in a way to use them now. It is important – and rewarding – to stay with this “boring” activity until we have all elements in the right way: to have the right nomenclature, the right elements, names etc.
We have identified the 9 blocks, the 4 rotations, the 9 positions, and the 8 partial bitmaps. We now begin to compose the elements: Each block – in a particular puzzle – contains 4 bitmaps. The first block (BL1), for example contains the 4 bitmaps (3, 6, 6, 1) beginning with the top in clockwise direction. Hence, each blocks can be specified by four numbers, the four bitmaps on it. This information can be collected in a table (see Table 1).










BLOCKS  BL1  BL2  BL3  BL4  BL5  BL6  BL7  BL8  BL9 










top  3  2  6  7  2  3  2  8  2 










right  6  4  4  7  5  7  6  5  8 










bottom  6  8  4  1  5  5  5  3  8 










left  1  7  8  1  1  1  3  4  2 










For all these elements we introduce now mathematical symbols:

The blocks are denoted by a set k ∈ K = {1…9}

The positions are denominated by a tuple list as follows:

The rotations are formalized by the set d ∈ D = {1…4}

Finally, the data table of the bitmaps number for each blocks is generalized by a_{d,k}withd ∈ D,k ∈ K. A particular number a_{d,k} denotes the bitmap on the top of block k when the block is rotated counterclockwise by d. For example, a_{2,2} = 4, because block 2 contains the top bitmap 4, if the block is rotated 90^{0} counterclockwise.
This previous step, to introduce algebraic symbols, has the advantage that we are no longer talking about a particular puzzle, but about a whole class of similar puzzles. We can easily define a new puzzle just by replacing the numbers in the table a_{d,k}, for example.
Where are we now? What are we looking for? As far as we can see, we got all the data for the problem. Now we want to know which block should be put in which position and in what rotation in order to match all bitmaps horizontally and vertically. Hence, we want to know whether the block k ∈ K is at position (i,j) ∈ T in rotation d ∈ D or not. For each combination (i,j,k,d) we introduce a binary variable x_{i,j,k,d} which is 1 if the block k is at position (i,j) in rotation d, and 0 otherwise.
The constraints are as follows:

At each position (i,j), we must have exactly one block k in rotation d, hence:

Each block k must be put at a particular position (i,j) in a particular rotation d, hence:

Horizontally and vertically, the two complementary bitmaps must match. How can we fulfil these requirements? Let’s first see, what the requirements mean: Suppose, that we have a block with a bitmap 9 at the right edge in a position, say (1, 1). Then in position (1, 2) (at the right of (1, 1)) we must place a block so that at the left edge of this block we get the bitmap 1 (see Figure 5).
This match must be enforced for all transitions from position (i,j) to position (i,j + 1) with 1 ≤ i ≤ 3 and 1 ≤ j ≤ 2, this is the horizontal matching. It must also be enforced for the vertical matching for all transitions from position (i,j) to position (i + 1,j) with 1 ≤ i ≤ 2 and 1 ≤ j ≤ 3.

For each horizontal transition, we must have:
(Note that a_{d mod 4+1,k} is the right bitmap of block k and a_{(d+2) mod 4+1,k} is the left bitmap when the block is rotated by d in clockwise direction.)

For each vertical transition, we have:
Now, we also see why we choose to number the bitmaps in such a way that their complement sum is 9: The matching two halves of each bitmap have assigned numbers such that there sum is always 9! Of course, this is an arbitrarily decision. We could have assigned other numbers.
model witches "The Witch Puzzle I";
set i,j := [1..3] "The rows/columns";
d := [1..4] "The 4 rotations";
k := [1..9] "The 9 puzzle blocks";
integer parameter a{d,k} "The bitmap data"
:= [3 2 6 7 2 3 2 8 2
6 4 4 7 5 7 6 5 8
6 8 4 1 5 5 5 3 8
1 7 8 1 1 1 3 4 2];
/* integer parameter a{d,k} "The bitmap data"
:= [2 2 3 7 8 5 5 8 8
1 4 7 6 4 2 6 5 6
7 6 8 4 3 4 2 4 2
6 8 4 1 5 8 1 2 3]; */
binary variable x{i,j,k,d}
"Block k is at position (i,j) with rotation d?";
constraint
P{i,j}: sum{k,d} x = 1 "At each (i,j) is a block k";
Q{k}: sum{i,j,d} x = 1 "Each block is at a position";
H{i,jj<#j}: sum{k,d} a[d%4+1,k]*x[i,j,k,d]
+ sum{k,d} a[(d+2)%4+1,k]*x[i,j+1,k,d] = 9;
V{i,ji<#i}: sum{k,d} a[(d+1)%4+1,k]*x[i,j,k,d]
+ sum{k,d} a[(d+3)%4+1,k]*x[i+1,j,k,d] = 9;
maximize obj: x[1,1,9,2] ;
Write{i,j,k,dx}('Place the block %1s at (%1s,%1s) with rotation %1s' n', k,i,j,d);
end
Solution
The model prints the solution as follows:
Place the block 9 at (1,1) with rotation 2 Place the block 4 at (1,2) with rotation 1 Place the block 7 at (1,3) with rotation 2 Place the block 6 at (2,1) with rotation 2 Place the block 3 at (2,2) with rotation 4 Place the block 1 at (2,3) with rotation 2 Place the block 2 at (3,1) with rotation 3 Place the block 5 at (3,2) with rotation 2 Place the block 8 at (3,3) with rotation 1
This solution corresponds to the layout of the blocks that is given in Figure 6. For example, block 9 is at position (1, 1) rotated by 90^{o} counterclockwise (rotation 2).
For a new puzzle, we only need to specify the data table a_{k,d}.
Further Comments
The approach that is proposed for the witch puzzle is a nice exercise in modeling, however for solving larger problems we need other methods. The wellknown Ethernity II puzzle, the larger version of this puzzle could not be attacked with this method.
Questions

Figure 7 shown another puzzle. Solve it!

Modify the table a_{d,k} to
a{d,k} := [2 2 1 1 2 7 3 3 6
3 4 4 2 1 2 9 8 7
9 8 7 7 7 4 6 6 1
6 7 6 8 8 9 1 1 2];What is the solution? Verify the solution!

Generate your own puzzle! In particular, generate a 4 × 4puzzle and solve it.
Answers

You need to enumerate the blocks, to assign the numbers to the bitmaps and specify the table a_{d,k}. Then one can use the model specified.

The solution is:
Place the block 8 at (1,1) with rotation 4 Place the block 2 at (1,2) with rotation 1 Place the block 9 at (1,3) with rotation 2 Place the block 6 at (2,1) with rotation 2 Place the block 1 at (2,2) with rotation 1 Place the block 4 at (2,3) with rotation 4 Place the block 3 at (3,1) with rotation 1 Place the block 7 at (3,2) with rotation 4 Place the block 5 at (3,3) with rotation 4
To check we need to verify if all transitions sum up to 9.

The answer is given in model witches1 (see next section).
Alternative Formulations
The two constraints H and V can be formulated in different ways: “If at a position (i,j) a block k is placed in rotation d, then at the position to the right (or below) [(i,j + 1) or (i + 1,j)] a block must be placed in such a way that the two corresponding bitmaps matches”. This can be coded in LPL as follows:
H{i,j,k,dj<#j}: x > or{k1 in k,d1 in d  k<>k1
and a[d%4+1,k]+a[(d1+2)%4+1,k1]=9} x[i,j+1,k1,d1];
V{i,j,k,di<#i}: x > or{k1 in k,d1 in d  k<>k1
and a[(d+1)%4+1,k]+a[(d1+3)%4+1,k1]=9} x[i+1,j,k1,d1];
Still another formulation is as follows: “If at a position (i,j) a block k is placed in rotation d, then at the position to the right (or below) [(i,j + 1) or (i + 1,j)] a block must not be placed in such a way that the two corresponding bitmaps do not match”. It seems that this is simply a negation of the formulation above. However, it leads to a very different model containing much more constraints as the second approach. In LPL, the formulation is as follows:
H{i,j,k,d,k1 in k,d1 in dj<#j and k<>k1 and a[d%4+1,k]
+a[(d1+2)%4+1,k1]<>9}: x[i,j,k,d] +x[i,j+1,k1,d1] <= 1;
V{i,j,k,d,k1 in k,d1 in di<#i and k<>k1 and
a[(d+1)%4+1,k] + a[(d1+3)%4+1,k1]<>9}: x[i,j,k,d]
+ x[i+1,j,k1,d1] <= 1;
References
[1] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.
[2] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.