ILP Part 60 – Fencing Match

This is the sixtieth 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 Fencing Match. We have a board with some numbers on it. Each number indicates how many edges of that field must be included in the road. We need to build the closed road (loop) meeting the requirements.

Code:

In line 3 we encode the board as a string.

We are going to model two things: fields and crossing points. Each field has four edges (top, bottom, left, right) represented by binary variables. You can see that in lines 8-24.

In lines 26-38 we define some helpers, and then in lines 40-49 we make sure that edges of adjacent fields match (so right edge of some field is equal to the left edge of the field on the right).

Second thing we model is crossing points. For each field there is one crossing point in the top left corner, also, fields on the right and bottom boundary have additional crossing points in the bottom right corner. This is in lines 51-76. We also define another variable IdVar for numbering the points in a BFS-like style later.

Next, we make sure crossing points match. Each crossing point includes up to four edges (left, right, up, down) which need to match with field edges. A lot of juggling in lines 78-137.

That was “simple” but cumbersome. Once we have the correct model we can easily model our requirements.

First, in lines 128-137 we make sure that edges of fields with numbers are selected properly.

In lines 139-159 we make sure the road is continuous. The same trick as always — we take edges for a given crossing point and make sure that either none of them or exactly two of them are selected for the road.

Finally, in lines 161-2016 we make sure there is exactly one road. We ignored this requirement in previous parts so it’s high time to takle it.

We base our idea on BFS-like approach. We want to cut the road in two equal halves, identify one “end” of it as a starting point and then number all points on the road based on the Manhattan distance.

We designate two points which we call “top left” and “bottom right”. They don’t need to be actual top-left-most and bottom-right-most points on the road. We need to make sure there is exactly one top left and one bottom right. This will guarantee there is exactly one road. So we start with lines 162 and 163 which we use to count the points and then in lines 215-216 we set the constraint.

Starting in line 165 we iterate through all the crossing points. We define binaries for top left and bottom right points in lines 170-171. We then add them in lines 173 and 174. Effectively only one road point will be a “top left” and some other will be “bottom right”.

We also calculate if given point is special – either top left or bottom right – in line 175.

Now we need to implement the BFS-like logic. In line 177 we use conditions to specify that if this point is a bottom-right one then its IdVar must be equal to zero. This effectively starts the numbering. Notice that IdVar is a natural number. If this point is not a bottom-right corner then line 177 set its IdVar to a free variable effectively neutralizing the constraint. This is actually how you make “if” condition in ILP (instead of “if-else” expression).

Next, in lines 181-196 we find neighbors. We group tuples of neighbours’ IdVars and our edges. Then in lines 198-200 we add a constraint that if there is a road (edge is equal to one) then neighbour’s IdVar must differ by one from our value. Since we operate on natural numbers and we start numbering from zero, neighbours will have increasing values.

In lines 202-209 we make some magic. If you take a continuous road and number points starting from the corner, you can see that for each “middle” point neighbours’ IdVars differ by two. However, for two special points (top left and bottom right corners) the neighbours are equal. This is what we set here — we conditionally take IdVars for neighbours (if there are edges) and then set the difference to zero or two, depending on whether given point is a special corner or not.

Finally, in line 211 we make sure that the special point can be on the road only — if is special is one (so given point is a corner) then we use material implication to indicate that at we must have some edges set for this field.

Output:

Printing may be a little misleading at first sight but it shows the correct answer.

Also, this solution is prone to numerical instability.