ILP Part 99 — MacMahon Squares

This is the ninetieth ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we’re going to solve MacMahon Squares. Let’s see the code:

Let’s start with elements. We take the following image and want to encode is an array of integers (lines 1-26). Each square has four triangles: the top one, the right one, the bottom one, and the left one. We then number colors, so white is assigned 0, red is 1, blue is 2. So numbers 1, 0, 2, 0 represent a square that is white on the top, blue on the bottom, and has white sides (second square from the left in the second row).

We then define some helper variables for the board size (lines 28-31).

Next, we define the board a four-dimensional array. First dimension is the Y axis (height), then X axis (width), number of square, and finally its rotation. So element fields[y][x][element][rotation] indicates whether we decided to put element element rotated rotation times in field x, y.

Okay, now we need to encode rules. We start with the requirement that each element must be placed on the board just once. So for each element we take all the fields for all the positions and all the rotations, sum all of that, and make sure it’s equal to one – lines 43-53.

Now we do the same for all fields. So we iterate over fields, and for every one of them we take all the elements in all the rotations, sum the variables, and set to one – lines 55-65.

Now we need to match the edges. We iterate over all fields that have right edge and some other field on the right. We then iterate over all elements, and check all of their rotation combinations. We take every combination for which edges do not match, and then we make sure that such a combination cannot be selected for these two fields. This is in line 68-89. We then do the same for bottom and top endges – lines 91-113.

That’s it. Now the output:

So we can see, that in the top right corner we selected element number 21 (it’s 0-based) in first rotation (again, 0-based). And so on.