ILP Part 100 — Literowce

This is the one hundredth 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’re going to solve Literowce. It’s similar to ILP Part 47 — Battleship puzzle. We have a board and some ships with letters on them. We need to put ships on the board, so they don’t collide with each other. The board has numbers on top and on the left. These numbers indicate how many ship parts are in given column or row. Also, the board has letters on the right and at the bottom. These letters indicate what is the letter closes to the edge in given row or column.

First, let’s start with the code:

That’s long. Let’s go part by part.

First, we need to define our ships. We’re not going to use letters. We’ll go with numbers instead. So the ship ABC is encoded as 123. This is in lines 1-8.

Next, we store numbers indicating how many parts are in given row and column. This is in lines 10-11.
Next, we store numbers indicating which ship part is the closest to the edge. This is in lines 12-13. Again, we replaced letters with numbers.

Next, a couple of helper variables in lines 15-19. Also, we’ll use directions represented as numbers. 0 indicates a ship stored horizontally to the right. 1 is going down. 2 is going left. 3 is going up.

Now, we need to represent our model. First, for each field at the board we’ll store a binary flag indicating whether the first part of the ship in given rotation is stored in this field. We call this part a “ship head”. This is in lines 21-29.

Another model is the actual numbers assigned to each field of the board. These numbers are non-negative, and 0 indicates that a given field is empty. This is in lines 31-35.

Next, we encode some basic rules. Each field can have at most one ship head – lines 37-51. Each ship must have its head somewhere – lines 53-67.

Next, every ship must assign numbers somewhere. So if we take ship 123 (ABC) and put its head in field 3,2, then fields 3,2; 3,3; 3,4 must have numbers assigned. We use an “if” condition encoded in ILP. This is in lines 70-99.

Next, we need to make sure that all fields without ships have no numbers assigned to them. So we count fields with numbers, and then we make sure this is equal to the total number of ship parts we have. This is in lines 101-111.

Next, we need to make sure that we don’t put a ship too close to the edge that would make it fall off the board. This is in lines 113-130.

Next, we need to make sure ships do not collide. We iterate over all fields, ships, and directions. Now, depending on the ship length and its direction, we take the correct rectangle (lines 143-153) without the ship itself. Next, we sum numbers in that rectangle, and set the sum to be equal to zero, so there are no numbers assigned. This is in lines 132-166.

Next, we make sure that when we put a ship on the board then no other ship can be put on top of it. So there is no other ship head on the top of some other ship. This is in lines 168-206.

Finally, we make sure we have correct number of ship parts in each row and column – lines 208-226.

Next, we do the same for very right and very bottom numbers in each row and column. We use condition to take the edge-most number. This is in lines 228-260.

That’s it. The output is:

And surprise! There is no solution! However, if we give it a little hint, and add the following constraint:

so we say that the very first ship should be put vertically, going down, and starting in field 0,2, then we get the following:

So not only it does find the solution, but also does it pretty fast.

This clearly shows that CPLEX isn’t infallible. We always need to remember that our formulas may be very correct, but the solvers may still fail us when looking for a solution.