ILP Part 59 – Pętliczek

This is the fifty ninth 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 Pętliczek. We have a chessboard of any size. Each column and row has a number associated which indicates how many edges in that line can be used. We need to build a continuous path (a loop) meeting the criteria. The line can self cross.

The code:

In lines 3 and 4 we define the board.

Lines 9-30 create variables. For each column and row crossing point we create three variables: one for edge going right, one for edge going down, one for the loop (we’ll come to that later).

In lines 32-41 we make sure we meet the constraint for columns. Similarly in lines 43-51 for rows.

Now we need to make sure the line is continuous. Similarly to the approach from the last part, each crossing point can have zero edges, two edges (for a straight line or a turning) or four edges (for self crossing). So we take edges from the point and from neighbors and then do some math.

Once again, we don’t make sure there is exactly one line because it just works. We’ll takle that challenge next time.

Output:

Printing the solution is interesting as well. Here in some more readable form:

Solution