ILP Part 94 — Horrendum

This is the ninetieth fourth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Let’s solve Horrendum. It’s a fancy sudoku. First, we need to make sure that numbers in rows and columns are unique (as always). We also need to make sure that the diagonal going from top left to the bottom right contains unique numbers as well. Next, each 8-pieces shape must have unique numbers. Finally, 8 blue fields must be unique, same as 5 pink shapes. Generally, nothing surprising, just a slight variation of Sudoku.

First, let’s see the regular solution:

Nothing new here. We first assign integers to groups, so we know which fields should be considered together. Next, we encode some known values. Finally, we create integers for each field, iterate over rows, columns, groups, and the diagonal, and add constraints. Output:

Great, it worked. However, CPLEX needed over 8 minutes to find a solution. That’s long. Can we do better?

The trick is to encode each number as binary digits. So let’s see the code:

There is a couple of changes, but they are mostly mechanical.

First, we use bits instead of integers (lines 27-33). So now we have a three-dimensional array of rows, columns, and bits for each field. That’s basically it. Now we need to make sure that our code compiles and works correctly with the new data representation, but it’s nothing challenging.

We set known values by turning up a respective bit (lines 35-42).

We then make sure that there is only one bit selected in each field (lines 44-50).

Next, we prepare a helper for setting “all different”, as we need to extract bit flags. The way we do it: we take a two-dimensional array where the former dimension represents the fields, and the latter represents the digits. We then iterate over numbers from 1 to 8, extract bit for a given number from all the fields passed as an argument, and then make sure that the sum of these bits is equal to one.

We then use this helper in other parts of the code. The output is:

CPLEX managed to find the solution in 0.14 second. That’s almost 3500 times faster!