ILP Part 63 – Surasshupakku

This is the sixtieth third 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 Surasshupakku riddle. We have a board with letters on it and we need to cut the board in a way that each part has each letter exactly once. To make the solution unique we can cut using diagonals only, no horizontal or vertical lines allowed.

This is going to be a big one but let’s start with the code as usual:

Okay, let’s go one by one.

We start with defining variables for each field. Idea is we have 4 edges with numbers where a number identifies to which part the field belongs. We also have two binary flags indicating whether the field has diagonal crossed. This is in lines 16-28.

Next, we want to make sure edges are shared between fields. This is in lines 30-48. We just rewrite references, we could use equality on an ILP level.

Next, we make sure that a field is either empty or has one diagonal. Lines 53-64.

Next, we make sure edges have a positive number for parts. Lines 66-87.

Finally, we start the edge propagation. Idea is: if a field has diagonal crossed in it then this diagonal makes edge numbers different. This guarantees us that the cut is “not in the middle” but is from the very edge of the board. Why? Imagine that a cut ends somewhere in the middle and we require that edges on one side of the field have different value than edges on the other side of the field (because field is cut in half). But because that doesn’t cut whole piece, values will be propagated “around the corner” of the diagonal and we’ll get the contradiction so the only way to satisfy the requirements is to cut till the end of the board.

So in lines 89-114 we make sure that values are propagated correctly. For instance, if we have a field with / diagonal then bottom and right edges must have the same number, same for top and left, bot top and bottom must be different.

Next, in liens 116-162 we block some propagation “in the corner”. Similarly, in lines 164-223 we do not allow the propagation on the edges.

Now we know all edges will have some reasonable numbers. We can form the parts (pieces of the board).

So for each part we dedicate one special field which will be a sort of “starting point”. This is in lines 226-242. Next, in lines 244-257 we make sure that letters belong to parts correctly (so one letter in each part etc).

And this is almost all but it doesn’t guarantee that parts are compact. To guarantee that we’ll build a path in each part connecting all the nodes.

Idea is: we’ll build a path from some starting point in a part, going through all letters in that part. We start with some variables for crossing points in lines 265-275.

Next, we define variables for each crossing point in lines 277-307. InPath indicates whether a given crossing point is used in given path. Identifier is used to calculate the distance from starting point (indicated by IsStart). Degree is a helper field representing node degree being a number of edges going out of that node. Finally, LowerNeighboursCount shows how many nodes with lower identifier we are connected to.

In lines 309-322 we make sure that if two neighbouring crossing points are connected (so there is an edge in the path) then the edge must belong to the part as well. This means that we cannot connect two points from different parts.

Next, we calculate the node degrees in lines 324-349.

In lines 351-359 we make sure there is one starting point for each path. Staring point will be used as a source of the BFS algorithm.

Next, we make sure that letters of given part are included in the path (because our path is supposed to connect all letters). This is in lines 361-372.

In 374-380 we make sure that the starting point is on the path as well. Next, in lines 382-389 we make sure that nodes on the path have positive degrees (so there are no isolated points).

Finally, we start calculating the BFS distance. In lines 391-404 we make sure that neighbouring points differ in distance by one. Lines 406-413 make sure that all points on the path have some identifier (BFS distance). Finally, for each point we calculate how many neighbours have lower identifier in lines 415-444.

We use this count of lower neighbours to construct well-formed path. Starting point must have the lowest identifier on the path so in lines 446-453 we make sure that it has no lower nieghbours. On the other hand, each inner point must have exactly one lower neighbour, as set in lines 465-473.

That’s it. We then add a dummy goal and solve the problem. Output:

You can see it took almost 10 minutes to find the solution. You can see that the solution has two “dummy” cuts in top left corner which do not change the solution (although, we might want to get rid of them).

That was pretty intense but shows that you can construct pretty sophisticated things by combining various constraints.