ILP Part 77 — Stained glass

~ afish

This is the seventieth seventh 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 Cc kwadrat or Stained glass. The idea is: we have a 3×3 board and we need to put one of two types of pieces in each field. We need to count solutions.

Two solutions are considered equal if they are the same up to a) rotations b) rotations and mirroring

How to solve it? The idea is to calculate all the transformations in one model and then make sure that base one is selected uniquely.

Code for first case (rotations only):

We create binary variables in line 1. Then, we define helper function to rotate the board in lines 3-5.

Next, we need a hashing function to reduce whole board to one number. Decomposing bits into a number is enough (line 7).

Finally, we define all possible transformations in lines 9-14. Next, in line 16 we define that the base solution must be minimum of all transformations.

We then add couple settings to CPLEX:

And the output:

So you can see 140 solutions in total.

To solve second case (rotations and mirroring) we need to add this transformation:

and then create these solutions:

Final output:

Works like a charm.