ILP Part 95 — Yin and Yang

This is the ninetieth fifth 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 are going to solve this riddle. There is a board with yin and yang symbols on it. We need to cut the board in two pieces of the same shape in a way that each part contains exactly one yin and exactly one yang. In other way, we need to draw a continuous line on the board in a way that it splits the board into two parts of the same shape and the same number of yin and yang symbols.

Let’s see the code:

Let’s go line by line.

First, we start with definitions of variables. We define the board dimensions (lines 1-2), binaries representing the assignment of each field (line 4), and identifiers of the fields (line 5). Then, we initialize all the variables (lines 7-12).

First thing we need to tackle is how to cut the board in two pieces of the same shape. This is much easier than it seems. We can use the point reflection. Basically, we take a field of some coordinates, then find the matching field reflected by the middle of the board, and we make sure that these two fields belong to different pieces. So the sum of their values must be equal to one. This is in lines 14-19.

Next, we want to make sure that there is exactly one yin and one yang in a piece. So we sum values for yins, and make the sum equal to one. Same for yangs. This is in lines 21-23.

From now on we assume that value 0 means black field, and value 1 means white field.

Now, we need to craft the line going through the board. We assume that the top-left field is black. This assumption changes nothing, we could assume it’s white, and everything would work the same way.

Our idea is to assign identifiers to all black fields. Identifiers must increase in a BFS-like fashion. This is the same trick we used in many previous tasks. First step is to assign identifier zero to the top-left field – this is in lines 29-31.

Next, we iterate over all fields. For each field we check if it’s black (line 34), and then calculate how many black fields with lower identifiers are next to the current field (lines 35-39). Next, we need to make sure that if the current field is black, then there must be exactly one black neighbour with a lower identifier. This is in lines 41-47.

Finally, we make sure that white fields have identifier of 0. It doesn’t matter actually, but it’s a good idea to have this kind of hygiene. This is in lines 49-55.

Lastly, we need to remove duplicates. As the solver will find multiple solutions differing in the value of identifiers, we need to exclude them. We could do that by making sure identifiers increase by one, but at the same time we can remove these duplicates in a post-processing step. So we have a dictionary (line 62), and we iterate over all solutions (lines 64-79). For each solution, we first create its text representation (lines 66-70), and then ignore it if it’s a duplicate (lines 72-74). Otherwise, we store it (line 76), and print it (line 78).