ILP Part 75 — 100 and 13

This is the seventieth 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 100 and 13. We have a board with numbers and we need to find a path with given amount of numbers, with some specific sum, and where all numbers are different. First, data model:

And now the solution:

First, we define the riddle in lines 1-9, and couple helper variables in 12-13.

Next, we create fields in lines 16-24. Value is just the number in the field. Selected indicates whether the field is chosen to the final result. Up and other directions are for indicting whether path continues in some specific direction from this field. Identifier is to propagate numbers throughout the path to make sure we have only one path on the board.

First, we block invalid directions in lines 26-34. We want to make sure that we don’t step out of the board.

Next, in lines 36-44 we make sure that if some field thinks that path is going in some direction then the neighbour thinks the same.

Next, we make sure that if there is a path in the field then it must be selected (lines 46-51).

Next, we make sure the path is continuous (lines 53-59). This means that it cannot fork so it can go in at most two directions in given field.

Next, we indicate the path has a start and an end (line 62). This is actually not needed as we block forks but better safe than sorry.

We set path length (line 65) and sum of the numbers (line 68).

Next, we make sure that all numbers on the path are different. In lines 71-74 we take all variables and check their SelectedIdentifier to set this constraint, given field must differ from its neighbours by one, and its neighbours must differ by two. This effectively makes creating loops impossible.

Finally, solution: