ILP Part 85 — Lying riddle

This is the eightieth 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 Lying riddle (Kłamigłówka).

We have a board split into parts. Each part has some numbers in it. A number indicates how many neighbouring fields (up, down, left, or right) are selected. One number in each part lies.

We need to select fields according to numbers. However, two selected fields cannot be neighbours and if they touch corners then they can’t split the board into multiple parts.

Solution:

First, in lines 14-38 we define the input. For numbers we use -1 to indicate there is no number in given field.

Next, we calculate neighbours in lines 55-64, just to know which fields are next to each other.

We start with straightforward constraints: one lier in each part (71-82), fields with number can’t be selected (85-88), selected fields can’t be next to each other (91-100), fields with numbers must have correct selected neighbours unless they lie (103-116).

Now, we take care of the requirement that we can’t split the board. First, we make sure a particular field is not isolated (123-132).

Next, we need to build a road from the starting position (bottom left corner) to each field. So we make sure that field is not selected and that we start counting from one (135-136).

Next, we calculate lower neighbours (142-147), we make sure that selected fields have very high id (150-157). Next, fields next to each other must differ by one unless any of them is selected (160-165). Finally, only one field (bottom left corner) can have no lower neighbours (168-174). That’s all.

Output: