ILP Part 76 — Dead ends

This is the seventieth sixth 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 Ślepe zaułki (Dead ends). We have a board with shapes. We need to choose shapes to build a one-lane road from start to end, going through all circles. Shapes with triangles must be selected as well but they must be in dead ends.

Data model:

SelectedInPath indicates whether given field is on the path from start to end. SelectedShape indicates whether this field is in a selected shape. Next, we have couple variables for directions (as usual). Identifier and LowerNeighbourCount are for building a connected graph representing the path.


In lines 5-23 we define an input.

In lines 26-34 we create variables representing the model.

Next, we make sure directions for the path are propagated okay (lines 36-44, 46-54, 56-61).

Next, we calculate lower neighbours. We propagate an identifier through the graph (distance from the source) and here we just check directions and calculate neighbours with lower identifier. Next, in lines 77-86 we make sure the source has no lower neighbours and other fields on the path do. This is to make sure the path is connected.

Next, in 88-115 we propagate identifiers for the path. We make sure they differ by one accordingly.

Finally, we encode some rules for the task specifically. We make sure that shape is selected as one piece (lines 117-133). We then make sure that start, end, circles and triangles are selected and are on the path (or, for triangles, they are not on the path). We then make sure the path goes through selected shapes only (145-150). And at the end we guarantee that the path is “one lane” (lines 152-162).

Finally, solution: