MatMod logo

The Witch Puzzle I (witches)

Run LPL Code  ,  PDF Document

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.


PIC

Figure 1: A Witch Puzzle


How would you solve such a problem? By “trial-and-error”! 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 “trial-and-error” 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 49 = 262144 ways. Hence, we have 9! 49 = 95126814720 possible arrangement for this puzzle. If a computer could test 109 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:

   16  ′   ′   ′   ′  ′   ′   ′ 16! ⋅ 4 =  89862 698 310 039 502 848 000

.

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 right-bottom 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.


PIC

Figure 2: Witch: Labeling the Blocks


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 0o. We can turn them counter-clockwise by 90o, by 180o, and by 270o, 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 counter-clockwise.


PIC

Figure 3: Witch: Labeling the Rotations


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.


PIC

Figure 4: Witch: Labeling the Bitmap Figures


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










Table 1: Witch: the Puzzle’s Block Data


For all these elements we introduce now mathematical symbols:

  1. The blocks are denoted by a set k K = {19}

  2. The positions are denominated by a tuple list as follows:

    T = {(i,j)|i ∈ I,j ∈ I}withI = {1 ...3}
  3. The rotations are formalized by the set d D = {14}

  4. Finally, the data table of the bitmaps number for each blocks is generalized by ad,kwithd D,k K. A particular number ad,k denotes the bitmap on the top of block k when the block is rotated counter-clockwise by d. For example, a2,2 = 4, because block 2 contains the top bitmap 4, if the block is rotated 900 counter-clockwise.

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 ad,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 xi,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:

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

    ∑  xi,j,k,d = 1   forall (i,j) ∈ I × I k,d
  2. Each block k must be put at a particular position (i,j) in a particular rotation d, hence:

    ∑  xi,j,k,d = 1 forall k ∈ K i,j,d
  3. 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).


    PIC

    Figure 5: Witch: Matching Bitmaps


    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.

  4. For each horizontal transition, we must have:

    ∑        ∑  a    ⋅ x +  a    ⋅ x    = 9   dmod 4+1,k   i,j,k,d  (d+2 )mod4+1,k  i,j+1,k,d  k,d       k,d                 forall i ∈ I, j ∈ I  {3}

    (Note that ad 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.)

  5. For each vertical transition, we have:

    ∑        ∑  a    ⋅ xi,j,k,d +   a    ⋅ xi+1,j,k,d = 9   (d+1) mod4+1,k      (d+3)mod 4+1,k  k,d       k,d                 forall i ∈ I  {3},j ∈ I

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.

Listing 1: The Complete Model implemented in LPL [2]

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,j|j<#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,j|i<#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,d|x}('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 90o counter-clockwise (rotation 2).


PIC

Figure 6: The Solution of the Witch Puzzle


For a new puzzle, we only need to specify the data table ak,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 well-known Ethernity II puzzle, the larger version of this puzzle could not be attacked with this method.

Questions

  1. Figure 7 shown another puzzle. Solve it!


    PIC

    Figure 7: Another Witch Puzzle


  2. Modify the table ad,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!

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

Answers

  1. You need to enumerate the blocks, to assign the numbers to the bitmaps and specify the table ad,k. Then one can use the model specified.

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

  3. 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,d|j<#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,d|i<#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 d|j<#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 d|i<#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.